map と multimap | Programming Place Plus　C++編【標準ライブラリ】　第９章

map と multimap 🔗

map および multimapは、STLコンテナの一種で、ソートされた集合を提供します。map は、同じキーを持ったデータが重複することを許さず、multimap は許すという違いがあります。キーというのは、ソートの条件に使用する値のことを指しています。

以降、map と multimap のいずれにも当てはまる事項は、map/multimap と記述します。

map/multimap のいずれも、使用するには、<map> という名前の標準ヘッダをインクルードする必要があります。

set/multiset（第８章）との違いは、要素が、キーと値のペアで管理される点です。要素は、キーに対する何らかの基準に従ってソートされます。

また、map の場合は、キーを配列の添字であるようにみなして、m[key] という形で要素をアクセスできる点も特徴的です。キーは整数である必要はありません。このように任意の型で表現される値を使って、要素へアクセスできるデータ構造を連想配列と呼びます。

map/multimap は、内部的には木構造（特に、赤黒木のような平衡木）になっているのが一般的です。

map/multimap は、要素がソート済みであることを利用して、検索を効率良く行えるという特性があります。そのため、要素の検索を行う機会が多い場合に利用します。

map/multimap に格納された要素が持つキーを変更することは、原則としてできません。勝手にキーが変更されてしまうと、ソート済みの状態を保つことができません。

正確に言えば、要素を指すイテレータを取得することもできるし、格納した要素へのポインタや参照をコンテナの外にも持っていれば、それらを経由して、キーを書き換えることはできてしまいます。しかし、そのようにして、ソート結果が変わってしまうような変更をした場合の動作は保証できません。

map/multimap はそれぞれ、次のように定義されています。

namespace std {
    template <typename Key,
              typename T,
              typename Compare = less<T>,
              typename Allocator = allocator<pair<const Key, T> > >
    class map {
    };
}

namespace std {
    template <typename Key,
              typename T,
              typename Compare = less<T>,
              typename Allocator = allocator<pair<const Key, T> > >
    class multimap {
    };
}

map/multimap はクラステンプレート（【言語解説】第２０章）なので、使用時にはテンプレート実引数の指定が必要です。テンプレート仮引数 Key は、要素のキーの型、テンプレート仮引数 T は、要素の値の型です。たとえば、std::string型のキーを持ち、int型の値を扱う map は、以下のようになります。

std::map<std::string, int> siMap;

キーを文字列にする場合に、const char* のような型を使うと、キーの比較を行う際に、ポインタの比較になることに注意してください。多くの場合、メモリアドレスの一致ではなく、文字列を構成する文字の一致を見るべきですから、この動作は適切で無い可能性があります。

３つ目のテンプレート仮引数 Compare は、要素をソートする基準を定義するもので、デフォルトでは std::less（第１９章）が指定されています。これはつまり、要素の大小関係の比較に <演算子を用いることを意味しています。

もう１つのテンプレート仮引数 Allocator は、メモリ確保の方法を定義するアロケータと呼ばれるオブジェクトの指定です。テンプレート仮引数 Allocator はデフォルトテンプレート実引数を持っているので省略できます。多くの場合、省略しても map/multimap は活用できるので、本章では解説しません。アロケータについては、第３２章であらためて取り上げます。

map/multimap の要素は、std::pair<Key, T> で表現されます。要素の型は、map/multimap の内部で、value_type という名前の型別名が定義されています。同様に、キーの型は key_type、要素の値の型は mapped_type という名前の型別名があります。

なお、この章のサンプルは、特に断らない限り、map と multimap の違いは型だけです。

サイズ 🔗

map/multimap の中に実際に存在している要素数が「サイズ」です。

vector の場合、実際に確保された領域の大きさを指して「容量」という言葉があります。map/multimap の場合も、内部に領域を確保していますが、map/multimap では「容量」を意識する必要はありません（調べることもできません）。

現在の「サイズ」を知るには、sizeメンバ関数を使います。また、「サイズ」が 0 かどうかは、emptyメンバ関数で調べられます。

「サイズ」の最大値は max_sizeメンバ関数で取得できます。戻り値の型は、map なら std::map<>::size_type型、multimap なら std::multimap<>::size_type型です。

使用例としては、次のようになります。

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

