連想コンテナについて

これまでにSTLの一部のコンテナ、例えばvector、list、dequeなどを学んできました。これらのコンテナは線形構造を持つシーケンシャルコンテナと呼ばれます。

では、連想コンテナとシーケンシャルコンテナの違いは何でしょうか？

連想コンテナとは、各要素がキー(key)と値(value)を持つコンテナです。要素が連想コンテナに挿入される際、内部構造は赤黒木やハッシュテーブルであり、キーの値に基づいて特定のルールで適切な位置に配置されます。

注意：連想コンテナには先頭や末尾という概念がありません（最大要素と最小要素のみ存在します）。そのため、push_back、push_front、pop_back、pop_frontのような操作は存在しません。

一般的に、連想コンテナの内部構造は平衡二分探索木であり、効率的な検索性能を実現します

キーバリューペア

上でキーについて触れましたが、キーバリューとは何でしょうか？

• キーバリューペアは一対一の関係を表現するための構造であり、通常2つのメンバ変数：keyとvalueを持ちます。keyはキーを表し、valueはkeyに対応する情報を表します。

連想コンテナの実装にはキーバリューペアが不可欠であり、標準ライブラリにはpairコンテナが専用に提供されています。

setコンテナ

3.1 概要

ドキュメント説明：

• setは以前に学んだ二分探索木のkeyモデルです。ただし、setは完全な二分探索木ではなく、実際の内部構造は赤黒木（一種の探索木）です。
• setでは同じキーを持つ要素が2つ存在することを許可しません。

3.2 コンストラクタ

1. デフォルトコンストラクタ
2. イテレータ範囲による初期化
3. コピーコンストラクタ

これまで学んできたSTLコンテナと同様なので省略します。

3.3 イテレータ

なぜイテレータで走査すると昇順になるのでしょうか？【二分探索木】を思い出してください。中間順序走査は昇順になります。したがって、setコンテナの内部イテレータ実装は中間順序です。

また、別の知識点：**イテレータをサポートするコンテナは必ず範囲forをサポートします。その内部実装はイテレータに依存しているためです。**

3.4 insert

関数プロトタイプ：

もしsetコンテナに重複要素を挿入した場合、結果はどうなるでしょうか？

以下のことが分かります：挿入する数値が重複すると、重複排除の効果があります。その内部では：キーの重複データは挿入されません。

3.5 find

戻り値：

コード例：

• 問題1：アルゴリズムライブラリalgorithmにもfind関数があるようですが、なぜsetコンテナは独自のfind関数を持っているのでしょうか？

機能は同じですが、効率面で違いがあります。setのfind関数の検索時間計算量はO(logN)です。大きい値は右部分木、小さい値は左部分木で検索し、高さ分だけ検索すればよいです。一方、アルゴリズムライブラリのfindはイテレータを使って全体を走査する（力任せ検索）ため、計算量はO(N)です。実際の開発ではfindを使用する際、組み込みのものを推奨します。

• 問題2：イテレータを使ってsetの要素値を変更することは可能ですか？

答えは明らかです！変更できません！setの要素値はそのキーであり、変更するとset要素の並び替えルールに関係します。任意にset要素値を変更すると、setの構造が重大に破壊されます。ドキュメントを見ると、通常のイテレータはconstイテレータとして定義されていることが分かります。

3.6 erase

関数プロトタイプ：

上の図をご覧ください。イテレータ方式での削除と値指定での削除には何か違いがありますか？値指定削除の方が便利ではありませんか？この2つの削除方法にはどんな違いがありますか？

値指定削除は最初の方法に基づいて実装されていると考えられます。なぜなら多くの場合、削除する値を探すために検索が必要だからです。

加えて、値指定削除方式の特徴：コンテナ外の値を削除してもエラーになりません。

3.7 count

• findだけでなく、countでも検索できます。countの役割は：値を渡すと、その値が何回出現したかを返します。したがって、検索にも使用できます。
• 値が存在する場合、必ず1を返します。なぜならsetではキーの重複を許可しないためです。

しかしfind関数があるのにcount関数を設計するのは冗長ではないでしょうか？実はcountには後で別の用途があります…

multisetコンテナ

