C++のmultisetの使い方


このエントリーをはてなブックマークに追加

競技プログラミングC++のmultisetをたまに使うことがありますが、毎回使い方を忘れているのでメモしておきます。

multisetとは

multisetは、集合を扱うデータ構造です。setと異なり、同じ値の要素を複数持つことができます。#include <set>すれば使えます。さっそく例を示します。

#include <iostream>
#include <set>

void print_multiset(std::multiset<int>& ms) {
    for (auto val: ms) {
        std::cout << val << ", ";
    }
    std::cout << std::endl;
}

int main(void)
{
    std::multiset<int> ms;
    ms.insert(7);
    ms.insert(5);
    ms.insert(2);
    ms.insert(7);
    ms.insert(5);

    print_multiset(ms);
    return 0;
}

とすると、

2, 5, 5, 7, 7,

が表示されます。つまり、変数msに、5つの値が順序付きで登録されていることがわかります。以下では、このように変数msを生成したとしてmultisetの使用例を説明します。

素数を調べる

例えばmsの中に値5を持つ要素が何個含まれているかを調べるには、以下のようにします。

ms.count(5);  // 2と表示される

ただしこれの実行には、要素数をNとしてO(log N)の時間がかかるので要注意です。値の有無を調べるためだけにcount()メソッドを使ってはいけません。値の有無を調べるにはfind()を使いましょう。

if (ms.find(5) == ms.end()) {
    // 5が存在しない
} else {
    // 5が存在する
}

ある値をもつ要素を全部消す

例えばmsから値5を持つ要素を 全部 消すには、以下のようにします。

ms.erase(5);

ms.erase()は何個の要素を消したかも返すので、もし

auto n = ms.erase(5);

とすると、nには2が入ります。

ms.erase(42);などと存在しない値を消そうとしてもエラーにはなりません。

ある値をもつ要素を1つ消す

例えばmsから値5を持つ要素を 1つだけ 消すには、面倒ですがイテレータを介する必要があります。

ms.erase(ms.find(5));

とすると、msの持つ要素は2, 5, 7, 7となり、5が1個だけ消えます。

msの中にない要素を消そうとするときには要注意です。 もし

ms.erase(ms.find(42));

としてしまうと、実行時に以下のエラーで死にます。

zsh: abort (core dumped)  ./a.exe

なので、以下のように、値がmsの中に存在することがわかっている場合のみ消すようにすると安全です。

auto it = ms.find(42);
if (it != ms.end()) {
    ms.erase(it);
}

参考