typedef std::map<std::string, int> StringIntMap;

int main()
{
    StringIntMap siMap;

    siMap.insert(std::make_pair("aaa", 0));
    siMap.insert(std::make_pair("bbb", 1));
    siMap.insert(std::make_pair("ccc", 2));

    std::cout << siMap.max_size() << "\n"
        << siMap.size() << "\n"
        << std::boolalpha << siMap.empty() << std::endl;
}

実行結果：

89478485
3
false

生成と初期化 🔗

map/multimap には、複数のコンストラクタが定義されているので、さまざまな方法でインスタンス化できます。

typedef std::map<std::string, int> StringIntMap;

int main()
{
    const std::pair<std::string, int> a[] = {
        std::make_pair("aaa", 0),
        std::make_pair("bbb", 1),
        std::make_pair("ccc", 2),
    };

    StringIntMap map1;              // 空
    StringIntMap map2(map1);        // 他の map からコピー
    StringIntMap map3(a, a + 3);    // イテレータで指定された範囲からコピー
}

map1、map3の方法の場合は、ソート基準と、アロケータを渡すデフォルト実引数が２つ隠されています。ソート基準に関しては、後の項であらためて取り上げます。アロケータについては、第３２章まで扱いません。

破棄 🔗

デストラクタでは、map/multimap が内部で確保した領域が破棄されます。

仮想デストラクタ（【言語解説】第２７章）ではないので、map/multimap を継承して使用することは不適切であることに注意してください。

ソート基準 🔗

ソートの基準は、テンプレート実引数で指定するか、コンストラクタの引数で指定します。

まず、テンプレート実引数で指定する方法を見ていきましょう。

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

typedef std::map<std::string, int> StringIntMap;
typedef std::map<std::string, int, std::greater<std::string> > StringIntReverseMap;

int main()
{
    const std::pair<std::string, int> a[] = {
        std::make_pair("aaa", 0),
        std::make_pair("bbb", 1),
        std::make_pair("ccc", 2),
    };

    StringIntMap map1(a, a + 3);
    StringIntReverseMap map2(a, a + 3);

    const StringIntMap::const_iterator itEnd1 = map1.end();
    for (StringIntMap::const_iterator it1 = map1.begin(); it1 != itEnd1; ++it1) {
        std::cout << it1->first << ":" << it1->second << " ";
    }
    std::cout << std::endl;

    const StringIntReverseMap::const_iterator itEnd2 = map2.end();
    for (StringIntReverseMap::const_iterator it2 = map2.begin(); it2 != itEnd2; ++it2) {
        std::cout << it2->first << ":" << it2->second << " ";
    }
    std::cout << std::endl;
}

実行結果：

aaa:0 bbb:1 ccc:2
ccc:2 bbb:1 aaa:0

typedef によって、２つの型の別名を定義しています。StringIntMap の方は、ソート基準を定義していないので、デフォルト実引数 (std::less<>) が使用されます。この場合、ソートには <演算子が使用されます。つまり、std::string型のキーによって、要素が昇順に並びます。

StringIntReverseMap の方は、ソート基準として std::greater<> を使用しました。こちらは、ソートに >演算子を使用するので、要素はキーの降順に並びます。

std::less<> や std::greater<> は、標準の関数オブジェクトで、<functional> という標準ヘッダに定義されています。関数オブジェクトについては、第１９章で取り上げます。

２つの map は、共通の要素（配列a）で初期化されていますが、要素を順番に出力してみると、逆の順序に並ぶことが分かります。（要素の出力処理のところで、std::map<>::const_iterator を使用しています。これは、「イテレータ」の項で説明しています）。

このように、ソート基準をテンプレート実引数で指定する方法では、コンテナの型自体が異なったものになります。そのため、型の不一致がコンパイラによって検出されます。これは利点でもあるし、不便さが生まれることもあります。実際、型が違うため、要素を出力する部分の処理は、StringIntMap と StringIntReverseMap とで同じですが、テンプレートを使わない普通の関数にまとめることができません。

次に、コンストラクタの引数で指定する方法です。

#include <iostream>
#include <set>
#include <map>

template <typename T>
class MyCompare {
public:
    enum Mode {
        MODE_NORMAL,
        MODE_REVERSE,
    };

public:
    explicit MyCompare(Mode mode = MODE_NORMAL) :
        mMode(mode)
    {}

