C++ std::multimap

標準ライブラリのSTLコンテナ、キーの重複を許すマップstd::multimap（以下multimap）についてのメモです。

初期化子リストによる初期化

キーと値のペアをstd::pairや初期化子リスト{key, value}の初期化子リストとして与えることで初期化できます。キーは重複可能で、値の数だけペアを指定します。std::map<KeyT, std::vector<ValueT>>のように初期化リストによる値の一括指定はできません。

なお、初期化子リストを使用した場合、元の値はコピーあるいは通常の構築に使用されます。ムーブが必要な場合はstd::moveを使用します。

// C++17
#include <map>
#include <string>
#include <iostream>

using namespace std;

int main()
{
    // キーは文字列、値は整数のmultimapを作成する。
    multimap<wstring, int> map{
        {L"a", 0},
        {L"a", 1},
        {L"a", 2},
        {L"b", 0},
        {L"b", 0},
        {L"a", 3}};

    // 要素を列挙する。
    for (const auto& [key, value] : map)
    {
        wcout << key << L", " << value << endl;
    }
}

出力

a, 0
a, 1
a, 2
a, 3
b, 0
b, 0

• 上記では省略していますが、multimapはテンプレート引数としてキーの比較方法を受け取ります。サンプルコードで初期化子リストの最後に指定した{L"a", 3}が出力では途中に来ているように、追加したペアはキーを比較して並べ替えられます。
• {L"b", 0}、{L"b", 0}のような重複したペアもそれぞれ保持されます。
• イテレーターはキーと値のペアを指します。したがって、範囲ベースforの要素はstd::pair<キーの型, 値の型>です。これはauto&や構造化束縛でも受け取れます。

C++14以前では構造化束縛を使用できないため、auto&やstd::pairを明記します。

// C++14
#include <map>
#include <string>
#include <iostream>

using namespace std;

int main()
{
    multimap<wstring, int> map{
        {L"a", 0},
        {L"a", 1},
        {L"a", 2},
        {L"b", 0},
        {L"b", 0},
        {L"a", 3}};

    // const pair<wstring, int>& entry
    for (const auto& entry : map)
    {
        wcout << entry.first << L", " << entry.second << endl;
    }
}

要素数やキーに対応した値の個数の取得

要素数はmultimap.size、キーに対応した値の数はmultimap.countで取得できます。後者は存在しないキーを指定すると0を返します。また、キーがstd::wstringの場合はmultimap.count(nullptr)で実行時エラーが発生します（MSVC）。

#include <map>
#include <string>
#include <iostream>

using namespace std;

int main()
{
    multimap<wstring, int> map{
        {L"a", 0}, {L"a", 1}, {L"a", 2},
        {L"b", 0}, {L"b", 0}, {L"a", 3}};

    wcout << map.size() << endl; // 6

    wcout << map.count(L"a") << endl; // 4
    wcout << map.count(L"b") << endl; // 2
    wcout << map.count(L"")  << endl; // 0
    wcout << map.count(L"c") << endl; // 0
    // wcout << map.count(nullptr) << endl; // wstringの場合は実行時エラー
}

要素の追加

multimap.insert、multimap.emplace、multimap.emplace_hintにより要素を追加できます。どの関数でもキーと値のペアを指定します。

#include <map>      // multimap
#include <string>   // wstring
#include <iostream> // wcout, endl, etc.

using namespace std;

