セット(Set)・集合のデータ構造

2019年11月27日2020年3月21日データ構造集合,データ構造,set

Setとは、数学における集合をデータ構造として表したものです。順序はなく、変更可能で、重複した要素を持ちません。

要素の挿入・削除・検索を高速に行うことができる特徴があります。

プログラム例

Pythonの例

Pythonでは標準でset型が容易されていて、{}を使って表現できます。

# setの定義
set = {6,11,49,2,8,8,8,6}
print(set)       # 出力 {2, 6, 8, 11, 49}
print(type(set)) # 出力 <class 'set'>
# 要素を加える
set.add(3)
set.add(3)
print(set)　　　　# 3は重複しない {2, 3, 6, 8, 11, 49}

C++の例

C++ ではライブラリで set が提供されています。

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

int main() {
    // set はデータの追加・削除・検索の処理速度がO(log N)
    set<int> s;

    // 要素を加える
    s.insert(6);
    s.insert(11);
    s.insert(49);
    s.insert(2);
    s.insert(8);
    s.insert(8);
    s.insert(8);
    s.insert(6);
    s.insert(3);
    s.insert(3);

    for (auto itr = s.begin(); itr != s.end(); ++itr) { // 出力は 2 3 6 8 11 49
        cout << *itr << " ";                            // データを出力
    }

    cout << "\n";

    return 0;
}