What Are SCARY Iterators?

What Are SCARY Iterators?

Rate This
  • Comments 8

Diego DagumHi 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 "Minimizing Dependencies within Generic Classes for Faster and Smaller Programs" and N2980 "SCARY Iterator Assignment and Initialization, Revision 1.

What are they useful for? What are they, in the first place? What’s so SCARY about them?

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

 

 

 

Imagine the following situation:

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

 

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

  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> &'
  2. 1>          with
  3. 1>          [
  4. 1>              _Mylist=std::_List_val<int,std::allocator<int>>
  5. 1>          ]
  6. 1>          and
  7. 1>          [
  8. 1>              _Mylist=std::_List_val<int,stdext::allocators::allocator_unbounded<int>>
  9. 1>          ]
  10. 1>          and
  11. 1>          [
  12. 1>              _Mylist=std::_List_val<int,std::allocator<int>>
  13. 1>          ]
  14. 1>          Reason: cannot convert from 'std::_List_iterator<_Mylist>' to 'const std::_List_iterator<_Mylist>'
  15. 1>          with
  16. 1>          [
  17. 1>              _Mylist=std::_List_val<int,stdext::allocators::allocator_unbounded<int>>
  18. 1>          ]
  19. 1>          and
  20. 1>          [
  21. 1>              _Mylist=std::_List_val<int,std::allocator<int>>
  22. 1>          ]
  23. 1>          No user-defined-conversion operator available that can perform this conversion, or the operator cannot be called

 

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

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.

Based on research paper N2911 "Minimizing Dependencies within Generic Classes for Faster and Smaller Programs", the acronym SCARY describes

Assignments and initializations that are Seemingly erroneous (appearing Constrained by conflicting generic parameters), but Actually work with the Right implementation (unconstrained bY the conflict due to minimized dependencies)

… or just SCARY, you know... (Don’t kill the messenger, I wasn’t the inventor of this name!)

 

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!

 

 

 

Epilogue

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" tells, it's a more general issue that can happen when designing generic classes. In its authors’ own words:

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.

Worth reading. Enjoy!

 

PS. A HUGE THANKS to Stephan T. Lavavej (Mr. STL) for reviewing this post.

  • The person who coined the name certainly went to unimaginable lengths to come up with a cool name!

  • Yeah... I'm not a 100% sure but I believe that he's the same guy who created the acronym RAII (Resource Acquisition Is Initialization). Although if I'm right about the guy, he still owns the credits for having invented the programming language which, without it, we wouldn't be discussing in this space. :-)

  • C++ syntax is very hard.Microsoft must implement new native language such as C# syntax.

    C++ is depend to 1980.

    new native language with garbage collection and ...

  • Indeed it is harder, fery. But have you been following the syntax improvements achieved with the latest standard C++11? I recommend you this reading by Herb Sutter as I see you talking about garbage collection and I feel, correct me if I'm wrong, like you may not be aware about improvements like smart pointers in this case. Herb's paper is here: herbsutter.com/elements-of-modern-c-style

  • Hi, thanks for improvements! Maybe you can (binary compatibly!) reduce the increadible slowdown of iterators in debug mode in next release? Try something like std:vector<std:list<int>:iterator>. That would be Great!

  • I think the acronym RAII (for "Resource Acquisition Is Initialization")  was given by Bjarne Stroustrup himself.

  • Narom: First, the STL gets to break binary compatibility between major releases (which is wonderful). Second, I have an idea to reduce the cost of our extensive correctness checks in debug mode, which I'd like to try someday. (Currently, we track iterators with a singly-linked list; I suspect that a doubly-linked list would be significantly more efficient when a container has many iterators.) However, it will always be quite expensive in absolute terms, since we need to take locks for operations that look like reads.

  • > First, the STL gets to break binary compatibility between major releases (which is wonderful).

    Yes ... and starting with VS10 it even refuses to link against incompatible versions (provided they are VS10+ too), which is also wonderful. Of course, that only means that I'm protected against linking my VS11 program against a VS10 library, not my VS10 program against a VS8 library. If you do that, you still get surprising runtime crashes.

    To think that you guys implemented a compiler/linker extension to achieve this, when the C++11 standard has inline namespaces to achieve the same thing, only in a way that would protect against the second class of errors too.

Page 1 of 1 (8 items)