setには親兄弟であるmultisetがあり、setコンテナとの最大の違いは：データの重複を許可します。つまり、重複データを挿入すると必ず成功します。

それ以外は、multisetとsetの操作は同じで、すべて一貫しています。ドキュメントを参照して確認できます。

ここでは重複データ許可の効果を単独でデモンストレーションします：

したがって、multisetこそが真のソートであり、データ重複が可能です。setは重複排除+ソートです。

さらに、先ほど述べたcount関数は実際にはmultisetのために用意されています。

では問題です。もし探しているデータがちょうど重複している場合、返されるのは何回目の出現データでしょうか？

アドレスを出力して確認できます

#include <iostream>
#include <vector>
#include <set>
using namespace std;

int main()
{
    vector<int> src_data = { 1,3,5,7,5,9,2,3,3,3 };
    multiset<int> multi_set_inst(src_data.begin(), src_data.end());

    auto iter_pos = multi_set_inst.begin();
    while (iter_pos != multi_set_inst.end())
    {
        cout << *iter_pos << "：" << &(*iter_pos) << endl;
        iter_pos++;
    }
    cout << endl;

    // 5を検索
    cout << "5：" << &(*multi_set_inst.find(5)) << endl;

    return 0;
}

出力結果：

実際の使用では、multisetはあまり使われず、重点的にsetを習得すれば十分です。

mapコンテナ

5.1 概要

• mapは二分探索木を改造したkey/valueモデルであり、真の意味でのキーバリューコンテナです。
• mapの特性：すべての要素は要素のキー値に基づいて自動的にソートされます。mapのすべての要素はpair構造で格納され、値(value)とキー(key)を同時に持ちます。pairの最初の要素(first)がキー、2番目の要素(second)が値と見なされます。
• 注意：mapでは2つの要素が同じキーを持つことを許可しません。

5.2 insert

関数プロトタイプ：

まず挿入インターフェースを見てください。パラメータ型に注目：value_type、これはどのような型でしょうか？ドキュメントを確認できます：

value_typeはpair構造であり、key_type（つまりキーkey）はconstで修飾されており、変更できないことを示しています！

コード例：辞書

挿入方法を上のように記述することはできません。これは多くの初心者が犯す誤りです。前述のように、キーと値はpair構造で保存する必要があります。

5.3 コンテナデータへのアクセス - イテレータ

• mapもイテレータをサポートします

コード例：

多くの初心者はおそらく上のようなコードを書きますが、コンパイルできません！ヒントから：pairはストリーム挿入<<をサポートしていません。

再度分析：**データはpair構造に存在するので、構造体内の要素にアクセスするには->または*演算子を使用できます。そして【map概要セクション】で述べたように：pairの最初の要素(first)がキー、2番目の要素(second)が値と見なされます。

同様に、mapがイテレータをサポートするということは、必ず範囲forもサポートします

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

using namespace std;

int main()
{
    map<string, string> dictionary;
    pair<string, string> element("挿入", "insert");
    dictionary.insert(element);
    dictionary.insert(pair<string, string>("挿入", "insert"));
    dictionary.insert(make_pair("削除", "erase"));
    dictionary.insert({"検索", "find"});

    // アクセスfor
    for (const auto &item : dictionary)
    {
        cout << item.first << ":" << item.second << endl;
    }
    return 0;
}

実行結果：

では今度は問題です：mapのイテレータを使ってmapの要素内容を変更することは可能でしょうか？

• キー(key)を変更しようとするのは不可能です。setと同じ理由：map要素のキーはmap要素の並び替えルールに関係します。map要素のkeyを任意に変更すると、map構造が重大に破壊されます。
• ただし要素の値(value)を変更したい場合は可能です。なぜならmap要素の値valueはmapの並び替えルールに影響を与えないからです。

公式ドキュメントも同じ答えを与えています：キーkeyはconstで修飾されており、変更できないことを示しています。

5.4 operator[]

不思議に思うかもしれません。mapの内部構造は木構造であり、通常ランダムアクセスをサポートしないはずですが、なぜmapはoperator[]をサポートするのでしょうか？

mapの一般的な使用シーンは：出現回数の統計です。

果物の出現回数を統計するコードを書くとします。ほとんどの人は以下のコードを書けます

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

