sal wrote:
> The std does not seem to offer any gurantees wrt to the ordering of
> elements with equal keys in a multimap. Is it reasonable (or foolish)
> to assume that most implementation will return the equal keyed
elements
> in the order they were inserted when equal_range is used?

The order is not prescribed as far as I can tell. However, if you
need a guarantee, you might be better off using an 'std::map' of an
appropriate container, e.g. a 'std::queue<T>' or 'std::vector<T>'.
Of course, the details of how elements are inserted, accessed, or
extracted would be slightly different.
--
<mailto:dietmar_kuehl@yahoo.com> <http://www.dietmar-kuehl.de/>
<http://www.contendix.com> - Software Development & Consulting

---
[ 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://www.jamesd.demon.co.uk/csc/faq.html                       ]

The std does not seem to offer any gurantees wrt to the ordering of
elements with equal keys in a multimap. Is it reasonable (or foolish)
to assume that most implementation will return the equal keyed elements
in the order they were inserted when equal_range is used?

It would be nice if the std was explicit one way or the other (I am not
sure I have the latest edition, though, so maybe this has been
addressed).

---
[ 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://www.jamesd.demon.co.uk/csc/faq.html                       ]

"sal" <smangano@siac.com> wrote in message
news:1108491169.427308.255370@l41g2000cwc.googlegroups.com...

> The std does not seem to offer any gurantees wrt to the ordering of
> elements with equal keys in a multimap. Is it reasonable (or foolish)
> to assume that most implementation will return the equal keyed elements
> in the order they were inserted when equal_range is used?
>
> It would be nice if the std was explicit one way or the other (I am not
> sure I have the latest edition, though, so maybe this has been
> addressed).

The C++ Standard offers no such guarantees about order. You can
insert with a hint to reliably add an element at one end or other
of the range of equivalent items, but even there practice seems
to vary about which side of the hint element should be preferred.
I know we've discussed spelling out the hint behavior better, but
I don't recall whether any of this made it into the 2003 revision.

Put simply, if you use the iterator returned by upper_bound as a hint,
the insertion should reliably go at the end of the sequence of elements
already present with equivalent ordering.

P.J. Plauger
Dinkumware, Ltd.
http://www.dinkumware.com


---
[ 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://www.jamesd.demon.co.uk/csc/faq.html                       ]

sal wrote:
> The std does not seem to offer any gurantees wrt to the ordering of
> elements with equal keys in a multimap. Is it reasonable (or foolish)
> to assume that most implementation will return the equal keyed elements
> in the order they were inserted when equal_range is used?
>
> It would be nice if the std was explicit one way or the other (I am not
> sure I have the latest edition, though, so maybe this has been
> addressed).

I seriously suspect that this doesn't hold. Internally multimaps are
usually represented as balanced trees, and if you put lots of values
into a balanced tree the you are likely to find values you put in early
near the top and values later near the bottom. However the tree will
normally be returned left-to-right.

As a rule, if the C++ standard doesn't give you a guarantee, you don't
have it :)

Chris

---
[ 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://www.jamesd.demon.co.uk/csc/faq.html                       ]

sal schrieb:

>The std does not seem to offer any gurantees wrt to the ordering of
>elements with equal keys in a multimap. Is it reasonable (or foolish)
>to assume that most implementation will return the equal keyed elements
>in the order they were inserted when equal_range is used?
>
>It would be nice if the std was explicit one way or the other (I am not
>sure I have the latest edition, though, so maybe this has been
>addressed)
>
This issue is currently investigated, see

http://www.open-std.org/jtc1/sc22/wg21/docs/lwg-active.html#371

Greetings from Bremen,

Daniel Kr=FCgler

---
[ 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://www.jamesd.demon.co.uk/csc/faq.html                       ]