Standard Template Library Programmer's Guide

Categories: iterators, adaptors

Component type: type

Back_insert_iterator is an iterator adaptor that functions as an Output Iterator: assignment through a back_insert_iterator inserts an object after the last element of a Back Insertion Sequence. [1]

list L;

L.push_front(3);

back_insert_iterator > ii(L);

*ii++ = 0;

*ii++ = 1;

*ii++ = 2;

copy (L.begin(), L.end(), ostream_iterator(cout, " "));

// The values that are printed are 3 0 1 2

Defined in the standard header iterator, and in the nonstandard backward-compatibility header iterator.h.

Output Iterator. An insert iterator's set of value types (as defined in the Output Iterator requirements) consists of a single type: BackInsertionSequence::value_type .

The template parameter BackInsertionSequence must be a Back Insertion Sequence.

None.

These members are not defined in the Output Iterator requirements, but are specific to back_insert_iterator .

[1] Note the difference between assignment through a BackInsertionSequence::iterator and assignment through a back_insert_iterator . If i is a valid BackInsertionSequence::iterator , then it points to some particular element in the back insertion sequence; the expression *i = t replaces that element with t , and does not change the total number of elements in the back insertion sequence. If ii is a valid back_insert_iterator , however, then the expression *ii = t is equivalent, to the expression seq.push_back(t) . That is, it does not overwrite any of seq 's elements and it does change seq 's size.

[2] Note how assignment through a back_insert_iterator is implemented. In general, unary operator* must be defined so that it returns a proxy object, where the proxy object defines operator= to perform the insert operation. In this case, for the sake of simplicity, the proxy object is the back_insert_iterator itself. That is, *i simply returns i , and *i = t is equivalent to i = t . You should not, however, rely on this behavior. It is an implementation detail, and it is not guaranteed to remain the same in future versions.

[3] This function exists solely for the sake of convenience: since it is a non-member function, the template parameters may be inferred and the type of the back_insert_iterator need not be declared explicitly. One easy way to reverse a range and insert it at the end of a Back Insertion Sequence S , for example, is reverse_copy(first, last, back_inserter(S)) .

insert_iterator, front_insert_iterator, Output Iterator, Back Insertion Sequence, Sequence, Iterator overview

Categories: iterators, adaptors

Component type: type

Insert_iterator is an iterator adaptor that functions as an Output Iterator: assignment through an insert_iterator inserts an object into a Container. Specifically, if ii is an insert_iterator , then ii keeps track of a Container c and an insertion point p ; the expression *ii = x performs the insertion c.insert(p, x) . [1]

There are two different Container concepts that define this expression: Sequence, and Sorted Associative Container. Both concepts define insertion into a container by means of c.insert(p, x) , but the semantics of this expression is very different in the two cases.

For a Sequence S , the expression S.insert(p, x) means to insert the value ximmediately before the iterator p . That is, the two-argument version of insert allows you to control the location at which the new element will be inserted. For a Sorted Associative Container, however, no such control is possible: the elements in a Sorted Associative Container always appear in ascending order of keys. Sorted Associative Containers define the two-argument version of insert as an optimization. The first argument is only a hint: it points to the location where the search will begin.

If you assign through an insert_iterator several times, then you will be inserting several elements into the underlying container. In the case of a Sequence, they will appear at a particular location in the underlying sequence, in the order in which they were inserted: one of the arguments to insert_iterator 's constructor is an iterator p , and the new range will be inserted immediately before p .

In the case of a Sorted Associative Container, however, the iterator in the insert_iterator 's constructor is almost irrelevant. The new elements will not necessarily form a contiguous range; they will appear in the appropriate location in the container, in ascending order by key. The order in which they are inserted only affects efficiency: inserting an already-sorted range into a Sorted Associative Container is an O(N ) operation.