multiset

[C++] multisetの使い方についてわかりやすく詳しく解説

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

C++のmultisetは、重複を許容するソート済みの集合を管理するコンテナです。

要素は自動的に昇順にソートされ、同じ値を複数回格納できます。

主な操作として、insertで要素を追加し、eraseで特定の値を削除、countで特定の値の出現回数を取得できます。

また、findで特定の値を検索し、lower_boundやupper_boundで範囲を取得可能です。

目次から探す

multisetとは何か

C++のmultisetは、標準ライブラリに含まれる連想コンテナの一つで、要素を自動的にソートし、重複を許可する特性を持っています。

multisetは、要素の挿入、削除、検索を効率的に行うことができ、特に重複したデータを扱う際に便利です。

以下に、multisetの主な特徴を示します。

特徴	説明
自動ソート	要素が挿入されると、自動的にソートされる
重複要素の許可	同じ値の要素を複数持つことができる
高速な検索	要素の検索が効率的に行える

multisetは、特にデータの頻度を管理したり、特定の条件に基づいてデータを集計したりする場合に役立ちます。

次のセクションでは、multisetの基本操作について詳しく見ていきます。

multisetの基本操作

multisetの基本操作には、要素の挿入、削除、検索、イテレーションなどがあります。

これらの操作は、multisetの特性を活かして効率的に行うことができます。

以下に、各操作の具体的な使い方を示します。

要素の挿入

multisetに要素を挿入するには、insertメソッドを使用します。

以下のサンプルコードでは、整数を持つmultisetを作成し、いくつかの要素を挿入しています。

#include <iostream>
#include <set>
int main() {
    std::multiset<int> myMultiset; // multisetの宣言
    // 要素の挿入
    myMultiset.insert(5); // 5を挿入
    myMultiset.insert(3); // 3を挿入
    myMultiset.insert(5); // 再度5を挿入(重複を許可)
    myMultiset.insert(1); // 1を挿入
    // 挿入後の要素を表示
    for (const auto& elem : myMultiset) {
        std::cout << elem << " "; // 要素を表示
    }
    std::cout << std::endl; // 改行
    return 0;
}

1 3 5 5

要素の削除

multisetから要素を削除するには、eraseメソッドを使用します。

特定の値を持つ要素をすべて削除することができます。

以下のサンプルコードでは、5を削除しています。

#include <iostream>
#include <set>
int main() {
    std::multiset<int> myMultiset = {1, 3, 5, 5}; // 初期化
    // 要素の削除
    myMultiset.erase(5); // すべての5を削除
    // 削除後の要素を表示
    for (const auto& elem : myMultiset) {
        std::cout << elem << " "; // 要素を表示
    }
    std::cout << std::endl; // 改行
    return 0;
}

1 3

要素の検索

multiset内の要素を検索するには、countメソッドを使用します。

このメソッドは、指定した値の要素がいくつ存在するかを返します。

以下のサンプルコードでは、5の出現回数を確認しています。

#include <iostream>
#include <set>
int main() {
    std::multiset<int> myMultiset = {1, 3, 5, 5}; // 初期化
    // 要素の検索
    int count = myMultiset.count(5); // 5の出現回数を取得
    std::cout << "5の出現回数: " << count << std::endl; // 出現回数を表示
    return 0;
}

5の出現回数: 2

イテレーション

multisetの要素をイテレートするには、範囲ベースのforループを使用します。

上記のサンプルコードでも示したように、multisetの要素を簡単に表示することができます。

これらの基本操作を理解することで、multisetを効果的に活用できるようになります。

次のセクションでは、範囲操作とソートの仕組みについて詳しく見ていきます。

範囲操作とソートの仕組み

multisetは、要素を自動的にソートする特性を持っているため、範囲操作や特定の条件に基づく操作が非常に便利です。

このセクションでは、multisetの範囲操作とそのソートの仕組みについて詳しく解説します。

自動ソートの仕組み

multisetに要素を挿入すると、内部的に要素が自動的にソートされます。

これは、multisetがバランスの取れた木構造(通常は赤黒木)を使用しているためです。

