C++のmultisetの使い方

programming contest C++

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

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

(2021-09-05追記: 計算量に誤りがあったので修正)

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、ms中の値5の要素数をMとしてO(log N + M)の時間がかかる (参考 ) ので要注意です。msの全要素が5であるような最悪の場合、M=NなのでO(N)かかってしまうことになります。したがって、値の有無を調べるためだけにcount()メソッドを使ってはいけません。値の有無を調べるにはfind()を使いましょう。find()であれば計算量は O(log N) です。 (参考)

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);
}

参考