What's the difference between iterator and back_insert_iterator?

Question

If random access iterators can be used to access elements at an arbitrary offset position relative to element they point to (somehow like pointers), why can't they be used in generic algorithms like std::copy() instead of using back_insert_iterator, and what's the difference between both?

Answer 1

std::back_insert_iterator is a specific kind of output iterator which supports push_back operation. When you write to it using operator=, it push_backs the value into the underlying container — so, in that sense it acts as an adaptor for containers which has push_back member function.

An example would be easy to understand:

std::vector<int> v;

std::back_insert_iterator<std::vector<int>>  it(v);

*it = 10; // it is equivalent to v.push_back(10);
 it = 99; // it is ALSO equivalent to v.push_back(99);

for (auto const & i : v)
    std::cout << i << " " ; //10 99

It outputs :

10 99

Online Demo.

The usual iterator operations ++ and * on it has no effect.

But you rarely use them directly (I've never used it directly untill now). You use them with algorithms, such as std::copy in which case you also use std::back_inserter function which returns an object of type std::back_insert_iterator.

//assuming dest is a container which supports push_back!
std::copy(src.begin(), src.end(), std::back_inserter(dest));

You would also like to see the following (adaptor) iterators:

• std::front_insert_iteratorn supports push_front operation
• std::insert_iterator supports insert operation.

So depending on the container, you choose adaptor iterator.

Note that all of them are output iterator.

why can't they be used in generic algorithms like std::copy() instead of using back_insert_iterator.

Of course, you can use the random access iterators (or any output iterator) in algorithms like std::copy, as third argument, but that assumes the iterator is referencing to existing range — *it and ++it are well-defined for the value you passed. You pass them to overwrite the existing elements of the range, whereas std::back_insert_iterator adds new elements to the container.

Hope that helps.

Answer 2

Actually, you can totally use a regular iterator in std::copy.

int main() {
    std::vector<int> vec{1, 2, 3, 4};

    std::list<int> list{vec.size()};

    std::copy(vec.begin(), vec.end(), list.begin());

    // list = 1, 2, 3, 4
}

However, as you may note, it means that:

• you first create len(source range) default elements
• and then copy elements from the source range to the destination range 1 by 1

which is rather inefficient, and requires that elements can be default constructed and then assigned to.

Instead, back_insert_iterator is a fake iterators, which operates as an Adaptor over a regular container. If you look at the interface you will see that it does not behave as a regular iterator at all, and just calls push_back on the underlying container reference it embeds whenever you try to push an item in.

int main() {
    std::list<int> list;

    std::back_insert_iterator<std::list<int>> bii(list);

    bii = 1;
    bii = 2;
    bii = 3;
    bii = 4;

    // list = 1, 2, 3, 4

    // note: decltype(*bii) == bii&, so deferencing bii serves no purpose;
    // similarly, ++bi does nothing either; both operations are just defined
    // to mimick a regular operator interface so it can be used in regular
    // algorithms over iterators.
}

Thus, the two approaches are equally valid, but have different behaviors:

• a regular iterator allows you to overwrite an existing range
• a back_insert_iterator allows you to append to an existing container

The semantics are different, picks whichever makes sense for the task at hand.

Answer 3

General iterators don't change the size or structure of a sequence. In particular random access iterators just access the elements at specific locations.

std::back_insert_iterator<Cont> is a trmplate modelling a concrete output iterator changing the sequence it refers to for each element written to it: it calls cont.push_back() for each element written. Since the iterator doesn't read the sequence it is modifying, adding elements works quite nicely.

Answer 4

They can, but it may not be safe to do so.

I suggest reading the excellent introduction to iterators from the Helsinki University.

If you have an iterator for a container (forward, bidirectional and random access are all fine), and you use it as an output iterator in an STL algorithm context, the output will be written into the container, but the iterator is never compared against the container's end(). If all the elements written fit, then this is fine, but if not, the output iterator will reach end(), and dereferencing it to write the next element will give undefined behaviour.

Things like back_insert_iterator are designed specifically for use as an output iterator, and will not cause UB in this way, because they can always insert more elements.

Answer 5

Regular iterators don't know anything about the container they are being used with except for the data type its holding. In order to add elements to a container, let's say a vector, one needs to know the number of elements in the vector.