When inserting an element into an associative container with equivilent
keys, the insert with hint method doesn't seem to provide the user a way to
be sure the operation will occur in amortized constant time.

Consider the following code:

typedef multimap<int, char> M;
M m;

M::iterator itA = m.insert(make_pair(1, 'A'));
M::iterator itB = m.insert(itA, make_pair(1, 'B'));

Does inserting B take amortized constant time?  The ISO C++ spec says
"logarithmic in general, but amortized constant if t is inserted right after
p." (23.1.2,7).  The problem is that I don't know where B gets inserted.  It
could be inserted either before or after A.  (At least I couldn't find
anything that specifies what an order of elements with equivilent keys.)
Since I have no guarantee that B will be inserted A (i.e. t will be inserted
right after p), I have no guarantee of amortized constant time.

Another question along similiar lines: After inserting B, does itA == itB?
The ISO C++ spec says "always returns the iterator pointing to the element
with key equivalent to the key of t." (23.1.2,7).  The use of the definate
article "the" implies the intent is to uniquely identify the return value;
however, that specification fails to do so.  For the hinted insertion, both
A and B fit the description, leaving an implemention free in this case to
return an iterator to either A or B.  So perhaps, itA == itB, or perhaps
not: a program can't count on it either way.
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]