このため、要素の挿入や削除が行われるたびに、全体の順序が保たれます。

以下のサンプルコードでは、要素を挿入した後のmultisetの状態を確認します。

#include <iostream>
#include <set>
int main() {
    std::multiset<int> myMultiset; // multisetの宣言
    // 要素の挿入
    myMultiset.insert(4);
    myMultiset.insert(1);
    myMultiset.insert(3);
    myMultiset.insert(2);
    // 挿入後の要素を表示
    for (const auto& elem : myMultiset) {
        std::cout << elem << " "; // 要素を表示
    }
    std::cout << std::endl; // 改行
    return 0;
}

1 2 3 4

範囲操作

multisetでは、特定の範囲の要素を取得することができます。

lower_boundとupper_boundメソッドを使用することで、指定した値に基づく範囲を取得できます。

以下のサンプルコードでは、3以上の要素を取得しています。

#include <iostream>
#include <set>
int main() {
    std::multiset<int> myMultiset = {1, 2, 3, 4, 5}; // 初期化
    // 範囲操作
    auto lower = myMultiset.lower_bound(3); // 3以上の最初の要素を取得
    auto upper = myMultiset.upper_bound(5); // 5以上の最初の要素を取得
    // 範囲内の要素を表示
    std::cout << "3以上の要素: ";
    for (auto it = lower; it != upper; ++it) {
        std::cout << *it << " "; // 要素を表示
    }
    std::cout << std::endl; // 改行
    return 0;
}

3以上の要素: 3 4 5

ソートのカスタマイズ

multisetでは、要素のソート順をカスタマイズすることも可能です。

デフォルトでは、要素は昇順にソートされますが、比較関数を指定することで、降順やその他の条件に基づくソートができます。

以下のサンプルコードでは、降順にソートされたmultisetを作成しています。

#include <iostream>
#include <set>
int main() {
    // 降順でソートするための比較関数
    auto cmp = [](int a, int b) { return a > b; };
    std::multiset<int, decltype(cmp)> myMultiset(cmp); // multisetの宣言
    // 要素の挿入
    myMultiset.insert(4);
    myMultiset.insert(1);
    myMultiset.insert(3);
    myMultiset.insert(2);
    // 挿入後の要素を表示
    for (const auto& elem : myMultiset) {
        std::cout << elem << " "; // 要素を表示
    }
    std::cout << std::endl; // 改行
    return 0;
}

4 3 2 1

これらの機能を活用することで、multisetを使ったデータ管理がより柔軟かつ効率的になります。

次のセクションでは、multisetの応用的な使い方について詳しく見ていきます。

応用的な使い方

multisetは、基本的な操作に加えて、さまざまな応用的な使い方が可能です。

このセクションでは、multisetを活用した具体的なシナリオや、実際の問題解決に役立つテクニックを紹介します。

頻度カウント

multisetは、要素の頻度を簡単にカウントするのに適しています。

特定のデータがどれだけ出現するかを把握するために、countメソッドを利用することができます。

以下のサンプルコードでは、文字列の頻度をカウントしています。

#include <iostream>
#include <set>
#include <string>
int main() {
    std::multiset<std::string> myMultiset; // multisetの宣言
    // 要素の挿入
    myMultiset.insert("apple");
    myMultiset.insert("banana");
    myMultiset.insert("apple");
    myMultiset.insert("orange");
    myMultiset.insert("banana");
    // 各要素の頻度を表示
    for (const auto& fruit : {"apple", "banana", "orange"}) {
        std::cout << fruit << "の出現回数: " << myMultiset.count(fruit) << std::endl; // 出現回数を表示
    }
    return 0;
}

appleの出現回数: 2
bananaの出現回数: 2
orangeの出現回数: 1

重複データの管理

multisetは、重複データを管理するのに非常に便利です。

例えば、同じ値を持つデータを集約したり、特定の条件に基づいてデータをフィルタリングしたりすることができます。

以下のサンプルコードでは、重複データを持つ整数のリストから、ユニークな値を取得しています。

