stlab.adobe.com Adobe Systems Incorporated

insert_iterator

iterators.gif
type.gif
adaptors.gif
Categories : iterators, adaptors Component type: type

Description

Insert_iterator is an iterator adaptor that functions as an OutputIterator : 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 SortedAssociativeContainer. 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 SortedAssociativeContainer, however, no such control is possible : the elements in a SortedAssociativeContainer always appear in ascending order of keys. SortedAssociativeContainer 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 SortedAssociativeContainer, 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 SortedAssociativeContainer 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

OutputIterator. An insert iterator's set of value types (as defined in the OutputIterator 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 The copy constructor
insert_iterator& operator=(const insert_iterator&) trivial The assignment operator
insert_iterator& operator*() OutputIterator Used to implement the OutputIterator expression *i = x. [2]
insert_iterator& operator=(const Container value_type&) OutputIterator Used to implement the OutputIterator expression *i = x. [2]
insert_iterator& operator++() OutputIterator Preincrement.
insert_iterator& operator++(int) OutputIterator 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 OutputIterator 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 SortedAssociativeContainer, 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())).

See also

front_insert_iterator, back_insert_iterator, OutputIterator, Sequence, Iterators

Copyright © 2006-2007 Adobe Systems Incorporated.

Use of this website signifies your agreement to the Terms of Use and Online Privacy Policy.

Search powered by Google