    inline bool operator()(const T& a, const T& b) const
    {
        return mMode == MODE_NORMAL ? a < b : a > b;
    }

private:
    Mode    mMode;
};

typedef std::map<std::string, int, MyCompare<std::string> > StringIntMap;

void PrintIntMap(const StringIntMap& siMap)
{
    const StringIntMap::const_iterator itEnd = siMap.end();
    for (StringIntMap::const_iterator it = siMap.begin(); it != itEnd; ++it) {
        std::cout << it->first << ":" << it->second << " ";
    }
    std::cout << std::endl;
}

int main()
{
    const std::pair<std::string, int> a[] = {
        std::make_pair("aaa", 0),
        std::make_pair("bbb", 1),
        std::make_pair("ccc", 2),
    };

    StringIntMap map1(a, a + 3);
    StringIntMap map2(a, a + 3, MyCompare<std::string>(MyCompare<std::string>::MODE_REVERSE));

    PrintIntMap(map1);
    PrintIntMap(map2);
}

実行結果：

aaa:0 bbb:1 ccc:2
ccc:2 bbb:1 aaa:0

この方法の場合は、ソート基準を表現する関数オブジェクトを独自で用意します。ここで用意した MyCompare は、コンストラクタに渡す引数によって、ソートの方法を切り替えられるようになっています。

map/multimap の３つ目のテンプレート仮引数には、MyCompare を指定しています。ソート基準は、コンストラクタで指定するので、map/multimap としては、１つの型で済みます。実際、要素を出力する部分を、PrintIntMap関数にまとめることができています。

なお、MyCompare に、デフォルトコンストラクタ（【言語解説】第１３章）がないと、map/multimap のコンストラクタで、必ず明示的にソート基準を指定しないといけなくなります。

要素のアクセス 🔗

map/multimap では、要素の追加や削除のたびにソートされるため、ランダムアクセスはできません。また、シーケンスコンテナ（第４章）のように、frontメンバ関数や backメンバ関数もありません。

map/multimap で、要素へアクセスする方法には、「検索」を行うものと、「イテレータ」を使うものがあります。これらの解説は、それぞれの項で行います。

また、map の場合は、[]演算子が使えます。

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

typedef std::map<std::string, int> StringIntMap;

int main()
{
    const std::pair<std::string, int> a[] = {
        std::make_pair("aaa", 0),
        std::make_pair("bbb", 1),
        std::make_pair("ccc", 2),
    };

    StringIntMap map(a, a + 3);

    std::cout << map["bbb"] << std::endl;

    map["bbb"] = 99;
    map["xxx"] = 100;
    std::cout << map["bbb"] << std::endl;
    std::cout << map["xxx"] << std::endl;
}

実行結果：

1
99
100

[]演算子に渡すのは、キーとなる値なので、ここでは std::string型そのものか、std::string へ変換できる型になります。そして、キーが一致した要素の値への参照が返されます。

[]演算子によって指定したキーを持った要素が、map内にない場合、自動的に要素が作られて、追加されます。この挙動は便利なこともありますが、指定するべきキーを間違えていても気づきにくいので注意が必要です。なお、この要素の自動作成処理には、デフォルトコンストラクタが使用されるので、要素の値の型がデフォルトコンストラクタを持っている必要があります。

どんな手段を使うにしても、map/multimap の要素が持つキーは書き換えてはならない（値は構わない）という点に注意してください。map/multimap は、要素の追加や削除が起きるたびに、ソート済みの状態を保つようになっていますが、外部から勝手にキーを書き換えられると、ソート済みの状態が壊されてしまい、以降の処理が正しく動作する保証が無くなってしまいます。また、multimap の場合には、要素の重複を許さないという特性まで失われる可能性があります。

実際には、どの方法でアクセスしても、返されるキーの型には const が付いているので、const_cast で無理やり、const を外すことをしなければ、普通は書き換えることはできません。

どうしても、キーを書き換える必要がある場合は、いったん、その要素を削除し、書き換えを行ってから、挿入し直すという手段を採ります。要素を削除する方法は「削除」の項で、挿入する方法は「挿入」の項で説明します。

イテレータ 🔗

