Table of Contents
+ Section [23.1.2], Table 69, of the C++ standard lists this + function for all of the associative containers (map, set, etc): +
+ a.insert(p,t); +
+ where 'p' is an iterator into the container 'a', and 't' is the
+ item to insert. The standard says that ât is
+ inserted as close as possible to the position just prior to
+ p.â (Library DR #233 addresses this topic,
+ referring to N1780.
+ Since version 4.2 GCC implements the resolution to DR 233, so
+ that insertions happen as close as possible to the hint. For
+ earlier releases the hint was only used as described below.
+
+ Here we'll describe how the hinting works in the libstdc++ + implementation, and what you need to do in order to take + advantage of it. (Insertions can change from logarithmic + complexity to amortized constant time, if the hint is properly + used.) Also, since the current implementation is based on the + SGI STL one, these points may hold true for other library + implementations also, since the HP/SGI code is used in a lot of + places. +
+ In the following text, the phrases greater + than and less than refer to the + results of the strict weak ordering imposed on the container by + its comparison object, which defaults to (basically) + â<â. Using those phrases is semantically sloppy, + but I didn't want to get bogged down in syntax. I assume that if + you are intelligent enough to use your own comparison objects, + you are also intelligent enough to assign âgreaterâ + and âlesserâ their new meanings in the next + paragraph. *grin* +
+ If the hint parameter ('p' above) is equivalent to:
+
+ begin(), then the item being inserted should
+ have a key less than all the other keys in the container.
+ The item will be inserted at the beginning of the container,
+ becoming the new entry at begin().
+
+ end(), then the item being inserted should have
+ a key greater than all the other keys in the container. The
+ item will be inserted at the end of the container, becoming
+ the new entry at end().
+
+ neither begin() nor end(), then:
+ Let h be the entry in the container pointed to
+ by hint, that is, h = *hint. Then
+ the item being inserted should have a key less than that of
+ h, and greater than that of the item preceding
+ h. The new item will be inserted between
+ h and h's predecessor.
+
+ For multimap and multiset, the
+ restrictions are slightly looser: âgreater thanâ
+ should be replaced by ânot less thanâand âless
+ thanâ should be replaced by ânot greater
+ than.â (Why not replace greater with
+ greater-than-or-equal-to? You probably could in your head, but
+ the mathematicians will tell you that it isn't the same thing.)
+
+ If the conditions are not met, then the hint is not used, and the
+ insertion proceeds as if you had called a.insert(t)
+ instead. (Note that GCC releases
+ prior to 3.0.2 had a bug in the case with hint ==
+ begin() for the map and set
+ classes. You should not use a hint argument in those releases.)
+
+ This behavior goes well with other containers'
+ insert() functions which take an iterator: if used,
+ the new item will be inserted before the iterator passed as an
+ argument, same as the other containers.
+
+ Note also that the hint in this + implementation is a one-shot. The older insertion-with-hint + routines check the immediately surrounding entries to ensure that + the new item would in fact belong there. If the hint does not + point to the correct place, then no further local searching is + done; the search begins from scratch in logarithmic time. +