Velocity Reviews

Velocity Reviews (http://www.velocityreviews.com/forums/index.php)
-   C++ (http://www.velocityreviews.com/forums/f39-c.html)
-   -   is STL multimap "find" order stable? (http://www.velocityreviews.com/forums/t446644-is-stl-multimap-find-order-stable.html)

salem.ganzhorn@gmail.com 06-24-2005 08:58 PM

is STL multimap "find" order stable?
 
#include <map>
#include <iostream>

using namespace std;

int main(
int argc,
const char * argv[]
)
{
if( 4 != argc ) {
cerr << "usage: " << endl
<< argv[0] << " index value1 value2" << endl;
exit(1);
}
int index = atoi(argv[1]);
int value1 = atoi(argv[2]);
int value2 = atoi(argv[3]);
multimap<int,int> mm;
mm.insert( pair<int,int>(index,value1) );
mm.insert( pair<int,int>(index,value2) );
cout << "Am I guaranteed that " << mm.find(index)->second << " == "
<< value1 << "?" << endl;
return 0;
}

I have read the STL docs and I did not see this explicitly stated.


James Daughtry 06-24-2005 09:16 PM

Re: is STL multimap "find" order stable?
 
There's no guarantee about the order of identical keys in a multimap.


salem.ganzhorn@gmail.com 06-24-2005 09:46 PM

Re: is STL multimap "find" order stable?
 
Arg... that is very unfortunate. I might actually have to write some
code :(
Thanks for the info.


Howard Hinnant 06-24-2005 10:00 PM

Re: is STL multimap "find" order stable?
 
In article <1119649603.994500.71970@g44g2000cwa.googlegroups. com>,
salem.ganzhorn@gmail.com wrote:

> Arg... that is very unfortunate. I might actually have to write some
> code :(
> Thanks for the info.


Fwiw, I'm trying to change this, at least partly:

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

If accepted, you would have to use lower_bound instead of find, but
otherwise you would be good to go. But as James said, as it stands
today you're just out of luck as far as the standard goes.

However the above paper contains a survey of several libraries (actually
all of them (current versions) that I'm aware of), and they all
implement "insert without hint" as if they were told to "insert at
upper_bound". So from a practical standpoint you might get away with
use of lower_bound instead of find today.

-Howard

salem.ganzhorn@gmail.com 06-25-2005 03:05 AM

Re: is STL multimap "find" order stable?
 
Howard, thanks so much!
This paper does all the hard work. It is sufficient for me to know that
current implementations are stable when inserting without hints. I will
just add additional unit tests to be sure it doesn't bite me when
someone changes the implementation.
Best wishes,
Salem



All times are GMT. The time now is 10:42 AM.

Powered by vBulletin®. Copyright ©2000 - 2014, vBulletin Solutions, Inc.
SEO by vBSEO ©2010, Crawlability, Inc.