Joseph Gottman wrote in message <85q3hk$p5$1@bgtnsc02.worldnet.att.net>...

>I have a question about the hint insert (container.insert(object, iterator))
>on multisets and multimaps.  Could anyone tell my WHY this is not guaranteed
>to insert the object at the position pointed to by the iterator when the
>hint is correct (i.e. when inserting the object at the position in front of
>the iterator would preserve the order of the multiset or multimap)? It seems
>to me this would be a very useful ability, ...

People have noted this problem before (often in discussions about how to
implement priority queues which remember insertion order as a secondary
key).  I don't know if the committee ever discussed this.  I don't see it on
the library issues list,
http://anubis.dkuug.dk/jtc1/sc22/wg21/docs/lwg-active.html, so you might
want to submit a defect report.

For your hint guarantee to be useful, multimap/set would also need to be
stable (in the sense that insertions and deletes not change the relative
order of existing elements with duplicate keys).  I suspect that almost all
implementations are stable, but I'm not at all sure that the standard
requires them to be.

>    Guaranteeing correct behavior would be easy for implementers, ... it
>would give users much needed control over an important aspect of their
>multisets,

Yes.

>without hurting run-time performance one bit.

I don't believe these guarantees hurt performance significantly, but almost
any time you take away some implementation freedom you risk hurting
performance by "one bit" or more.  For instance, I can imagine an
implementation that would take advantage of the existing freedom to
sometimes find a cheaper way to maintain the tree's balance.




[ 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              ]

I have a question about the hint insert (container.insert(object, iterator))
on multisets and multimaps.  Could anyone tell my WHY this is not guaranteed
to insert the object at the position pointed to by the iterator when the
hint is correct (i.e. when inserting the object at the position in front of
the iterator would preserve the order of the multiset or multimap)? It seems
to me this would be a very useful ability, especially in conjunction with
the lower_bound() and upper_bound() methods.

         multiset<X> container;
         ....
         container.insert(foo, container.lower_bound(foo));// Insert in
front of all equivalent elements.
         container.insert(bar, container.upper_bound(bar)); // Insert behind
all equivalent elements.

    Guaranteeing correct behavior would be easy for implementers, since this
is the obvious way to ensure that the hint insert has the correct run-time
complexity.  It removes an unnecessary difference between multimap and
multiset and all other STL containers, since all the other STL containers
will insert in front of the iterator if they can (even set and map).  And it
would give users much needed control over an important aspect of their
multisets, without hurting run-time performance one bit.


---
[ 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              ]