STL/集合と連想配列 (C++をもう一度)
[履歴] [最終更新] (2014/12/28 08:51:42)
最近の投稿
注目の記事

概要

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

二分探索木の要素ノードには 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;
}
関連ページ
    概要 暗号技術で有名な MD5 や SHA-1, SHA-2 (SHA-256など) はハッシュ関数です。ハッシュ関数はある集合 A から別のある集合 B への写像関数のようなもので、集合 A の要素 a を入力として実行すると集合 B の要素 b が出力されます。このとき要素 b のことを要素 a のハッシュ値とよびます。また、集合 A の要素と集合 B の要素の対応表をハッシュ表とよびます。
    概要 限られた時間の中で問題を解くために必要となる、競技プログラミングにおける基本的な処理のチートシートです。競プロにおけるメジャー言語 C++ を利用します。その際 C++11 の機能は利用せず C++03 の機能の範囲内で記述します。 頻度高く定期的に開催されるコンテスト AtCoder Codeforces