概要

ツリーはデータを階層的に扱うデータ構造です。各ノードの子ノードが最大二つしか存在しないことが保証されているツリーを特に二分木とよびます。データ構造である二分木に新たな要素ノードを追加する際の規則を工夫することで、要素の検索を二分探索で実行できるようになります。この場合の二分木を特に二分探索木とよびます。二分探索木に対し、ソートされた要素を順番に追加すると性能が極端に悪くなってしまいます。これは二分探索木の中でも特殊な平衡二分探索木を使用することで回避できます。

二分探索木の要素ノードには key と value の二つの属性を備えることができます。key のみが備えられた二分探索木を集合 set とよびます。key と value の両方が備えられた二分探索木を連想配列 map とよびます。

連想配列 map

#include <iostream>
#include <map>
using namespace std;

int main() {
    map<string, int> m;
    multimap<string, int> mm; // キーの重複が許される連想配列

    // 値の追加
    m["one"] = 1;
    m["two"] = 2;
    m.insert( map<string, int>::value_type("two", 2) ); // としても同じ
    cout << m.size() << endl; //=> 2 (キーの重複が許されなかったため 3 とはならない)

    // multimap の場合は重複可能性があるため [] 演算子は使用できません
    mm.insert( multimap<string, int>::value_type("one", 1) );
    mm.insert( multimap<string, int>::value_type("one", -1) );
    cout << mm.size() << endl; //=> 2


    // 値の参照
    cout << m["one"] << endl; //=> 1
    for(map<string, int>::iterator it = m.begin(), end = m.end(); it != end; ++it) {
        cout << it->first << ": " << it->second << endl; //=> one: 1
    }                                                    //   two: 2

    for(multimap<string, int>::iterator it = mm.begin(), end = mm.end(); it != end; ++it) {
        cout << it->first << ": " << it->second << endl; //=> one: 1
    }                                                    //   one: -1

    // 該当キーの要素数
    cout << m.count("one") << endl; //=> 1
    cout << mm.count("one") << endl; //=> 2


    // 値の検索
    map<string, int>::iterator it = m.find("one");
    if ( it != m.end() ) { // 見つからなければ m.end() が返されます
        cout << "found: (" << it->first << ", " << it->second << ")" << endl; //=> found: (one, 1)
    }

    multimap<string, int>::iterator it_ = mm.find("one");
    if ( it_ != mm.end() ) {
        cout << "found" << endl; //=> found
    }

    // 値の削除
    cout << m.erase("one") << endl; //=> 1 (削除された要素数)
    cout << m.erase("not_exist") << endl; //=> 0 (存在しない要素の場合)
    cout << m.size() << endl; //=> 1

    cout << mm.erase("one") << endl; //=> 2
    cout << mm.size() << endl; //=> 0

    // 全削除
    m.clear();
    mm.clear();
    cout << boolalpha
         << m.empty() << endl //=> true
         << mm.empty() << endl; //=> true

    return 0;
}

集合 set

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

int main() {
    set<int> s;
    multiset<int> ms; // 重複が許される集合

    // 要素の追加
    s.insert( set<int>::value_type(0) );
    s.insert( set<int>::value_type(0) );
    cout << s.size() << endl; //=> 1 (キーの重複が許されなかったため 2 とはならない)

    ms.insert( multiset<int>::value_type(0) );
    ms.insert( multiset<int>::value_type(0) );
    cout << ms.size() << endl; //=> 2

    // 要素の列挙
    for(set<int>::iterator it = s.begin(), end = s.end(); it != end; ++it) {
        cout << *it << endl; //=> 0
    }

    for(multiset<int>::iterator it = ms.begin(), end = ms.end(); it != end; ++it) {
        cout << *it << endl; //=> 0
    }                       //    0

    // 該当キーの要素数
    cout << s.count(0) << endl; //=> 1
    cout << ms.count(0) << endl; //=> 2

    // 値の検索
    set<int>::iterator it = s.find(0);
    if ( it != s.end() ) { // 見つからなければ s.end() が返されます
        cout << "found: " << *it << endl; //=> found: 0
    }
    multiset<int>::iterator it_ = ms.find(0);
    if ( it_ != ms.end() ) {
        cout << "found: " << *it_ << endl; //=> found: 0
    }

    // 値の削除
    cout << s.erase(0) << endl; //=> 1 (削除された要素数)
    cout << s.erase(-1) << endl; //=> 0 (存在しない要素の場合)
    cout << s.size() << endl; //=> 0

    cout << ms.erase(0) << endl; //=> 2
    cout << ms.size() << endl; //=> 0

    // 全削除
    s.clear();
    ms.clear();
    cout << boolalpha
         << s.empty() << endl //=> true
         << ms.empty() << endl; //=> true

    return 0;
}