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

C++編【標準ライブラリ】 第9章 map と multimap

先頭へ戻る

この章の概要

この章の概要です。


map と multimap

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

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

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

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

また、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 はクラステンプレート(【言語解説】第20章)なので、使用時にはテンプレート実引数の指定が必要です。テンプレート仮引数 Key は、要素のキーの型、テンプレート仮引数 T は、要素の値の型です。例えば、std::string型のキーを持ち、int型の値を扱う map は、以下のようになります。

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

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

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

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

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の方法の場合は、ソート基準と、アロケータを渡すデフォルト実引数が2つ隠されています。ソート基準に関しては、後の項で改めて取り上げます。アロケータについては、第32章まで扱いません。

C++11 (生成と初期化)

C++11 で、コンストラクタ周りは強化されています。 まず、std::initializer_list を使用できるようになりました。

int main()
{
    StringIntMap map4{ {"aaa", 0}, {"bbb", 1}, {"ccc", 2} };       // std::initializer_list
}

第2引数にはソート基準を、第3引数にはアロケータを指定することが可能です(それぞれデフォルト実引数を持っているので省略可)。

また、ムーブコンストラクタが追加されています。

int main()
{
    StringIntMap map5(std::move(map1));  // ムーブコンストラクタ
}

こちらは、第2引数にアロケータが指定できます。

また、これまでは、アロケータを指定する形式では、いつも間に、ソート基準を指定する引数が挟まれていましたが、C++11 では、アロケータを指定する引数だけの形式が追加されています。

破棄

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

仮想デストラクタ(【言語解説】第27章)ではないので、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 によって、2つの型の別名を定義しています。StringIntMap の方は、ソート基準を定義していないので、デフォルト実引数 (std::less<>) が使用されます。この場合、ソートには <演算子が使用されます。つまり、std::string型のキーによって、要素が昇順に並びます。

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

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

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

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

要素のアクセス

map/multimap では、要素の追加や削除のたびにソートされるため、ランダムアクセスはできません。また、シーケンスコンテナ(第4章)のように、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 を外すことをしなければ、普通は書き換えることはできません。

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

C++11 (operator[] のムーブ対応)

C++11 の map では、operator[] の引数を、ムーブで渡すことが可能になりました。

std::string s("xxx");
std::cout << map[std::move(s)] << std::endl;

C++11 (atメンバ関数)

C++11 の map には、atメンバ関数が追加されています。役割は、vector の atメンバ関数と同様で、operator[] の代替になりますが、指定されたキーを持つ要素が見つからない場合には、std::out_of_range例外が送出されます

std::cout << map.at("xxx") << std::endl;

イテレータ

イテレータに関する詳細は、第14章で改めて取り上げますが、ここでは、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アルゴリズム(第18章)に、イテレータを渡してもいけません。

C++11(const版のイテレータ取得関数)

C++11 には、必ず constイテレータを返す cbegin、cend、crbegin、crend の各メンバ関数が追加されています。

元々、begin、end、rbegin、rend の各メンバ関数は、非constイテレータを返すものと constイテレータを返すものとでオーバーロードされており、constイテレータ型の変数で受け取れば、const版を使えました。

新たにこれらのメンバ関数が追加された意義は幾つかあると思いますが、例えば、C++11 で追加された auto(【言語解説】第7章)を使いやすくすることが考えられます。

std::map<std::string, int> siMap;
auto it  = siMap.begin();   // こう書くと std::map<std::string, int>::iterator型
auto it2 = siMap.cbegin();  // こう書くと std::map<std::string, int>::const_iterator型

検索

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

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

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

lower_bound、upper_bound の場合、結果はイテレータで返されます。equal_range の場合、結果は std::pair(第3章)で返されます。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");
}

実行結果

1
1
1 1
3
3
3 3

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

キーが {"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");
}

実行結果

2
2
2 2
3
5
3 5
5
5
5 5

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

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

代入

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

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

C++11 (std::initializer_list対応)

C++11 では、代入演算子の引数として、std::initializer_list を使えるようになりました。

#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()
{
    StringIntMap siMap;
    siMap = { {"aaa", 0}, {"bbb", 1}, {"ccc", 2} };

    PrintStringIntMap(siMap);
}

実行結果

aaa:0 bbb:1 ccc:2

C++11 (ムーブ代入演算子)

C++11 では、ムーブ代入演算子が追加されています。

#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 siMap2;

    siMap2 = std::move(siMap);

    PrintStringIntMap(siMap);
    PrintStringIntMap(siMap2);
}

実行結果


aaa:0 bbb:1 ccc:2

