std::insert_iterator and iterator invalidation

Question

I tried writing a generic, in place, intersperse function. The function should intersperse a given element into a sequence of elements.

#include <vector>
#include <list>
#include <algorithm>
#include <iostream>

template<typename ForwardIterator, typename InserterFunc>
void intersperse(ForwardIterator begin, ForwardIterator end, InserterFunc ins, 
                 // we cannot use rvalue references here, 
                 // maybe taking by value and letting users feed in std::ref would be smarter
                 const ForwardIterator::value_type& elem) {
  if(begin == end) return;
  while(++begin != end) {
    // bugfix would be something like:
    // begin = (ins(begin) = elem); // insert_iterator is convertible to a normal iterator
    // or
    // begin = (ins(begin) = elem).iterator(); // get the iterator to the last inserted element

    // begin now points to the inserted element and we need to
    // increment the iterator once again, which is safe
    // ++begin;
    ins(begin) = elem;
  }
}

int main()
{
  typedef std::list<int> container;
  // as expected tumbles, falls over and goes up in flames with:
  // typedef std::vector<int> container;
  typedef container::iterator iterator;
  container v{1,2,3,4};

  intersperse(v.begin(), v.end(), 
              [&v](iterator it) { return std::inserter(v, it); },
              23);
  for(auto x : v)
    std::cout << x << std::endl;
  return 0;
}

The example works only for containers that do not invalidate their iterators on insertion. Should I simply get rid of the iterators and accept a container as the argument or am I missing something about insert_iterator that makes this kind of usage possible?

score 2 · Accepted Answer · answered Feb 06 '12 at 00:37

The example works only for containers that do not invalidate their iterators on insertion.

Exactly.

Should I simply get rid of the iterators and accept a container as the argument

That would be one possibility. Another would be not making the algorithm in-place (ie. output to a different container/output-iterator).

am I missing something about insert_iterator that makes this kind of usage possible?

No. insert_iterator is meant for repeated inserts to a single place of a container eg. by a transform algorithm.

AnT stands with Russia · Answer 2 · 2012-07-04T23:15:43.633

The problems with your implementation have absolutely nothing to do with the properties of insert_iterator. All kinds of insert iterators in C++ standard library are guaranteed to remain valid, even if you perform insertion into a container that potentially invalidates iterators on insert. This is, of course, true only if all insertions are performed through only through the insert iterator.

In other words, the implementation of insert iterators guarantees that the iterator will automatically "heal" itself, even if the insertion lead to a potentially iterator-invalidating event in the container.

The problem with your code is that begin and end iterators can potentially get invalidated by insertion into certain container types. It is begin and end that you need to worry about in your code, not the insert iterator.

Meanwhile, you do it completely backwards for some reason. You seem to care about refreshing the insert iterator (which is completely unnecessary), while completely ignoring begin and end.

`This is, of course, true only if all insertions are performed through only through the insert iterator` I don't know why this is not in en.cppreference.com Thank you ! — Martin Morterol, Nov 29 '21 at 08:08

std::insert_iterator and iterator invalidation

2 Answers2

Linked