SGI

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

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())).

See also

front_insert_iterator, back_insert_iterator, Output Iterator, Sequence, Iterator overview
[Silicon Surf] [STL Home]
Copyright © 1999 Silicon Graphics, Inc. All Rights Reserved. TrademarkInformation