イテレータに関する詳細は、第１４章であらためて取り上げますが、ここでは、map/multimap におけるイテレータについて、簡単に紹介します。

他のコンテナと同様に、最初の要素を指すイテレータを beginメンバ関数で、最後の要素の次を指すイテレータを endメンバ関数で取得できます。また、逆方向に走査するための逆イテレータの場合に最初の要素を指すイテレータを rbeginメンバ関数で、最後の要素の次を指すイテレータを rendメンバ関数で取得できます。

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

typedef std::map<std::string, int> StringIntMap;

int main()
{
    const std::pair<std::string, int> a[] = {
        std::make_pair("aaa", 0),
        std::make_pair("bbb", 1),
        std::make_pair("ccc", 2),
    };

    StringIntMap siMap(a, a + 3);

    const StringIntMap::const_iterator itEnd = siMap.end();
    for (StringIntMap::const_iterator it = siMap.begin(); it != itEnd; ++it) {
        std::cout << it->first << ":" << it->second << " ";
    }
    std::cout << std::endl;

    const StringIntMap::const_reverse_iterator ritEnd = siMap.rend();
    for (StringIntMap::const_reverse_iterator rit = siMap.rbegin(); rit != ritEnd; ++rit) {
        std::cout << rit->first << ":" << rit->second << " ";
    }
    std::cout << std::endl;
}

実行結果：

aaa:0 bbb:1 ccc:2
ccc:2 bbb:1 aaa:0

beginメンバ関数や endメンバ関数で取得できるイテレータの型は、std::map<>::iterator型、あるいはその const版である std::map<>::const_iterator型です。

また、rbeginメンバ関数、rendメンバ関数の場合は、std::map<>::reverse_iterator型、あるいはその const版である std::map<>::const_reverse_iterator型になります（それぞれ、multimap の場合は、「map」を「multimap」に読み替えてください）。

これらイテレータの型は、map/multimap内部で typedef されているものですが、その正体（typedef の元になる型) が何であるかは実装依存です。

イテレータが指す先にあるのは、std::pair<const Key, T> です。そのため、it->first のようなアクセスでキーが得られ、it->second で要素の値が得られます。

ただし、どの型のイテレータであっても、イテレータを通して要素のキーを書き換えることはできません。キーの型には const が付加されているので、普通は書き換えることはできませんが、const_cast を用いる等の方法があるので、不可能ではありません。キーを書き換えてしまった場合、ソート済みの状態を保つことや、multimap において要素の重複がないことを保証できなくなります。

同じ理由で、要素を変更する STLアルゴリズム（第１８章）に、イテレータを渡してもいけません。

検索 🔗

map/multimap から、特定の要素を探し出すには、findメンバ関数を使います。

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

typedef std::map<std::string, int> StringIntMap;

int main()
{
    const std::pair<std::string, int> a[] = {
        std::make_pair("aaa", 0),
        std::make_pair("bbb", 1),
        std::make_pair("ccc", 2),
    };

    StringIntMap siMap(a, a + 3);

    StringIntMap::iterator it = siMap.find("bbb");
    if (it != siMap.end()) {
        std::cout << "見つかりました" << std::endl;
    }
    else {
        std::cout << "見つかりません" << std::endl;
    }
}

実行結果：

見つかりました

findメンバ関数は、引数で指定したキーを持った、最初の要素を指すイテレータを返します。発見できなかった場合は、endメンバ関数が返す結果と同じイテレータを返します。

find関数には、同名の STLアルゴリズムがありますが、map/multimap の場合にはメンバ関数版を使うようにしてください。

countメンバ関数を使うと、指定の値を持った要素の数を調べられます。map の場合は要素の重複を許さないので、必ず 0 か 1 を返すはずです。

count関数には、同名の STLアルゴリズムがありますが、map/multimap の場合にはメンバ関数版を使うようにしてください。

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

typedef std::map<std::string, int> StringIntMap;
typedef std::multimap<std::string, int> StringIntMultiMap;

