[c++] set/map で最大/最小値を求める

Motivation

set および map のデータ構造で、複数のクエリにより継続的にデータ集合が変わる場面において、各状態の集合に対して高速に最大値/最小値を求める方法について書き記す。

Experiment

std::max_element を用いた方法と、std::set:rbegin を用いた2種類の方法で、集合の最大値を求める。
処理内容は、以下の通り。

1. 集合にデータを投入する。(N = 10,000)
2. N 回のクエリを実行する。
   2.1. 集合の最大値を取得する。
   2.2. その値を表示する。
   2.3. これを集合から削除する。
3. 2 に要した時間を計測、表示する。

max_element を使用した場合 → 計算量 O(N)

max_element についてはこちらを参照。

#include <stdio.h>
#include <stdlib.h>
#include <bits/stdc++.h>
using namespace std;
using namespace std::chrono;

int main(void){
	set<int> s;
    // 1. データ投入
	int n = 10000;
	for(int i = 0; i < n; i++) {
		s.insert(i);
	}

	// 計測開始
	auto start = high_resolution_clock::now();

	int num_of_loops = n;
	while(num_of_loops--) {
		// 2.1. 最大値を取得
		int max = *max_element(s.begin(), s.end());

        // 2.2. 表示する。表示は省略
        // cout << "max:" << max << endl;

		// 最大値を削除
		s.erase(max);
	}
	// 計測終了
	auto stop = high_resolution_clock::now();
	auto duration = duration_cast<milliseconds>(stop - start);

    // 3. 計測時間の表示
	cout << "It took " << duration.count() << " ms." << endl;
}

これを10回行った結果の平均値は 1724ms であった。

rbegin を使用した場合 → 計算量 O(1)

rbegin についてはこちらを参照。

#include <stdio.h>
#include <stdlib.h>
#include <bits/stdc++.h>
using namespace std;
using namespace std::chrono;

int main(void){
	set<int> s;
    // 1. データ投入
	int n = 10000;
	for(int i = 0; i < n; i++) {
		s.insert(i);
	}

	// 計測開始
	auto start = high_resolution_clock::now();

	int num_of_loops = n;
	while(num_of_loops--) {
		// 2.1. 最大値を取得
		int max = *s.rbegin();

        // 2.2. 表示する。表示は省略
        // cout << "max:" << max << endl;

		// 最大値を削除
		s.erase(max);
	}
	// 計測終了
	auto stop = high_resolution_clock::now();
	auto duration = duration_cast<milliseconds>(stop - start);

    // 3. 計測時間の表示
	cout << "It took " << duration.count() << " ms." << endl;
}

これを10回行った結果の平均値は 6ms であった。
今回のケースでは、286倍の短縮に繋がったことになる。

また、最小値の場合も

• max_element → min_element
• rbegin → begin

に対応しているため、最小値を取得する箇所で、int max = *s.begin() とすることで O(1) での処理が可能である。

map でも同じ。

この場合、begin や rbegin によって返されるのがイテレータであるが、同様のロジックが適用される。

Conclusion

set や map の最大/最小値取得には、rbegin/beginを使うべし。