c++のmultimapで特定のキーのi番目の要素を取得する方法を探しています。

Question

c++のmultimapで特定のキーのi番目の要素を取得する方法を探しています。
例えば以下のようなプログラム文があります。

#include <stdio.h>
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
#include <functional>
#include <map>

using namespace std;

int main() {
int i;

multimap<string, int> mpp;

for (i = 0; i < 10; i++) {
if (i % 2 == 0) {
mpp.insert(pair<string, int>("A", i));
}
else {
mpp.insert(pair<string, int>("B", i));
}
}

std::multimap<std::string, int>::iterator p;

for (p = mpp.begin(); p != mpp.end(); p++) {
cout << p->first << " " << p->second << endl;
}

getchar();
getchar();
return 0;
}

実行結果は
A 0
A 2
A 4
A 6
A 8
B 1
B 3
B 5
B 7
B 9

となりますが、キー「B」の要素「5」だけを表示する方法はありますでしょうか。
この場合、「5」を検索したりするのではなく、キー「B」の2番目の要素を指し示す
方法を知りたいです。
よろしくお願いいたします。

Answer 1

こんにちは。

ちょっと面倒ですが、std::multimap::lower_boundで指定キーの「先頭」イテレータを得て、必要回数インクリメント（①）すれば基本はOKです。
注意点として、std::multimap::lower_boundは指定キーがない場合でも指定キーを挿入するべき位置を返却するので、①が指定キーを持つのか確認する必要があります。

std::multimapはstd::unordered_multimapではないので順序付けはなされるようですが、std::pair::secondも使ってソートが必要ならばstd::multisetを使った方が良いと思います。std::tieを使えば比較関数を極簡単に書けます。

Comments

[mattn]

multimap は順序付けされるのはキーだけという認識だったのですが。

[Chironian]

その通りですね。

[mattn]

キーや値での順保障はないですが、挿入順は保証されるようでした。この意味からするとキー内では挿入順になるので Chironian さんので問題なさそうでした。(C++11から)すみません。

http://en.cppreference.com/w/cpp/container/multimap

[tada_tadaa]

回答ありがとうございます。
Chironian様のおっしゃるようにプログラムを作ってみました。
間違いもあるかもしれませんが、一応動いていると思います。

#include <stdio.h>
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
#include <functional>
#include <map>

using namespace std;

int main() {
int i;

multimap<string, int> mpp;

for (i = 0; i < 10; i++) {
if (i % 2 == 0) {
mpp.insert(pair<string, int>("A", i));
}
else {
mpp.insert(pair<string, int>("B", i));
}
}

multimap<std::string, int>::iterator p;

for (p = mpp.begin(); p != mpp.end(); p++) {
cout << p->first << " " << p->second << endl;
}

// 「B」キーがあるかどうか調べる
int cnt_a = mpp.count("B");

if (cnt_a == 0) {
cout << "キーが存在しません" << endl;
}
else if( cnt_a > 0 ){
cout << "キーは存在します" << endl;
cout << cnt_a << endl;
p = mpp.lower_bound("B");
p++;
cout << "p->" << p->second << endl;
p++;
cout << "p->" << p->second << endl;

}

getchar();
getchar();
return 0;
}

実行結果は
A 0
A 2
A 4
A 6
A 8
B 1
B 3
B 5
B 7
B 9
キーは存在します
5
p->3
p->5

になり、うまくキー「B」の2番目の要素（ゼロから数えて）を得ることができました。
それで、ついでに上記プログラムのmultiset版も作ってみようかと思ったのですが、よく分からないで
います。
multimapの文字列をmultisetにしただけなのですが、エラーがでてコンパイルできません。

int i;

//multimap<string, int> mpp;
multiset <string, int> mpp;

for (i = 0; i < 10; i++) {
if (i % 2 == 0) {
mpp.insert(pair<string, int>("A", i));
}
else {
mpp.insert(pair<string, int>("B", i));
}
}

そもそもmultisetは"文字をキーにして、"要素を格納できるものなのでしょうか？
度々質問してすみません。

[Chironian]

std::multisetは、要素全てをキーにして格納します。標準の型でない場合、コンパイラは大小比較方法が分からないので、大小比較関数を定義して渡してあげる必要があります。http://vivi.dyndns.org/tech/cpp/multiset.html

この比較関数って意外に面倒です。firstキー不一致の時はfirstキーで大小比較し、firstキーが一致しているはsecondキーで比較するため、3分岐します。
std::tieはその辺よしなにしてくれるようです。http://d.hatena.ne.jp/yohhoy/20120218/p1

Answer 2

multimap は ordered map ではないので i 番目は分かりません。

Comments

[tada_tadaa]

回答ありがとうございます。
Chironian様がうまい方法を教えてくださいました。

ありがとうございました。

[mattn]

うまい方法といいますか、僕の知識が C++11 より前で止まっていたので multimap は挿入順では無いと思っていました。もちろん C++11 未満では期待しない動作になるかもしれないのでご使用の際はお気をつけて。

[tada_tadaa]

＞C++11 未満では期待しない動作になるかもしれないのでご使用の際はお気をつけて。

了解しました。