Unless I'm misreading the source (possible) in bits/stl_tree.h in
insert_unique(iterator, const value_type&) and insert_equal(iterator, const
value_type&), it looks like we use the passed hint by trying to insert BEFORE
it, rather than after it. I'd imagine this bug is present in all versions of
libstdc++-v3.
This doesn't cause incorrect behaviour, just log(n) inserts rather than constant
time ones. In theory this shouldn't be too hard to fix, but playing with the
tree code may require being careful. I'm submitting a bug report just so it
doesn't get forgotten about :)
--
Summary: set, multiset, map, multimap misuse hint on insert
Product: gcc
Version: 4.0.0
Status: UNCONFIRMED
Severity: minor
Priority: P2
Component: libstdc++
AssignedTo: unassigned at gcc dot gnu dot org
ReportedBy: chris at bubblescope dot net
CC: caj at cs dot york dot ac dot uk,gcc-bugs at gcc dot gnu
dot org
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=19433