#include <iostream>
#include <set>
#include <vector>
int main() {
    std::vector<int> numbers = {1, 2, 2, 3, 4, 4, 4, 5}; // 重複データを含むリスト
    std::multiset<int> myMultiset(numbers.begin(), numbers.end()); // multisetの初期化
    // ユニークな値を表示
    std::cout << "ユニークな値: ";
    for (const auto& num : myMultiset) {
        std::cout << num << " "; // 要素を表示
    }
    std::cout << std::endl; // 改行
    return 0;
}

ユニークな値: 1 2 2 3 4 4 4 5

複雑なデータ構造の管理

multisetは、カスタムデータ型を扱うこともできます。

例えば、構造体やクラスを使用して、特定の条件に基づいてデータをソートすることができます。

以下のサンプルコードでは、Personという構造体を定義し、年齢でソートされたmultisetを作成しています。

#include <iostream>
#include <set>
#include <string>
struct Person {
    std::string name;
    int age;
    // 年齢でソートするための比較関数
    bool operator<(const Person& other) const {
        return age < other.age; // 年齢で比較
    }
};
int main() {
    std::multiset<Person> people; // multisetの宣言
    // 要素の挿入
    people.insert({"Alice", 30});
    people.insert({"Bob", 25});
    people.insert({"Charlie", 35});
    people.insert({"David", 25});
    // 挿入後の要素を表示
    for (const auto& person : people) {
        std::cout << person.name << " (" << person.age << "歳)" << std::endl; // 要素を表示
    }
    return 0;
}

Bob (25歳)
David (25歳)
Alice (30歳)
Charlie (35歳)

統計的なデータ分析

multisetを使用することで、データの統計的な分析を行うことも可能です。

例えば、中央値や最頻値を計算する際に、multisetの特性を活かすことができます。

以下のサンプルコードでは、中央値を計算する方法を示しています。

#include <iostream>
#include <set>
#include <vector>
double calculateMedian(std::multiset<int>& myMultiset) {
    auto it = myMultiset.begin();
    std::advance(it, myMultiset.size() / 2); // 中央の位置を取得
    if (myMultiset.size() % 2 == 0) {
        auto itPrev = std::prev(it); // 前の要素を取得
        return (*it + *itPrev) / 2.0; // 中央値を計算
    } else {
        return *it; // 中央値を返す
    }
}
int main() {
    std::multiset<int> myMultiset = {1, 2, 3, 4, 5}; // 初期化
    // 中央値を計算
    double median = calculateMedian(myMultiset);
    std::cout << "中央値: " << median << std::endl; // 中央値を表示
    return 0;
}

中央値: 3

これらの応用的な使い方を理解することで、multisetをより効果的に活用し、さまざまな問題を解決することができるようになります。

次のセクションでは、multisetのパフォーマンスと注意点について詳しく見ていきます。

パフォーマンスと注意点

multisetは、データの管理や操作において非常に便利ですが、使用する際にはパフォーマンスや注意点を理解しておくことが重要です。

このセクションでは、multisetのパフォーマンス特性と、使用時の注意点について解説します。

パフォーマンス特性

multisetは、内部的にバランスの取れた木構造(通常は赤黒木)を使用しているため、以下のようなパフォーマンス特性を持っています。

操作	時間計算量
要素の挿入	O(log n)
要素の削除	O(log n)
要素の検索	O(log n)
順序付けされた要素のイテレーション	O(n)

このように、multisetは要素の挿入、削除、検索が効率的に行えるため、大量のデータを扱う際にもパフォーマンスが良好です。

ただし、要素の数が増えると、操作にかかる時間も増加するため、注意が必要です。

メモリ使用量

multisetは、要素を格納するために追加のメモリを使用します。

特に、重複要素を多く持つ場合、メモリの使用量が増加します。

メモリ使用量が問題となる場合は、他のデータ構造(例えば、unordered_multiset)を検討することも一つの手です。

注意点

重複要素の管理: multisetは重複要素を許可しますが、重複要素の管理が必要な場合は、適切にカウントや削除を行う必要があります。

特に、重複要素を削除する際には、意図しない結果を避けるために注意が必要です。