int main()
{
    const std::pair<std::string, int> a1[] = {
        std::make_pair("aaa", 0),
        std::make_pair("bbb", 1),
        std::make_pair("ccc", 2),
    };
    const std::pair<std::string, int> a2[] = {
        std::make_pair("aaa", 0),
        std::make_pair("aaa", 1),
        std::make_pair("bbb", 0),
        std::make_pair("ccc", 0),
        std::make_pair("ccc", 1),
    };

    StringIntMap      siMap(a1, a1 + 3);
    StringIntMultiMap simMap(a2, a2 + 5);

    std::cout << siMap.count("ccc") << std::endl;
    std::cout << simMap.count("ccc") << std::endl;
}

実行結果：

1
2

要素を挿入する適切な位置を調べる関数が３つあります。それぞれ、lower_bound、upper_bound、equal_range といい、要素を挿入できる最初の位置、最後の位置、最初と最後の位置を返します。意味が分かりにくいと思いますが、要するに、要素を再ソートする必要がない挿入位置を教えてくれるということです。

これらの関数には、同名の STLアルゴリズムがありますが、map/multimap の場合にはメンバ関数版を使うようにしてください。

lower_bound、upper_bound の場合、結果はイテレータで返されます。equal_range の場合、結果は std::pair（第３章）で返されます。equal_range の呼び出しは、「std::make_pair(s.lower_bound(), s.upper_bound())」と同じことです。

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

typedef std::map<std::string, int> StringIntMap;

void func(const StringIntMap& siMap, const std::string& key)
{
    std::cout << std::distance(siMap.begin(), siMap.lower_bound(key)) << std::endl;
    std::cout << std::distance(siMap.begin(), siMap.upper_bound(key)) << std::endl;

    std::pair<StringIntMap::const_iterator, StringIntMap::const_iterator> itPair = siMap.equal_range(key);
    std::cout << std::distance(siMap.begin(), itPair.first) <<
          " " << std::distance(siMap.begin(), itPair.second) << std::endl;
}


int main()
{
    const std::pair<std::string, int> a[] = {
        std::make_pair("aaa", 0),
        std::make_pair("bbb", 1),
        std::make_pair("ccc", 2),
    };

    StringIntMap siMap(a, a + 3);

    func(siMap, "abc");
    func(siMap, "xyz");
}

実行結果：

std::distance関数（第１５章）を使って、先頭位置から、各関数が返した位置までの距離を調べています。

キーが {“aaa”, “bbb”, “ccc”} の map に対して、“abc” を挿入できる位置を探すと、lower_bound、upper_bound、equal_range のいずれを使っても、1 という結果が得られました。先頭からの距離なので、“bbb” という値が入っている場所を指すイテレータが返されたことが分かります。イテレータと値を渡すタイプの insertメンバ関数に渡せば、{“aaa”, “abc”, “bbb”, “ccc”} になります。

一方、“xyz” を挿入できる位置を探すと、3 という結果が得られました。これは、末尾を超えたところです。こちらも同様に、insertメンバ関数に渡せば、{“aaa”, “bbb”, “ccc”, “xyz”} になります。

同じことを、multimap に対して行ってみます。今度は、同じ要素が複数あります。

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

typedef std::multimap<std::string, int> StringIntMap;

void func(const StringIntMap& siMap, const std::string& key)
{
    std::cout << std::distance(siMap.begin(), siMap.lower_bound(key)) << std::endl;
    std::cout << std::distance(siMap.begin(), siMap.upper_bound(key)) << std::endl;

    std::pair<StringIntMap::const_iterator, StringIntMap::const_iterator> itPair = siMap.equal_range(key);
    std::cout << std::distance(siMap.begin(), itPair.first) <<
          " " << std::distance(siMap.begin(), itPair.second) << std::endl;
}


int main()
{
    const std::pair<std::string, int> a[] = {
        std::make_pair("aaa", 0),
        std::make_pair("aaa", 1),
        std::make_pair("bbb", 0),
        std::make_pair("ccc", 0),
        std::make_pair("ccc", 1),
    };

    StringIntMap siMap(a, a + 5);

    func(siMap, "abc");
    func(siMap, "ccc");
    func(siMap, "xyz");
}

実行結果：

すでに、“ccc” が 2つ入った状態で、“ccc” を挿入できる位置を探すと、lower_bound と upper_bound とで異なる結果を返します。lower_bound なら最初の位置である 3番目のところ、upper_bound なら最後の位置である 5番目のところを指すイテレータを返しています。equal_range はこの組み合わせなので、3番目と 5番目を指すイテレータの pair になります。

