**Description**

**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 *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.