カスタム比較関数: カスタムデータ型を使用する場合、適切な比較関数を定義することが重要です。

比較関数が正しくないと、要素の順序が意図しないものになる可能性があります。

スレッドセーフではない: multisetはスレッドセーフではありません。

複数のスレッドから同時にアクセスする場合は、適切なロック機構を使用する必要があります。

イテレーションの注意: multisetの要素をイテレートする際、要素の削除や挿入を行うと、イテレータが無効になることがあります。

イテレーション中にデータ構造を変更する場合は、注意が必要です。

これらのパフォーマンス特性や注意点を理解することで、multisetを効果的に活用し、適切なデータ管理を行うことができるようになります。

次のセクションでは、multisetを使った実践例を紹介します。

実践例：multisetを使った問題解決

このセクションでは、multisetを活用した具体的な問題解決の例をいくつか紹介します。

これにより、multisetの実用性や効果的な使い方を理解することができます。

例1: 数字の頻度をカウントして最頻値を求める

与えられた整数のリストから、最も頻繁に出現する数字(最頻値)を求める問題を考えます。

multisetを使用することで、各数字の出現回数を簡単に管理できます。

以下のサンプルコードでは、最頻値を求める方法を示しています。

#include <iostream>
#include <set>
#include <vector>
#include <algorithm>
int main() {
    std::vector<int> numbers = {1, 3, 2, 3, 4, 2, 1, 3}; // 入力データ
    std::multiset<int> frequencySet; // 出現頻度を管理するmultiset
    // 各数字の出現頻度をカウント
    for (int num : numbers) {
        frequencySet.insert(num); // multisetに挿入
    }
    // 最頻値を求める
    int maxCount = 0;
    int mode = 0;
    for (const auto& num : frequencySet) {
        int count = frequencySet.count(num); // 出現回数を取得
        if (count > maxCount) {
            maxCount = count; // 最大出現回数を更新
            mode = num; // 最頻値を更新
        }
    }
    std::cout << "最頻値: " << mode << " (出現回数: " << maxCount << ")" << std::endl; // 結果を表示
    return 0;
}

最頻値: 3 (出現回数: 3)

例2: スコアの管理と中央値の計算

学生のテストスコアを管理し、中央値を計算する問題を考えます。

multisetを使用することで、スコアを自動的にソートし、中央値を簡単に求めることができます。

以下のサンプルコードでは、スコアの追加と中央値の計算を行っています。

#include <iostream>
#include <set>
double calculateMedian(std::multiset<int>& scores) {
    auto it = scores.begin();
    std::advance(it, scores.size() / 2); // 中央の位置を取得
    if (scores.size() % 2 == 0) {
        auto itPrev = std::prev(it); // 前の要素を取得
        return (*it + *itPrev) / 2.0; // 中央値を計算
    } else {
        return *it; // 中央値を返す
    }
}
int main() {
    std::multiset<int> scores; // スコアを管理するmultiset
    // スコアの追加
    scores.insert(85);
    scores.insert(90);
    scores.insert(78);
    scores.insert(92);
    scores.insert(88);
    // 中央値を計算
    double median = calculateMedian(scores);
    std::cout << "中央値: " << median << std::endl; // 結果を表示
    return 0;
}

中央値: 88

例3: 重複データのフィルタリング

重複したデータを持つリストからユニークな値を取得する問題を考えます。

multisetを使用することで、重複を自動的に管理し、ユニークな値を簡単に取得できます。

以下のサンプルコードでは、重複データをフィルタリングしています。

#include <iostream>
#include <set>
#include <vector>
int main() {
    std::vector<int> numbers = {1, 2, 2, 3, 4, 4, 4, 5}; // 重複データを含むリスト
    std::multiset<int> uniqueSet(numbers.begin(), numbers.end()); // multisetの初期化
    // ユニークな値を表示
    std::cout << "ユニークな値: ";
    for (const auto& num : uniqueSet) {
        std::cout << num << " "; // 要素を表示
    }
    std::cout << std::endl; // 改行
    return 0;
}