set

[C++] std::setを使わない方が良い場面と代替STLの紹介

2025-01-18更新日: 2025-01-18

std::setは二分探索木を基盤としたデータ構造で、要素の挿入・削除・検索が平均で $O (\log n)$ の計算量を持ちます。

しかし、頻繁な挿入や削除が不要で、単純な検索や順序を考慮しない場合、std::setはオーバーヘッドが大きく非効率です。

このような場合、std::unordered_set(ハッシュテーブルを基盤とし、平均計算量が $O (1)$ )が適しています。

また、順序が不要で重複を許容する場合はstd::vectorやstd::dequeを用い、std::sortやstd::uniqueで管理する方法もあります。

目次から探す

std::setを使わない方が良い場面
std::setの代替となるSTLコンテナ
- 各コンテナの使用例
適切なSTLコンテナを選択するための指針
まとめ

std::setを使わない方が良い場面

std::setは、要素を自動的にソートし、重複を許さないコンテナですが、特定の状況では他のコンテナを使用した方が効率的です。

以下のような場面では、std::setの使用を避けることを検討しましょう。

順序が不要な場合

要素の順序が重要でない場合、std::setを使用する必要はありません。
代わりに、std::unordered_setを使用することで、より高速な挿入や検索が可能です。

重複を許可する場合

重複を許可する必要がある場合、std::setは適していません。
この場合は、std::vectorやstd::unordered_setを使用することが考えられます。

頻繁な挿入・削除が必要な場合

std::setは、要素の挿入や削除がO(log n)の時間計算量で行われます。
頻繁に挿入や削除を行う場合、std::vectorやstd::dequeの方が効率的です。

メモリ使用量が問題となる場合

std::setは、内部で木構造を使用しているため、メモリのオーバーヘッドが大きくなります。
メモリ使用量を抑えたい場合は、std::vectorやstd::unordered_setを検討しましょう。

特定の順序でのアクセスが必要な場合

特定の順序で要素にアクセスする必要がある場合、std::setは適していません。
std::vectorやstd::dequeを使用することで、インデックスを使ったアクセスが可能です。

これらの場面では、std::setの特性が逆にデメリットとなることがあります。

状況に応じて適切なコンテナを選択することが重要です。

std::setの代替となるSTLコンテナ

std::setの代替として使用できるSTLコンテナはいくつかあります。

それぞれの特性を理解し、用途に応じて選択することが重要です。

以下に、std::setの代替となる主なSTLコンテナを紹介します。

コンテナ名	特徴	使用例
`std::unordered_set`	– ハッシュテーブルを使用し、要素の順序は保証されない – 挿入・検索が平均O(1)の時間計算量	重複を許可せず、高速な検索が必要な場合
`std::vector`	– 動的配列で、要素の順序が保持される – 挿入・削除はO(n)だが、インデックスアクセスがO(1)	順序が重要で、重複を許可する場合
`std::deque`	– 両端からの挿入・削除が効率的 – 要素の順序が保持される	頻繁に両端からの操作が必要な場合
`std::multiset`	– 重複を許可するが、要素は自動的にソートされる – 挿入・削除はO(log n)	重複を許可し、順序が必要な場合
`std::list`	– 双方向リストで、挿入・削除がO(1)で行える – 要素の順序が保持される	頻繁な挿入・削除が必要な場合

各コンテナの使用例

std::unordered_setの使用例

#include <iostream>
#include <unordered_set>
int main() {
    std::unordered_set<int> mySet;
    mySet.insert(1); // 要素を挿入
    mySet.insert(2);
    mySet.insert(3);
    // 要素の存在確認
    if (mySet.find(2) != mySet.end()) {
        std::cout << "2はセットに存在します。" << std::endl;
    }
    return 0;
}

2はセットに存在します。

std::vectorの使用例

#include <iostream>
#include <vector>
int main() {
    std::vector<int> myVector;
    myVector.push_back(1); // 要素を追加
    myVector.push_back(2);
    myVector.push_back(3);
    // 要素の表示
    for (int num : myVector) {
        std::cout << num << " "; // 要素を表示
    }
    std::cout << std::endl;
    return 0;
}