insert_iterator<Container>



Categories: iterators adaptors	Component type: type

Description

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 x immediately 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.

Example

Insert a range of elements into a list.

list<int> L;
L.push_front(3);
insert_iterator<list<int> > ii(L
L.begin());
*ii++ = 0;
*ii++ = 1;
*ii++ = 2;
copy(L.begin()
L.end()
ostream_iterator<int>(cout
" "));
// The values that are printed are 0 1 2 3.

Merge two sorted lists inserting the resulting range into a set. Note that a set never contains duplicate elements.

int main()
{
  const int N = 6;

  int A1[N] = {1
3
5
7
9
11};
  int A2[N] = {1
2
3
4
5
6};
  set<int> result;

  merge(A1
A1 + N
A2
A2 + N

        inserter(result
result.begin()));

  copy(result.begin()
result.end()
ostream_iterator<int>(cout
" "));
  cout << endl;

  // The output is "1 2 3 4 5 6 7 9 11".
}

Definition

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

Template parameters

Parameter	Description	Default
`Container`	The type of Container into which values will be inserted.

Model of

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

Type requirements

The template parameter Container is a model of Container.
Container is variable-sized as described in the Container requirements.
Container has a two-argument insert member function. Specifically if c is an object of type Container p is an object of type Container::iterator and v is an object of type Container::value_type then c.insert(p v) must be a valid expression.

Public base classes

None.

Members

Member	Where defined	Description
`insert_iterator(Container& Container::iterator)`	`insert_iterator`	See below.
`insert_iterator(const insert_iterator&)`	Trivial Iterator	The copy constructor
`insert_iterator& operator=(const insert_iterator&)`	Trivial Iterator	The assignment operator
`insert_iterator& operator*()`	Output Iterator	Used to implement the output iterator expression `*i = x`. [2]
`insert_iterator& operator=(const Container::value_type&)`	Output Iterator	Used to implement the output iterator expression `*i = x`. [2]
`insert_iterator& operator++()`	Output Iterator	Preincrement.
`insert_iterator& operator++(int)`	Output Iterator	Postincrement.
`output_iterator_tag iterator_category(const insert_iterator&)`	iterator tags	Returns the iterator's category. This is a global function not a member.
template<class Container class Iter) insert_iterator<Container> inserter(Container& C Iter i);	`insert_iterator`	See below.

New members

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

Member	Description
`insert_iterator(Container& C Container::iterator i)`	Constructs an `insert_iterator` that inserts objects in `C`. If `Container` is a Sequence then each object will be inserted immediately before the element pointed to by `i`. If `C` is a Sorted Associative Container then the first insertion will use `i` as a hint for beginning the search. The iterator `i` must be a dereferenceable or past-the-end iterator in `C`.
template<class Container class Iter) insert_iterator<Container> inserter(Container& C Iter i);	Equivalent to `insert_iterator<Container>(C i)`. [2] This is a global function not a member function.

Notes

[1] Note the difference between assignment through a Container::iterator and assignment through an insert_iterator<Container>. If i is a valid Sequence::iterator then it points to some particular element in the container; the expression *i = t replaces that element with t and does not change the total number of elements in the container. If ii is a valid insert_iterator<container> however then the expression *ii = t is equivalent for some container c and some valid container::iterator j to the expression c.insert(j t). That is it does not overwrite any of c's elements and it does change c's size.

[2] Note how assignment through an 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 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 insert_iterator need not be declared explicitly. One easy way to reverse a range and insert it into a Sequence S for example is reverse_copy(first last inserter(S S.begin())).