このように、map が対象の場合は、要素に重複がないため、適切な挿入位置はいつも１カ所に定まるので、lower_bound、upper_bound、equal_range の結果は同じになります。一方、multimap が対象の場合は、要素が重複していると、適切な挿入位置に範囲があるかも知れず、異なる結果を返す可能性があります。

代入 🔗

map/multimap は、テンプレート実引数が同一であれば、代入演算子を使ってコピーできます。

テンプレート実引数が同一でなければならないので、ソート基準やアロケータが違うと代入できません。ソート基準の違いに関しては、テンプレート実引数は共通にしておき、コンストラクタの引数から指定することで回避できます。詳細は、「ソート基準」の項を参照してください。

挿入 🔗

要素を挿入する方法は、シーケンスコンテナとは少し違いがあります。

まず、push_back、pop_back のように、挿入位置を指定するものはありません。map/multimap は、内部でソートを行うので、挿入位置を指定することに意味がないためです。insert はありますが、挿入位置は指定しないようになっています（オーバーロードの１形式だけは、イテレータを指定するものがありますが、意味合いが少し異なります）。

insertメンバ関数は、いくつかの形式があります。１つ目は、挿入する要素だけを指定します。これがもっとも基本的な使い方になります。map と multimap とでは、戻り値の形が異なるので、まずは map の例を挙げます。

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

typedef std::map<std::string, int> StringIntMap;

void InsertToStringIntMap(StringIntMap& siMap, const StringIntMap::value_type& v)
{
    std::pair<StringIntMap::iterator, bool> result = siMap.insert(v);
    if (result.second) {
        std::cout << "(" << v.first << ":" << v.second << ") を挿入しました。" << std::endl;
    }
    else {
        std::cout << v.first << "は挿入済みです。" << std::endl;
    }
}

void PrintStringIntMap(const StringIntMap& siMap)
{
    const StringIntMap::const_iterator itEnd = siMap.end();
    for (StringIntMap::const_iterator it = siMap.begin(); it != itEnd; ++it) {
        std::cout << it->first << ":" << it->second << " ";
    }
    std::cout << std::endl;
}

int main()
{
    const std::pair<std::string, int> a[] = {
        std::make_pair("aaa", 0),
        std::make_pair("bbb", 1),
        std::make_pair("ccc", 2),
    };

    StringIntMap siMap(a, a + 3);

    InsertToStringIntMap(siMap, std::make_pair("aaa", 1));
    InsertToStringIntMap(siMap, std::make_pair("ddd", 3));

    PrintStringIntMap(siMap);
}

実行結果：

aaaは挿入済みです。
(ddd:3) を挿入しました。
aaa:0 bbb:1 ccc:2 ddd:3

map の場合、戻り値の型は std::pair で、firstメンバは std::map<>::iterator、secondメンバは bool です。挿入が行われた場合、secondメンバが true になり、行われなかった場合は false になります。挿入が行われない場合というのは、すでに map の中に、同じキーを持った要素ある場合です。

firstメンバの方は、挿入された要素、あるいはすでに存在していた要素を指すイテレータです。

次に multimap の場合です。

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

typedef std::multimap<std::string, int> StringIntMultiMap;

void InsertToStringIntMultiMap(StringIntMultiMap& simMap, const StringIntMultiMap::value_type& v)
{
    StringIntMultiMap::iterator it = simMap.insert(v);
    std::cout << std::distance(simMap.begin(), it) << "番目の位置に" <<
        "(" << v.first << ":" << v.second << ") を挿入しました。" << std::endl;
}

void PrintStringIntMultiMap(const StringIntMultiMap& simMap)
{
    const StringIntMultiMap::const_iterator itEnd = simMap.end();
    for (StringIntMultiMap::const_iterator it = simMap.begin(); it != itEnd; ++it) {
        std::cout << it->first << ":" << it->second << " ";
    }
    std::cout << std::endl;
}

int main()
{
    const std::pair<std::string, int> a[] = {
        std::make_pair("aaa", 0),
        std::make_pair("aaa", 1),
        std::make_pair("bbb", 0),
        std::make_pair("ccc", 0),
        std::make_pair("ccc", 1),
    };

    StringIntMultiMap simMap(a, a + 5);

    InsertToStringIntMultiMap(simMap, std::make_pair("aaa", 1));
    InsertToStringIntMultiMap(simMap, std::make_pair("ddd", 3));

    PrintStringIntMultiMap(simMap);
}

