473,322 Members | 1,347 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,322 software developers and data experts.

Is std::multimap "stable" ?

Hello.

[lib.associative.reqmts] 9 says:

'' The fundamental property of iterators of associative containers is
that they iterate through the containers in the non-descending order of
keys where non-descending is defined by the comparison that was used to
construct them. ''

Does it mean that if I insert values into a multimap with equal keys, I
am guaranteed to receive them back with find() and equal_range() in the
same order I inserted them?

Thanks,
melfar

Apr 17 '06 #1
1 3771
In article <11*********************@t31g2000cwb.googlegroups. com>,
"me****@gmail.com" <me****@gmail.com> wrote:
Hello.

[lib.associative.reqmts] 9 says:

'' The fundamental property of iterators of associative containers is
that they iterate through the containers in the non-descending order of
keys where non-descending is defined by the comparison that was used to
construct them. ''

Does it mean that if I insert values into a multimap with equal keys, I
am guaranteed to receive them back with find() and equal_range() in the
same order I inserted them?

Thanks,
melfar


No, not according to the standard. However there are several issues of
interest.

First, see:

http://www.open-std.org/jtc1/sc22/wg...ctive.html#371

This LWG issue is in the working draft for C++0X (voted in just two
weeks ago). It states that once your equal keys are in the multimap,
they won't change order as the multimap rebalances due to further
inserts and erases. But it doesn't guarantee that the keys are placed
in any particular order related to the order in which they were inserted.

However, also see:

http://www.open-std.org/jtc1/sc22/wg...ctive.html#233

and a related paper:

http://www.open-std.org/jtc1/sc22/wg...005/n1780.html

If N1780 is accepted as the proposed resolution to 233, then your equal
keys will be in the order you inserted them, or as otherwise directed by
the optional "hint" parameter. That still doesn't mean that find()
would find the keys in that order, but it does mean that equal_range,
lower/upper_bound would find them in the expected order.

N1780 is still controversial on the committee, but does have support.
N1780 also points out that all existing implementations currently
interpret "insert without hint" as "insert at upper bound" (equal keys
will be in the order you inserted them). So there is also a second
answer to your original question:

Yes, all implementations will keep your inserted equal keys in the order
you inserted them. Use lower_bound or equal_range, not find, to find
them in that order.

Sorry the answer is so complicated.

-Howard
Apr 17 '06 #2

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

205
by: Jeremy Siek | last post by:
CALL FOR PAPERS/PARTICIPATION C++, Boost, and the Future of C++ Libraries Workshop at OOPSLA October 24-28, 2004 Vancouver, British Columbia, Canada http://tinyurl.com/4n5pf Submissions
235
by: napi | last post by:
I think you would agree with me that a C compiler that directly produces Java Byte Code to be run on any JVM is something that is missing to software programmers so far. With such a tool one could...
4
by: salem.ganzhorn | last post by:
#include <map> #include <iostream> using namespace std; int main( int argc, const char * argv ) {
48
by: Tony | last post by:
How much bloat does the STL produce? Is it a good design wrt code bloat? Do implementations vary much? Tony
22
by: nospam_news | last post by:
I currently get asked about my usage of "auto". What is it for? The keyword is clearly superflous here. In contrast to the huge majority of C/C++ developers I write definitions very explicitly...
0
by: DolphinDB | last post by:
Tired of spending countless mintues downsampling your data? Look no further! In this article, you’ll learn how to efficiently downsample 6.48 billion high-frequency records to 61 million...
0
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
0
by: jfyes | last post by:
As a hardware engineer, after seeing that CEIWEI recently released a new tool for Modbus RTU Over TCP/UDP filtering and monitoring, I actively went to its official website to take a look. It turned...
1
by: CloudSolutions | last post by:
Introduction: For many beginners and individual users, requiring a credit card and email registration may pose a barrier when starting to use cloud servers. However, some cloud server providers now...
1
by: Defcon1945 | last post by:
I'm trying to learn Python using Pycharm but import shutil doesn't work
1
by: Shællîpôpï 09 | last post by:
If u are using a keypad phone, how do u turn on JavaScript, to access features like WhatsApp, Facebook, Instagram....
0
by: af34tf | last post by:
Hi Guys, I have a domain whose name is BytesLimited.com, and I want to sell it. Does anyone know about platforms that allow me to list my domain in auction for free. Thank you
0
by: Faith0G | last post by:
I am starting a new it consulting business and it's been a while since I setup a new website. Is wordpress still the best web based software for hosting a 5 page website? The webpages will be...
0
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 3 Apr 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome former...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.