挿入

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

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

insertメンバ関数は、幾つかの形式が存在します。1つ目は、挿入する要素だけを指定します。これが最も基本的な使い方になります。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メンバ関数の2つ目の形式は、2つのイテレータを使って表現される範囲にある値をまとめて挿入します。こちらは、戻り値が 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メンバ関数の3つ目の形式は、イテレータと要素を指定します。ここで指定するイテレータは、挿入する位置を探すためのヒントを与えるという意味合いのものです。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 の場合は、すでに同じ値の要素があったかも知れませんが、それを知ることはできません。

C++11(移動による挿入)

C++11 では、移動による挿入ができるようになっています。

std::pair<std::string, int> v("xyz", 9);  // があるとして・・・

siMap.insert(std::move(v));
siMap.insert(it, std::move(v));

C++11(insert の std::initializer_list対応)

C++11 では、insertメンバ関数が std::initializer_list に対応しています。

siMap.insert({{"abc", 0}, {"xyz", 9}});

C++11(insert のイテレータの const化)

C++03 までの insertメンバ関数は、要素の挿入位置のヒントを指定する第1引数の型が、std::map<>::iterator型になっていました。そのため、この引数の意味は、挿入位置を示すことだけなので constイテレータで問題ないはずなのに、constイテレータを渡すことができません。

C++11 では、第1引数の型が std::map<>::const_iterator型に改められています(multimap なら std::multimap<>::const_iterator型)。

C++11(emplace、emplace_hint)

insert は、map/multimap の外で挿入するオブジェクトを作り、それをコピー(または移動)する必要があります。これは、少なくとも一時オブジェクトを生成するコストが掛かるため(コピーの場合は、更にコピーのコスト)、使い方によっては非効率さがあります。

C++11 では、要素のコンストラクタに渡す引数だけを指定し、メンバ関数内でオブジェクトを作らせるという方法が使えるようになりました。要素1つだけを指定する insert の代わりには、emplaceメンバ関数を、挿入位置のヒントと要素を指定する insert の代わりには、emplace_hintメンバ関数を使用します。

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

siMap.insert(std::make_pair("xyz", 9));      // 一時オブジェクトを作ってコピー
siMap.emplace("xyz", 9);                     // コンストラクタの引数だけ指定し、関数内で生成

siMap.insert(it, std::make_pair("xyz", 9));  // 一時オブジェクトを作ってコピー
siMap.emplace_hint(it, "xyz", 9);            // コンストラクタの引数だけ指定し、関数内で生成

削除

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

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

eraseメンバ関数は、幾つかの形式が存在します。

1つ目の形式は、イテレータを1つ渡し、指す先の要素を削除するものです。挿入時に位置を指定することに意味はありませんが、削除する要素の位置を指定することには意味があるので、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メンバ関数の3つ目の形式を使った方が簡単です。

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

#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メンバ関数の3つ目の形式は、削除したい要素の値を指定します。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());
}

実行結果





C++11(erase のイテレータの const化)

C++03 までの eraseメンバ関数は、要素の位置を指定するイテレータが、std::map<>::iterator型になっていました(multimap は std::multimap<>::iterator型)。そのため、この引数の意味は、位置を示すことだけなので constイテレータで問題ないはずなのに、constイテレータを渡すことができません。

C++11 では、イテレータの型が std::map<>::const_iterator型(multimap は std::multimap<>::const_iterator型)に改められています。


練習問題

問題① map/multimap に、特定のキーを持つ要素が存在するかどうか調べる関数を作成して下さい。map/multimap のテンプレート実引数は、任意で決めて構いません。

問題② map に登録されている要素のキーを変更する関数を作成して下さい。指定されたキーを持った要素が存在しない場合は、新規の要素が作られるものとします。


解答ページはこちら

参考リンク



更新履歴

'2018/4/5 VisualStudio 2013 の対応終了。

'2018/4/2 「VisualC++」という表現を「VisualStudio」に統一。

'2018/1/5 コンパイラの対応状況について、対応している場合は明記しない方針にした。

'2017/7/30 clang 3.7 (Xcode 7.3) を、Xcode 8.3.3 に置き換え。

'2017/3/25 VisualC++ 2017 に対応。

≪更に古い更新履歴を展開する≫



前の章へ(第8章 set と multiset)

次の章へ(第10章 stack)

C++編のトップページへ

Programming Place Plus のトップページへ


はてなブックマーク Pocket に保存 Twitter でツイート Twitter をフォロー
Facebook でシェア Google+ で共有 LINE で送る rss1.0 取得ボタン RSS