using namespace std;

int main()
{
    string fruits[] = {"すいか", "すいか", "バナナ", "リンゴ", "桃", "バナナ", "バナナ", "バナナ"};
    map<string, int> fruit_count;
    // 配列内の要素をmapに投入して回数を統計
    for (auto fruit_name : fruits)
    {
        // 果物が初めて出現する場合、カウントを1にする
        map<string, int>::iterator position = fruit_count.find(fruit_name);
        if (position == fruit_count.end())
        {
            fruit_count.insert(make_pair(fruit_name, 1));
        }
        // そうでなければ2回以上出現している
        else
        {
            position->second++;
        }
    }

    for (const auto &item : fruit_count)
    {
        cout << item.first << ":" << item.second << endl;
    }
    return 0;
}

実行結果：

しかし上記コードはさらに最適化できます：operator[]を使用

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

using namespace std;

int main()
{
    string fruits[] = { "すいか", "すいか", "バナナ", "リンゴ", "桃", "バナナ", "バナナ", "バナナ" };
    map<string, int> fruit_count;
    // 配列内の要素をmapに投入して回数を統計
    for (auto fruit_name : fruits)
    {
        fruit_count[fruit_name]++;
    }

    for (const auto& item : fruit_count)
    {
        cout << item.first << ":" << item.second << endl;
    }
    return 0;
}

実行結果：

コード改善後の結果も正しく、最初の方法よりずっと簡潔です！

では、operator[]とは一体何者でしょうか？ドキュメントで分析できます：

パラメータと戻り値型に注目してください。このoperator[]はこれまで認識していた添え字アクセスではありません。キーkeyを通じて値valueの参照を返します！

では、どのようにして値を見つけ、変更できるのでしょうか？

ドキュメントは同じく答えを提供しており、operator[]は以下の長いコードと同等です

このような長いコードには落ち着いて内側から外側へ分析する必要があります

したがって、insertの戻り値を研究する必要があります

簡単な翻訳：

insertはpair構造を返し、このpairのfirstはイテレータとして設定されます。イテレータの指し示す場所は2つのケースがあります：

1. キーkeyが既に木にある場合、木の中のkeyがあるノードのイテレータを返します
2. キーkeyが木にない場合、新しく挿入されたkeyがあるノードのイテレータを返します

したがって、(this->insert(make_pair(k,mapped_type()))の戻り値はpair<iterator, bool>

次に逆参照して.firstでイテレータが指すノードを取得し、最後の.secondでノードの値valueを取得します。

したがって、[]はキーkeyを通じて値valueを変更できます。

上記の長いコードは以下のように分解できます：

template<class K, class V>
V &operator[](const K &key_value)
{
    pair<iterator, bool> result = insert(make_pair(key_value, V()));
    return result.first->second;
}

multimap

multimapでは複数の重複キーの出現を許可します。したがって、operator[]は呼び出し者の意図を確認できず、どのキーに対応するノードを返すべきか分かりません。そのためmultimapにはoperator[]が提供されていません。もちろん他の操作はmapと同じです。

他には：findで検索する場合、中間順序走査で最初に出現する要素のイテレータを返します。またcountは現在のキーの数を返します。

mapを習得すれば十分で、multimapはほとんど使用されません。

積集合と差集合

7.1 積集合の求め方

積集合とは、2つの配列で共通する要素から構成される集合のことです。

積集合を求める手順：

1. まず2つの配列をソート+重複除去します。setコンテナを使用できます
2. 2つのsetコンテナを走査し、等しければ積集合要素であり、同時に++します。等しくなければ、小さい方に++します
3. 片方が終了すれば、すべての積集合が求められます

7.2 差集合の求め方

集合Aと集合Bにおいて、集合Aに属するが集合Bに属さない要素から構成される集合を、集合Aと集合Bの差集合といいます。例えば、集合A = {1, 2, 3}、集合B = {2, 3, 4}の場合、差集合は{1}です。

差集合を求める手順：

1. まず2つの配列をソート+重複除去します
2. 2つのコンテナを走査します。等しければ同時++、等しくなければ小さい方を記録してから++
3. 片方が終了すれば、すべての差集合が求められます