|
|
|
|
| |
| 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, " "));
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;
}
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