int main()
{
    wstring s1(L"s1");
    wstring s2(L"s2");
    wstring s3(L"s3");
    wstring s4(L"s4");
    wstring s5(L"s5");
    wstring s6(L"s6");
    wstring s7(L"s7");
    wstring s8(L"s8");
    wstring s9(L"s9");

    multimap<wstring, int> map;

    // 構築（キーは"s1"～"s9"を引数に初期化されます）
    map.insert({ L"s1", 1 });
    map.insert(pair(L"s2", 2));
    map.insert(make_pair(L"s3", 3));
    map.emplace(L"s4", 4);
    map.emplace(pair(L"s5", 5));
    map.emplace(make_pair(L"s6", 6));
    map.emplace_hint(map.cend(), L"s7", 7);
    map.emplace_hint(map.cend(), pair(L"s8", 8));
    map.emplace_hint(map.cend(), make_pair(L"s9", 9));

    wcout << L"\"" << s1 << s2 << s3 << s4 << s5 << s6 << s7 << s8 << s9 << L"\"" << endl;

    // コピー（キーはs1～s9のコピーで初期化されます）
    map.insert({ s1, 1 });
    map.insert(pair(s2, 2));
    map.insert(make_pair(s3, 3));
    map.emplace(s4, 4);
    map.emplace(pair(s5, 5));
    map.emplace(make_pair(s6, 6));
    map.emplace_hint(map.cend(), s7, 7);
    map.emplace_hint(map.cend(), pair(s8, 8));
    map.emplace_hint(map.cend(), make_pair(s9, 9));

    wcout << L"\"" << s1 << s2 << s3 << s4 << s5 << s6 << s7 << s8 << s9 << L"\"" << endl;

    // ムーブ（キーはs1～s9をムーブして初期化されます）
    map.insert({ move(s1), 1 });
    map.insert(pair(move(s2), 2));
    map.insert(make_pair(move(s3), 3));
    map.emplace(move(s4), 4);
    map.emplace(pair(move(s5), 5));
    map.emplace(make_pair(move(s6), 6));
    map.emplace_hint(map.cend(), move(s7), 7);
    map.emplace_hint(map.cend(), pair(move(s8), 8));
    map.emplace_hint(map.cend(), make_pair(move(s9), 9));

    wcout << L"\"" << s1 << s2 << s3 << s4 << s5 << s6 << s7 << s8 << s9 << L"\"" << endl;
    wcout << endl;

    for (const auto& [key, value] : map)
    {
        wcout << key << L", " << value << endl;
    }
}

出力

"s1s2s3s4s5s6s7s8s9"
"s1s2s3s4s5s6s7s8s9"
""

s1, 1
s1, 1
s1, 1
s2, 2
s2, 2
s2, 2
s3, 3
s3, 3
s3, 3
s4, 4
s4, 4
s4, 4
s5, 5
s5, 5
s5, 5
s6, 6
s6, 6
s6, 6
s7, 7
s7, 7
s7, 7
s8, 8
s8, 8
s8, 8
s9, 9
s9, 9
s9, 9

あるキーを持つ要素の列挙

multimap::equal_range、multimap::lower_bound＆multimap::upper_boundであるキーを持つ要素を列挙できます。前者は先頭・番兵イテレーターのペア（std::pair）を返し、後者はそれらを個別に取得します。イテレーターを直接使用して通常のfor文でも記述できますが、C++20からはstd::ranges::subrangeを使うことで範囲ベースforも使用できます。

lower_bound、upper_bound、subrangeを使用する例（C++20以降）

#include <map>
#include <string>
#include <iostream>
#include <ranges>

using namespace std;

int main()
{
    multimap<wstring, int> map{ {L"a", 0}, {L"a", 1}, {L"b", 0}, {L"b", 0} };

    for (const auto& [key, value] : ranges::subrange(map.lower_bound(L"a"), map.upper_bound(L"a")))
    {
        wcout << key << L", " << value << endl;
    }
}

equals_range、subrangeを使用する例（C++20以降）

#include <map>
#include <string>
#include <iostream>
#include <ranges>

using namespace std;

template <typename IterT>
constexpr ranges::subrange<IterT> make_subrange(std::pair<IterT, IterT> pair) noexcept
{
    return ranges::subrange(pair.first, pair.second);
}

int main()
{
    multimap<wstring, int> map{ {L"a", 0}, {L"a", 1}, {L"b", 0}, {L"b", 0} };

    for (const auto& [key, value] : make_subrange(map.equal_range(L"a")))
    {
        wcout << key << L", " << value << endl;
    }
}

出力

a, 0
a, 1

あるキーを持つ要素をまとめて削除

multimap.eraseを使います。

#include <map>
#include <string>

using namespace std;

int main()
{
    multimap<wstring, int> map{ {L"a", 0}, {L"a", 1}, {L"b", 0}, {L"b", 0} };

    map.erase(L"a"); // {L"b", 0}, {L"b", 0}だけ残る。
}

その他

multimapは他にも通常のSTLコンテナの持つメンバー関数などを持ちます。詳細はcppreferenceやcpprefjpの記事が詳しく書かれています。