C++ STLのmap・multimapを降順で扱う方法

一般に、C++のmapおよびmultimapは、デフォルトではキーを昇順で格納します。しかし、第3テンプレート引数として比較用の関数オブジェクトstd::greaterを指定することで、要素を降順で格納することも簡単にできます。

mapを降順で使用する

使用する主なメンバ関数

• m.find() – 指定したキーを持つ要素へのイテレータを返します。見つからない場合はend()イテレータを返します。

• m.erase() – マップから指定したキーの要素を削除します。

• m.equal_range() – イテレータのペア（pair）を返します。このペアは、指定したキーと等しいキーを持つすべての要素を含む範囲の境界を表します。

• m.insert() – マップコンテナに要素を挿入します。

• m.size() – マップコンテナ内の要素数を返します。

• m.count() – 指定したキーと一致する要素の個数を返します。

サンプルコード

#include <iostream>
#include <map>
#include <string>
using namespace std;
int main () {
    map<char, int, greater<int>> m;
    map<char, int>::iterator it;
    m.insert(pair<char, int>('a', 10));
    m.insert(pair<char, int>('b', 20));
    m.insert(pair<char, int>('c', 30));
    m.insert(pair<char, int>('d', 40));
    cout << "Size of the map: " << m.size() << endl;
    cout << "map contains:\n";
    for (it = m.begin(); it != m.end(); ++it)
        cout << (*it).first << " => " << (*it).second << '\n';
    for (char c = 'a'; c <= 'd'; c++) {
        cout << "There are " << m.count(c) << " element(s) with key " << c << ":";
        map<char, int>::iterator it;
        for (it = m.equal_range(c).first; it != m.equal_range(c).second; ++it)
            cout << ' ' << (*it).second;
        cout << endl;
    }
    if (m.count('a'))
        cout << "The key a is present\n";
    else
        cout << "The key a is not present\n";
    if (m.count('f'))
        cout << "The key f is present\n";
    else
        cout << "The key f is not present\n";
    it = m.find('b');
    m.erase(it);
    cout << "Size of the map: " << m.size() << endl;
    cout << "map contains:\n";
    for (it = m.begin(); it != m.end(); ++it)
        cout << (*it).first << " => " << (*it).second << '\n';
    return 0;
}

実行結果

Size of the map: 4
map contains:
d => 40
c => 30
b => 20
a => 10
There are 1 element(s) with key a: 10
There are 1 element(s) with key b: 20
There are 1 element(s) with key c: 30
There are 1 element(s) with key d: 40
The key a is present
The key f is not present
Size of the map: 3
map contains:
d => 40
c => 30
a => 10

実行結果を見ると、要素がキー「d」から「a」へと降順で並んでいることがわかります。これはmap<char, int, greater<int>>のように、第3テンプレート引数にgreaterを渡しているためです。

multimapを降順で使用する

multimapは同じキーを持つ複数の要素を格納できる点がmapとの大きな違いですが、降順ソートの方法はまったく同じです。

使用する主なメンバ関数

• mm.find() – 指定したキーを持つ要素へのイテレータを返します。見つからない場合はend()イテレータを返します。

• mm.erase() – マルチマップから指定したキーの要素を削除します。

• mm.equal_range() – イテレータのペア（pair）を返します。このペアは、指定したキーと等しいキーを持つすべての要素を含む範囲の境界を表します。

• mm.insert() – マルチマップコンテナに要素を挿入します。

• mm.size() – マルチマップコンテナ内の要素数を返します。

サンプルコード

#include <iostream>
#include <map>
#include <string>
using namespace std;
int main () {
    multimap<char, int, greater<char>> mm;
    multimap<char, int>::iterator it;
    mm.insert(pair<char, int>('a', 10));
    mm.insert(pair<char, int>('b', 20));
    mm.insert(pair<char, int>('a', 30));
    mm.insert(pair<char, int>('b', 40));
    cout << "Size of the multimap: " << mm.size() << endl;
    cout << "multimap contains:\n";
    for (it = mm.begin(); it != mm.end(); ++it)
        cout << (*it).first << " => " << (*it).second << '\n';
    for (char c = 'a'; c <= 'd'; c++) {
        cout << "There are " << mm.count(c) << " elements with key " << c << ":";
        map<char, int>::iterator it;
        for (it = mm.equal_range(c).first; it != mm.equal_range(c).second; ++it)
            cout << ' ' << (*it).second;
        cout << endl;
    }
    if (mm.count('a'))
        cout << "The key a is present\n";
    else
        cout << "The key a is not present\n";
    if (mm.count('f'))
        cout << "The key f is present\n";
    else
        cout << "The key f is not present\n";
    it = mm.find('b');
    mm.erase(it);
    cout << "Size of the multimap: " << mm.size() << endl;
    cout << "multimap contains:\n";
    for (it = mm.begin(); it != mm.end(); ++it)
        cout << (*it).first << " => " << (*it).second << '\n';
    return 0;
}

実行結果

Size of the multimap: 4
multimap contains:
b => 20
b => 40
a => 10
a => 30
There are 2 elements with key a: 10 30
There are 2 elements with key b: 20 40
There are 0 elements with key c:
There are 0 elements with key d:
The key a is present
The key f is not present
Size of the multimap: 3
multimap contains:
b => 40
a => 10
a => 30

まとめ

mapやmultimapを降順で使いたい場合は、テンプレートの第3引数にstd::greater<Key>を指定するだけです。デフォルトのstd::less（昇順）と入れ替えることで、ソート順序を自由に制御できます。また、find()・erase()・equal_range()・count()といったメンバ関数を組み合わせれば、要素の検索・削除・範囲取得も柔軟に行えます。