C++ STL multimapでの検索方法について

Question

C++ STL multimapでの検索法

STL multimupにて検索する際下記1.2で速度の違いはありますでしょうか。

1. findとupper_boundを利用して該当データを全て調べる方法
2. equal_rangeで該当データを全て調べる方法

multimap<string, string> test;
string n = "b";
   
test.insert(pair<string, string>("a", "a"));
test.insert(pair<string, string>("a", "b"));
test.insert(pair<string, string>("b", "a"));
test.insert(pair<string, string>("b", "b"));
test.insert(pair<string, string>("c", "a"));
test.insert(pair<string, string>("c", "b"));

//find + upper_bound ver    
auto p = test.find(n);
do{
    cout <<p->first << " " << p->second << endl;
    p++;
}while(p != test.upper_bound(n));
   
// equal_range ver
auto p2 = test.equal_range(n);
auto pb = p2.first;
auto pe = p2.second;
do{
    cout << pb->first << " " << pb->second << endl; 
    pb++;
}while(pb != pe);

Answer 1

findは最も若い(先頭に近い)要素を指すとは限らなかったように思う。
そうであるならlower_bound/equal_rangeの代わりにはならない。

Comments

[alphya]

確かに、最初の要素を指すことは保証されません！

Answer 2

質問に直接関係しません。補足です。
連想配列を使うのであれば、std::unordered_multimap の使用を検討してみてください。
[C++] STLの型の使い分け - Qiita
また、このような問題は Effective STL で扱われているので、読んでみてもいいかもしれないです。

また、test.equal_­range(ke)はmake_­pair(test.lower_­bound(ke), test.upper_­bound(ke))と等価です。

Answer 3

同じだと思います。

std::multimap

参考にしたのは、上記のサイトです。
どちらも計算量は「size について対数時間」つまりO(log n)なので、変わらないと思います。