実行結果：

2番目の位置に(aaa:1) を挿入しました。
6番目の位置に(ddd:3) を挿入しました。
aaa:0 aaa:1 aaa:1 bbb:0 ccc:0 ccc:1 ddd:3

multimap の場合、戻り値の型は std::multimap<>::iterator です。map と違い、multimap の insert は（例外が起こらなければ）必ず挿入されるので、挿入された位置を返すだけになっています。

insertメンバ関数の２つ目の形式は、２つのイテレータを使って表現される範囲にある値をまとめて挿入します。こちらは、戻り値が void型になっていて、map/multimap で違いはありません。逆にいうと、map の場合に挿入されなかった要素があったかどうかを知ることはできません。

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

typedef std::map<std::string, int> StringIntMap;

void PrintStringIntMap(const StringIntMap& siMap)
{
    const StringIntMap::const_iterator itEnd = siMap.end();
    for (StringIntMap::const_iterator it = siMap.begin(); it != itEnd; ++it) {
        std::cout << it->first << ":" << it->second << " ";
    }
    std::cout << std::endl;
}

int main()
{
    const std::pair<std::string, int> a1[] = {
        std::make_pair("aaa", 0),
        std::make_pair("bbb", 1),
        std::make_pair("ccc", 2),
    };
    const std::pair<std::string, int> a2[] = {
        std::make_pair("caa", 3),
        std::make_pair("baa", 4),
        std::make_pair("aaa", 5),
    };

    StringIntMap siMap(a1, a1 + 3);

    siMap.insert(a2, a2 + 3);

    PrintStringIntMap(siMap);
}

実行結果：

aaa:0 baa:4 bbb:1 caa:3 ccc:2

insertメンバ関数の３つ目の形式は、イテレータと要素を指定します。ここで指定するイテレータは、挿入する位置を探すためのヒントを与えるという意味合いのものです。map/multimap は、ソートされた状態を保つために、必ず適切な挿入位置を決める必要がありますが、引数から適切なイテレータを指定できれば、この位置決定のパフォーマンスを高められます。

たとえば、lower_bound、upper_bound のような関数を使い（「検索」の項を参照）、挿入位置を決定したとすれば、それらの関数が返したイテレータを渡せば良いでしょう。

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

typedef std::map<std::string, int> StringIntMap;

void PrintStringIntMap(const StringIntMap& siMap)
{
    const StringIntMap::const_iterator itEnd = siMap.end();
    for (StringIntMap::const_iterator it = siMap.begin(); it != itEnd; ++it) {
        std::cout << it->first << ":" << it->second << " ";
    }
    std::cout << std::endl;
}

int main()
{
    const std::pair<std::string, int> a[] = {
        std::make_pair("aaa", 0),
        std::make_pair("bbb", 1),
        std::make_pair("ccc", 2),
    };

    StringIntMap siMap(a, a + 3);

    StringIntMap::iterator it = siMap.insert(siMap.end(), std::make_pair("xyz", 9));
    std::cout << std::distance(siMap.begin(), it)
              << "番目の位置に挿入しました。" << std::endl;

    PrintStringIntMap(siMap);
}

実行結果：

3番目の位置に挿入しました。
aaa:0 bbb:1 ccc:2 xyz:9

戻り値は、map なら std::map<>::iterator、multimap なら std::multimap<>::iterator です。いずれにしても、挿入された要素を指すイテレータになります。map の場合は、すでに同じ値の要素があったかもしれませんが、それを知ることはできません。

削除 🔗

「削除」は、コンテナから要素を取り除くということです。格納されている要素が new で生成されたものであるのなら、取り除くだけではなく delete を行わなければなりません。「削除」はそういった、必要な解放処理までは面倒を見ないことに注意してください。

push_back や pop_back がないのと同様に、pop_back や pop_front はありません。使えるのは、erase と clear になります。

eraseメンバ関数は、いくつかの形式があります。

１つ目の形式は、イテレータを１つ渡し、指す先の要素を削除するものです。挿入時に位置を指定することに意味はありませんが、削除する要素の位置を指定することには意味があるので、erase にはこの形式があります。

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

