std::set iterator is implicitly const



iterator invalidated{erase: opaque

See also

I had multiple encounters with STL iterator invalidation, esp. after erase().

  • sometimes I get correct result
  • sometimes I get segfault
  • sometimes I get incorrect result

Opaque i.e. no obvious clues, so no keyword to google

Luckily my code was 20-lines

Luckily i could reproduce it once a while.

This is another example of tough bugs to hunt down.

STL iterator invalidation rules, succinctly is concise with explanations. Specifically,

  • list insertions don’t invalidate any iterator. I feel iterator is a pointer to a node.
  • tree insertions don’t invalidate any iterator. Same reason as list.
  • for erasure from lists or trees, only the iterator to the erased node is invalidated.

Now for vector:

  • vector insertion invalidates any iterator positioned somewhere after the insertion point. If reallocation happens due to exceeding vector.capacity() then all invalidated

declare iterator]function template #gotcha

(Needed in some coding interviews and also in GTD!)

Update: With c++11, you can use the “auto” keyword and avoid the complexity.

If you drop the “typename” from the for-loop header, then compiler is confused

error: dependent-name ‘std::multiset::iterator’ is parsed as a non-type, but instantiation yields a type
note: say ‘typename std::multiset::iterator’ if a type is meant

Basically, we need to be extra explicit to the confused compiler.

template<typename T> ostream & operator<<(ostream & os, multiset<T> const & l){
  for(typename multiset<T>::iterator it = l.begin(); 
      it != l.end(); ++it){
        os<<*it<<" ";

iterators : always pbclone !! pbref or by pointer

Iterators – generalizations of pointers – are expected to be copied cheaply. The copy cost is never raised as an issues.

Iterators are usually passed by value. Sutter and Alexandrescu recommended (P154 in their book) putting iterators into containers rather than putting pointers into containers. Containers would copy the iterators by value.

someContainer.end() often returns a temp object, so taking its address is a bug. The returned iterator object from end() must be passed by Value.

Someone online said that If an argument is taken by value, this makes it usually easier for the compiler to optimize the code. Look at the advantage of using function objects by value instead of taking function pointers. This is a similar reason for by-value parameters reasoned on the level of functions objects.

Note java/c# arguments are predominently passed by reference.

calling same method on unrelated objects: c++template outshines java

Suppose pure abstract class Animal has a die() method, and so does Project, Product, Plant and Planet, but they don’t share a base class. How would you write a reusable function that invokes this method on a generic input object, whose type could be any of them?

Java can’t do this. In C++ you create

template<typename T>  f1(T input){ input.die(); }

If you pass an int into f1(), then you get compile time error. Probably a linker error. Is this SFINAE ? I doubt it.

STL algorithms routinely take an iterator argument and then call operator>() on the iterator. Now, this operator is undefined for a lot of iterator INSTANCES. I think only RandomAccessIterator category supports it.

Q: So how does STL make sure you don’t pass an object of ForwardInterator category into such a function?
A: use the template parameter type name (dummy type name) as a hint. Instead of the customary “T”, they put a suggestive dummy type name like “BidirectionayInterator” or “InputIterator”. If you ignore the hint you get compile-time error.

Now we understand that STL iterators have no inheritance hierarchy, but “stratification” among them.

y create custom STL iterators, briefly

Q: when would you write your own STL iterator?

I think if you create your own customized container, you probably need custom iterator Objects. You probably need to return such an Object from rbegin() etc.

In python, c# and (less commonly) in java, many data structures can be made iterable. There’s an implicit iterator.

[[STL tutorial]] has a 3-page chapter showing a debuggable-iterator that reveals interesting details of the inner workings of STL containers and STL algorithms.

inputIterator category — unneeded?

Q: why there's a category “Input Iterator” at all, where is it used? (Output iterator is a similar story, so this post will omit it.)

I think the only major use is input stream.

There are some algorithms like std::merge(…) that require a tiny *subset* of a C pointer's full capabilities.

To make merge() useful on an input stream, STL authors put the Dummy type name “InputIterator” into merge() template declaration as a *hint* — a hint that in the implementation, only that *subset* of pointer capabilities are used. This is a hint to containers

“Hey Containers, if you have an iterator capable of deference-then-read, then you can use me.”

It turned out all containers except output stream has that capability.