{"id":2503,"date":"2012-04-06T09:33:00","date_gmt":"2012-04-06T09:33:00","guid":{"rendered":"https:\/\/blogs.msdn.microsoft.com\/vcblog\/2012\/04\/06\/what-are-scary-iterators\/"},"modified":"2021-10-04T10:55:34","modified_gmt":"2021-10-04T10:55:34","slug":"what-are-scary-iterators","status":"publish","type":"post","link":"https:\/\/devblogs.microsoft.com\/cppblog\/what-are-scary-iterators\/","title":{"rendered":"What Are SCARY Iterators?"},"content":{"rendered":"

\"Image<\/a><\/p>\n

Hi there! I’m Diego Dagum, a Program Manager with the Visual C++ team.<\/p>\n

As Stephan announced last September when Visual Studio 11 Developer Preview was released<\/a>, our STL implementation comes with SCARY iterators<\/strong>. On Stephan’s words,<\/p>\n

\n

”(…) as permitted but not required by the C++11 Standard, SCARY iterators have been implemented, as described by N2911 “Minimizing Dependencies within Generic Classes for Faster and Smaller Programs<\/em>“<\/a> and N2980 “SCARY Iterator Assignment and Initialization, Revision 1<\/em>”<\/a>.<\/p>\n<\/blockquote>\n

What are they useful for? What are they, in the first place? What’s so SCARY about them?<\/p>\n

In this post I’ll demystify any mystery about SCARY iterators, hopefully inspiring in you some design best practice for your own template classes.<\/p>\n

 <\/p>\n

 <\/p>\n

 <\/p>\n

Imagine the following situation:<\/p>\n

\n
\n
\n
    \n
  1. \/\/ the list below uses an allocator other than the default<\/span><\/li>\n
  2. list<\/span><<\/span>int<\/span>, stdext::allocators::<\/span>allocator_unbounded<\/span><<\/span>int<\/span>>> l;<\/span><\/li>\n
  3.  <\/li>\n
  4. \/\/ Is the following line valid? (i.e. does it compile?)<\/span><\/li>\n
  5. list<\/span><<\/span>int<\/span>>::<\/span>iterator<\/span> iter(l.begin());<\/span><\/li>\n<\/ol>\n<\/div>\n<\/div>\n<\/div>\n

     <\/p>\n

    Does it compile or not? Well, I tried to compile that code using a pre-v11 Visual C++ compiler, getting the following error:<\/p>\n

    \n
    \n
    \n
      \n
    1. error C2664: ‘std::_List_iterator<_Mylist>::_List_iterator(const std::_List_iterator<_Mylist> &)’ : cannot convert parameter 1 from ‘std::_List_iterator<_Mylist>’ to ‘const std::_List_iterator<_Mylist> &’<\/li>\n
    2. 1>          with<\/li>\n
    3. 1>          [<\/li>\n
    4. 1>              _Mylist=std::_List_val<int,std::allocator<int>><\/li>\n
    5. 1>          ]<\/li>\n
    6. 1>          and<\/li>\n
    7. 1>          [<\/li>\n
    8. 1>              _Mylist=std::_List_val<int,stdext::allocators::allocator_unbounded<int>><\/li>\n
    9. 1>          ]<\/li>\n
    10. 1>          and<\/li>\n
    11. 1>          [<\/li>\n
    12. 1>              _Mylist=std::_List_val<int,std::allocator<int>><\/li>\n
    13. 1>          ]<\/li>\n
    14. 1>          Reason: cannot convert from ‘std::_List_iterator<_Mylist>’ to ‘const std::_List_iterator<_Mylist>’<\/li>\n
    15. 1>          with<\/li>\n
    16. 1>          [<\/li>\n
    17. 1>              _Mylist=std::_List_val<int,stdext::allocators::allocator_unbounded<int>><\/li>\n
    18. 1>          ]<\/li>\n
    19. 1>          and<\/li>\n
    20. 1>          [<\/li>\n
    21. 1>              _Mylist=std::_List_val<int,std::allocator<int>><\/li>\n
    22. 1>          ]<\/li>\n
    23. 1>          No user-defined-conversion operator available that can perform this conversion, or the operator cannot be called<\/li>\n<\/ol>\n<\/div>\n<\/div>\n<\/div>\n

       <\/p>\n

      The reason I’ve got this error is that in the last line of the code I’m trying to initialize iter<\/span> (an iterator over a list of int<\/span> using the default list allocator std::allocator<int<\/span>><\/span>) with an iterator which looks similar excepts that it corresponds to a list allocated by the alternative stdext::allocators::allocator_unbounded<int<\/span>><\/span>. Sad but true, these are different specializations of list of int<\/span>s; therefore, conversions between them can’t be handled by default.<\/p>\n

      From a compiler perspective there is nothing wrong here. From a practical standpoint, however, there isn’t any semantic dependence between list iterators and list allocators. And, in general for all STL containers, iterators only depend (semantically speaking) on the container element type.<\/p>\n

      Based on research paper N2911<\/a> “Minimizing Dependencies within Generic Classes for Faster and Smaller Programs<\/em>“, the acronym SCARY describes<\/p>\n

      \n

      Assignments and initializations that are <\/em>S<\/span>eemingly erroneous (appearing <\/em>C<\/span>onstrained by conflicting generic parameters), but <\/em>A<\/span>ctually work with the <\/em>R<\/span>ight implementation (unconstrained b<\/em>Y<\/span> the conflict due to minimized dependencies)<\/em><\/p>\n<\/blockquote>\n

      … or just SCARY, you know… (Don’t kill the messenger, I wasn’t the inventor of this name!)<\/p>\n

       <\/p>\n

      In our STL11 implementation, iterator dependencies were minimized so the precedent code compiles fine. The same applies for any other STL container iterator (vector, deque, etc.) This said, you’ll be able to implement novel algorithms in ways that were previously impossible due to type mismatches. Not that scary, after all!<\/p>\n

       <\/p>\n

       <\/p>\n

       <\/p>\n

      Epilogue<\/h2>\n

      The issue that prevented my program to compile isn’t just tied to a particular STL implementation. In fact, as N2911 “Minimizing Dependencies within Generic Classes for Faster and Smaller Programs<\/em>“<\/a> tells, it’s a more general issue that can happen when designing generic classes. In its authors’ own words:<\/p>\n

      \n

      We advocate a design principle whereby the dependencies between the members and the type parameters of a generic class should be minimized, we propose techniques to realize this principle, and we show that the principle can be leveraged to achieve faster and smaller programs.<\/em><\/p>\n<\/blockquote>\n

      Worth reading. Enjoy!<\/p>\n

       <\/p>\n

      PS. A HUGE THANKS to Stephan T. Lavavej (Mr. STL) for reviewing this post.<\/p>\n","protected":false},"excerpt":{"rendered":"

      Hi there! I’m Diego Dagum, a Program Manager with the Visual C++ team. As Stephan announced last September when Visual Studio 11 Developer Preview was released, our STL implementation comes with SCARY iterators. On Stephan’s words, ”(…) as permitted but not required by the C++11 Standard, SCARY iterators have been implemented, as described by N2911 […]<\/p>\n","protected":false},"author":293,"featured_media":35994,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_acf_changed":false,"footnotes":""},"categories":[1],"tags":[68,32],"class_list":["post-2503","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-cplusplus","tag-design","tag-stl"],"acf":[],"blog_post_summary":"

      Hi there! I’m Diego Dagum, a Program Manager with the Visual C++ team. As Stephan announced last September when Visual Studio 11 Developer Preview was released, our STL implementation comes with SCARY iterators. On Stephan’s words, ”(…) as permitted but not required by the C++11 Standard, SCARY iterators have been implemented, as described by N2911 […]<\/p>\n","_links":{"self":[{"href":"https:\/\/devblogs.microsoft.com\/cppblog\/wp-json\/wp\/v2\/posts\/2503","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/devblogs.microsoft.com\/cppblog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/devblogs.microsoft.com\/cppblog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/cppblog\/wp-json\/wp\/v2\/users\/293"}],"replies":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/cppblog\/wp-json\/wp\/v2\/comments?post=2503"}],"version-history":[{"count":0,"href":"https:\/\/devblogs.microsoft.com\/cppblog\/wp-json\/wp\/v2\/posts\/2503\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/cppblog\/wp-json\/wp\/v2\/media\/35994"}],"wp:attachment":[{"href":"https:\/\/devblogs.microsoft.com\/cppblog\/wp-json\/wp\/v2\/media?parent=2503"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/cppblog\/wp-json\/wp\/v2\/categories?post=2503"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/cppblog\/wp-json\/wp\/v2\/tags?post=2503"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}