typedef std::map<std::string, int> StringIntMap;

void PrintStringIntMap(const StringIntMap& siMap)
{
    const StringIntMap::const_iterator itEnd = siMap.end();
    for (StringIntMap::const_iterator it = siMap.begin(); it != itEnd; ++it) {
        std::cout << it->first << ":" << it->second << " ";
    }
    std::cout << std::endl;
}

int main()
{
    const std::pair<std::string, int> a[] = {
        std::make_pair("aaa", 0),
        std::make_pair("bbb", 1),
        std::make_pair("ccc", 2),
    };

    StringIntMap siMap(a, a + 3);

    StringIntMap::iterator it = siMap.find("bbb");
    if (it != siMap.end()) {
        siMap.erase(it);
    }

    PrintStringIntMap(siMap);
}

実行結果：

aaa:0 ccc:2

必ず有効な位置を指すイテレータを指定しなければならないことに注意してください。たとえば、このサンプルプログラムでいうと、「std::map<>::find()」が要素を発見できなかった場合、末尾の要素の次を指すイテレータを返すので、そのチェックを行っています。

実際のところ、このように特定の値を持った要素を削除したいのであれば、eraseメンバ関数の３つ目の形式を使った方が簡単です。

eraseメンバ関数の２つ目の形式は、２つのイテレータを使って表現される範囲にある要素をまとめて削除します。

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

typedef std::map<std::string, int> StringIntMap;

void PrintStringIntMap(const StringIntMap& siMap)
{
    const StringIntMap::const_iterator itEnd = siMap.end();
    for (StringIntMap::const_iterator it = siMap.begin(); it != itEnd; ++it) {
        std::cout << it->first << ":" << it->second << " ";
    }
    std::cout << std::endl;
}

int main()
{
    const std::pair<std::string, int> a[] = {
        std::make_pair("aaa", 0),
        std::make_pair("bbb", 1),
        std::make_pair("ccc", 2),
    };

    StringIntMap siMap(a, a + 3);

    StringIntMap::iterator it = siMap.begin();
    std::advance(it, 2);
    siMap.erase(siMap.begin(), it);

    PrintStringIntMap(siMap);
}

実行結果：

ccc:2

eraseメンバ関数の３つ目の形式は、削除したい要素の値を指定します。multimap の場合、条件を満たす要素が複数あったら、そのすべてが削除されます。

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

typedef std::map<std::string, int> StringIntMap;

void PrintStringIntMap(const StringIntMap& siMap)
{
    const StringIntMap::const_iterator itEnd = siMap.end();
    for (StringIntMap::const_iterator it = siMap.begin(); it != itEnd; ++it) {
        std::cout << it->first << ":" << it->second << " ";
    }
    std::cout << std::endl;
}

int main()
{
    const std::pair<std::string, int> a[] = {
        std::make_pair("aaa", 0),
        std::make_pair("bbb", 1),
        std::make_pair("ccc", 2),
    };

    StringIntMap siMap(a, a + 3);

    siMap.erase("bbb");

    PrintStringIntMap(siMap);
}

実行結果：

aaa:0 ccc:2

最後に、要素をすべて削除する場合ですが、これは clearメンバ関数を使うだけです。

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

typedef std::map<std::string, int> StringIntMap;

int main()
{
    const std::pair<std::string, int> a[] = {
        std::make_pair("aaa", 0),
        std::make_pair("bbb", 1),
        std::make_pair("ccc", 2),
    };

    StringIntMap siMap(a, a + 3);

    siMap.clear();
    assert(siMap.empty());
}

実行結果：

はてなブックマークに保存	Pocket に保存	Facebook でシェア
X でポスト／フォロー	LINE で送る	noteで書く
RSS	管理者情報	プライバシーポリシー

map と multimap | Programming Place Plus　C++編【標準ライブラリ】　第９章

この章の概要 🔗

map と multimap 🔗

サイズ 🔗

生成と初期化 🔗

破棄 🔗

ソート基準 🔗

要素のアクセス 🔗

イテレータ 🔗

検索 🔗

代入 🔗

挿入 🔗

削除 🔗

練習問題 🔗

参考リンク 🔗

更新履歴 🔗