C++編【標準ライブラリ】 第8章 set と multiset

この章の概要

この章の概要です。

set と multiset

set および multisetは、 STLコンテナの一種で、ソートされた集合を提供します。 set は、同じキーを持ったデータが重複することを許さず、multiset は許すという違いがあります。 キーというのは、ソートの条件に使用する値のことを指しています。
以降、set と multiset のいずれにも当てはまる事項は、set/multiset と記述します。

set/multiset のいずれも、使用するには、set という名前の標準ヘッダをインクルードする必要があります。

set/multiset は、 内部的には木構造(特に、赤黒木のような平衡木)になっているのが一般的です。

set/multiset は、要素がソート済みであることを利用して、検索を効率良く行えるという特性があります。 そのため、要素の検索を行う機会が多い場合に利用します。

set/multiset に格納された要素が持つキーを変更することは、原則としてできません。 勝手にキーが変更されてしまうと、ソート済みの状態を保つことができません。

正確に言えば、要素を指すイテレータを取得することもできるし、格納した要素へのポインタや参照をコンテナの外にも持っていれば、 それらを経由して、キーを書き換えることはできてしまいます。 しかし、そのようにして、ソート結果が変わってしまうような変更をした場合の動作は保証できません。

set と multiset はそれぞれ、次のように定義されています。

namespace std {
	template <typename T, typename Compare = less<T>, typename Allocator = allocator<T> >
	class set {
	};
}

namespace std {
	template <typename T, typename Compare = less<T>, typename Allocator = allocator<T> >
	class multiset {
	};
}

set/multiset はクラステンプレート(【言語解説】第20章)なので、使用時にはテンプレート引数の指定が必要です。 テンプレートパラメータ T は、動的配列の要素の型です。 例えば、int型の要素を扱う set は、以下のようになります。

std::set<int> intSet;

2つ目のテンプレートパラメータ Compare は、要素をソートする基準を定義するもので、デフォルトでは std::less(第19章)が指定されています。 これはつまり、要素の大小関係の比較に <演算子を用いることを意味しています。

もう1つのテンプレートパラメータ Allocator は、メモリ確保の方法を定義するアロケータと呼ばれるオブジェクトの指定です。 テンプレートパラメータ Allocator はデフォルト値を持っているので省略することができます。 多くの場合、省略しても list は活用できるので、本章では解説しません。 アロケータについては、第32章で改めて取り上げます。


なお、この章のサンプルは、特に断らない限り、set と multiset の違いは型だけです。

サイズ

set/multiset の中に実際に存在している要素数が「サイズ」です。

vector の場合、実際に確保された領域の大きさを指して「容量」という言葉があります。 set/multiset の場合も、内部に領域を確保していますが、set/multiset では「容量」を意識する必要はありません(調べることもできません)。

現在の「サイズ」を知るには、sizeメンバ関数を使います。 また、「サイズ」が 0 かどうかは、emptyメンバ関数で調べられます。
「サイズ」の最大値は max_sizeメンバ関数で取得できます。 戻り値の型は、set なら std::set<>::size_type型、multiset なら std::multiset<>::size_type型です。
この辺りは、他のコンテナと同様です。

使用例としては、次のようになります。

#include <iostream>
#include <set>

int main()
{
	std::set<int> intSet;

	for (int i = 0; i < 5; ++i) {
		intSet.insert(i);
	}

	std::cout << intSet.max_size() << "\n"
		<< intSet.size() << "\n"
		<< std::boolalpha << intSet.empty() << std::endl;
}

実行結果

214748364
5
false

生成

set/multiset には、複数のコンストラクタが定義されているので、様々な方法でインスタンス化できます。

int main()
{
	const int a[] = {0, 1, 2, 3, 4};

	std::set<int> set1;           // 空
	std::set<int> set2(set1);     // 他の set からコピー
	std::set<int> set3(a, a + 5); // イテレータで指定された範囲からコピー
}

set1、set3の方法の場合は、ソート基準と、アロケータを渡すデフォルト引数2つが隠されています。 ソート基準に関しては、後の項で改めて取り上げます。 アロケータについては、第32章まで扱いません。

C++11 (生成)

C++11 で、コンストラクタ周りは強化されています。 まず、std::initializer_list を使用できるようになりました。

int main()
{
	std::set<int> set4 {0, 1, 2};       // std::initializer_list
}

第2引数にはソート基準を、第3引数にはアロケータを指定することが可能です(それぞれデフォルト値を持っているので省略可)。

また、ムーブコンストラクタが追加されています。

int main()
{
	std::set<int> set5(std::move(set1));  // ムーブコンストラクタ
}

こちらは、第2引数にアロケータが指定できます。

また、これまでは、アロケータを指定する形式では、いつも間に、ソート基準を指定する引数が挟まれていましたが、 C++11 では、アロケータを指定する引数だけの形式が追加されています。

これらの追加されたコンストラクタは、VisualC++ 2013/2015/2017、clang 3.7 のいずれでも使用できます。

破棄

デストラクタでは、set/multiset が内部で確保した領域が破棄されます。

仮想デストラクタ(【言語解説】第27章)ではないので、 set/multiset を継承して使用することは不適切であることに注意して下さい

ソート基準

ソートの基準は、テンプレート引数で指定するか、コンストラクタの引数で指定します。

まず、テンプレート引数で指定する方法を見ていきましょう。

#include <iostream>
#include <set>
#include <functional>

typedef std::set<int> IntSet;
typedef std::set<int, std::greater<int> > IntReverseSet;

int main()
{
	const int a[] = { 0, 1, 2, 3, 4 };

	IntSet set1(a, a + 5);
	IntReverseSet set2(a, a + 5);

	const IntSet::const_iterator itEnd1 = set1.end();
	for (IntSet::const_iterator it1 = set1.begin(); it1 != itEnd1; ++it1) {
		std::cout << *it1 << " ";
	}
	std::cout << std::endl;

	const IntReverseSet::const_iterator itEnd2 = set2.end();
	for (IntReverseSet::const_iterator it2 = set2.begin(); it2 != itEnd2; ++it2) {
		std::cout << *it2 << " ";
	}
	std::cout << std::endl;
}

実行結果

0 1 2 3 4
4 3 2 1 0

typedef によって、2つの型の別名を定義しています。
IntSet の方は、ソート基準を定義していないので、デフォルト値 (std::less<>) が使用されます。 この場合、ソートには <演算子が使用されることになり、int型の要素達は昇順に並びます。
IntReverseSet の方は、ソート基準として std::greater<> を使用しました。 こちらは、ソートに >演算子を使用するので、要素は降順に並びます。

std::less<> や std::greater<> は、標準の関数オブジェクトで、 functional という標準ヘッダに定義されています。 関数オブジェクトについては、第19章で取り上げます。

2つの set は、共通の要素(配列a)で初期化されていますが、要素を順番に出力してみると、逆の順序に並ぶことが分かります。 (要素の出力処理のところで、std::set<>::const_iterator を使用しています。これは、「イテレータ」の項で説明しています)。

このように、ソート基準をテンプレート引数で指定する方法では、コンテナの型自体が異なったものになります。 そのため、型の不一致がコンパイラによって検出されます。これは利点でもあるし、不便さが生まれることもあります。 実際、型が違うため、要素を出力する部分の処理は、IntSet と IntReverseSet とで同じですが、 テンプレートを使わない普通の関数にまとめることができません。


次に、コンストラクタの引数で指定する方法です。

#include <iostream>
#include <set>

template <typename T>
class MyCompare {
public:
	enum Mode {
		MODE_NORMAL,
		MODE_REVERSE,
	};

public:
	explicit MyCompare(Mode mode = MODE_NORMAL) :
		mMode(mode)
	{}

	inline bool operator()(const T& a, const T& b) const
	{
		return mMode == MODE_NORMAL ? a < b : a > b;
	}

private:
	Mode	mMode;
};

typedef std::set<int, MyCompare<int> > IntSet;

void PrintIntSet(const IntSet& intSet)
{
	const IntSet::const_iterator itEnd = intSet.end();
	for (IntSet::const_iterator it = intSet.begin(); it != itEnd; ++it) {
		std::cout << *it << " ";
	}
	std::cout << std::endl;
}

int main()
{
	const int a[] = { 0, 1, 2, 3, 4 };

	IntSet set1(a, a + 5);
	IntSet set2(a, a + 5, MyCompare<int>(MyCompare<int>::MODE_REVERSE));

	PrintIntSet(set1);
	PrintIntSet(set2);
}

実行結果

0 1 2 3 4
4 3 2 1 0

この方法の場合は、ソート基準を表現する関数オブジェクトを独自で用意します。 ここで用意した MyCompare は、コンストラクタに渡す引数によって、ソートの方法を切り替えられるようになっています。
set/multiset の2つ目のテンプレートパラメータには、MyCompare を指定しています。 ソート基準は、コンストラクタで指定するので、set/multiset としては、1つの型で済みます。 実際、要素を出力する部分を、PrintIntSet関数にまとめることができています。

なお、MyCompare に、デフォルトコンストラクタ(【言語解説】第13章)が無いと、 set/multiset のコンストラクタで、必ず明示的にソート基準を指定しないといけなくなります。

要素のアクセス

set/multiset では、要素の追加や削除のたびにソートされるため、ランダムアクセスはできません。 また、シーケンスコンテナ(第4章)のように、frontメンバ関数や backメンバ関数もありません。

set/multiset で、要素へアクセスする方法は、大きく分けると2通りで、 「検索」を行うか、「イテレータ」を使うかです。 目的の要素の値を知っている状況ならば、findメンバ関数を使って「検索」するのが普通です。

どんな手段を使うにしても、set/multiset の要素が持つキーは書き換えてはならないという点に注意して下さい。 set/multiset は、要素の追加や削除が起きるたびに、ソート済みの状態を保つようになっていますが、 外部から勝手にキーを書き換えられると、ソート済みの状態が壊されてしまい、以降の処理が正しく動作する保証が無くなってしまいます。
また、multiset の場合には、要素の重複を許さないという特性まで失われる可能性があります。
どうしても、キーを書き換える必要がある場合は、 一旦、その要素を削除し、書き換えを行ってから、挿入し直すという手段を採ります。 要素を削除する方法は「削除」の項で、挿入する方法は「挿入」の項で説明します。

イテレータ

イテレータに関する詳細は、第14章で改めて取り上げますが、 ここでは、set/multiset におけるイテレータについて、簡単に紹介します。

他のコンテナと同様に、最初の要素を指すイテレータを beginメンバ関数で、 最後の要素の次を指すイテレータを endメンバ関数で取得できます。 また、逆方向に走査するための逆イテレータの場合に最初の要素を指すイテレータを rbeginメンバ関数で、 最後の要素の次を指すイテレータを rendメンバ関数で取得できます。

#include <iostream>
#include <set>

typedef std::set<int> IntSet;

int main()
{
	const int a[] = { 0, 1, 2, 3, 4 };

	IntSet iSet(a, a + 5);

	const IntSet::const_iterator itEnd = iSet.end();
	for (IntSet::const_iterator it = iSet.begin(); it != itEnd; ++it) {
		std::cout << *it << " ";
	}
	std::cout << std::endl;

	const IntSet::const_reverse_iterator ritEnd = iSet.rend();
	for (IntSet::const_reverse_iterator rit = iSet.rbegin(); rit != ritEnd; ++rit) {
		std::cout << *rit << " ";
	}
	std::cout << std::endl;
}

実行結果

0 1 2 3 4
4 3 2 1 0

beginメンバ関数や endメンバ関数で取得できるイテレータの型は、 std::set<>::iterator型、あるいはその const版である std::set<>::const_iterator型です。
また、rbeginメンバ関数、rendメンバ関数の場合は、 std::set<>::reverse_iterator型、あるいはその const版である std::set<>::const_reverse_iterator型になります。 (それぞれ、multiset の場合は、「set」を「multiset」に読み替えて下さい)。

これらイテレータの型は、set/multiset内部で typedef されているものですが、 その正体(typedef の元になる型) が何であるかは実装依存です。

vector等の場合と異なり、どの型のイテレータであっても、イテレータを通して要素のキーを書き換えてはならないことに注意して下さい。 ソート済みの状態を保つことや、multiset において要素の重複が無いことを保証することの妨げになるため、禁止されています。 このため、iterator と const_iterator、reverse_iterator と const_reverse_iterator との間には、実質的な違いはありません。

同じ理由で、要素を変更する STLアルゴリズム(第18章)に、イテレータを渡してもいけません。

実装によっては、イテレータを使って要素を書き換えようとするとコンパイルエラーになることがありますが、これは実装依存です。

C++11(const版のイテレータ取得関数)

C++11 には、必ず constイテレータを返す cbegin、cend、crbegin、crend の各メンバ関数が追加されています。

元々、begin、end、rbegin、rend の各メンバ関数は、非constイテレータを返すものと constイテレータを返すものとでオーバーロードされており、 constイテレータ型の変数で受け取れば、const版を使えました。
新たにこれらのメンバ関数が追加された意義は幾つかあると思いますが、 例えば、C++11 で追加された auto(【言語解説】第2章)を使いやすくすることが考えられます。

std::set<int> iSet;
auto it  = iSet.begin();   // こう書くと std::set<int>::iterator型
auto it2 = iSet.cbegin();  // こう書くと std::set<int>::const_iterator型

これらの追加されたメンバ関数は、VisualC++ 2013/2015/2017、clang 3.7 のいずれでも使用できます。

検索

set/multiset から、特定の要素を探し出すには、findメンバ関数を使います。

#include <iostream>
#include <set>

typedef std::set<int> IntSet;

int main()
{
	const int a[] = { 0, 1, 2, 3, 4 };

	IntSet iSet(a, a + 5);

	IntSet::iterator it = iSet.find(3);
	if (it != iSet.end()) {
		std::cout << "見つかりました" << std::endl;
	}
	else {
		std::cout << "見つかりません" << std::endl;
	}
}

実行結果

見つかりました

findメンバ関数は、引数で指定した値を持った、最初の要素を指すイテレータを返します。 発見できなかった場合は、endメンバ関数が返す結果と同じイテレータを返します。
イテレータを返すからといって、set/multiset の要素のキーを書き換えてはならないことに注意して下さい

find関数には、同名の STLアルゴリズムがありますが、set/multiset の場合にはメンバ関数版を使うようにして下さい。


countメンバ関数を使うと、指定の値を持った要素の数を調べることができます。 set の場合は要素の重複を許さないので、必ず 0 か 1 を返すはずです。

count関数には、同名の STLアルゴリズムがありますが、set/multiset の場合にはメンバ関数版を使うようにして下さい。

#include <iostream>
#include <set>

typedef std::set<int> IntSet;
typedef std::multiset<int> IntMultiSet;

int main()
{
	const int a1[] = { 1, 6, 4 };
	const int a2[] = { 1, 1, 6, 4, 4 };

	IntSet      iSet(a1, a1 + 3);
	IntMultiSet imSet(a2, a2 + 5);

	std::cout << iSet.count(4) << std::endl;
	std::cout << imSet.count(4) << std::endl;
}

実行結果

1
2


要素を挿入する適切な位置を調べる関数が3つあります。 それぞれ、lower_boundupper_boundequal_range といい、 要素を挿入できる最初の位置、最後の位置、最初と最後の位置を返します。
ちょっと意味が分かりにくいと思いますが、要するに、要素を再ソートする必要が無い挿入位置を教えてくれるということです。

これらの関数には、同名の STLアルゴリズムがありますが、set/multiset の場合にはメンバ関数版を使うようにして下さい。

lower_bound、upper_bound の場合、結果はイテレータで返されます。
equal_range の場合、結果は std::pair(第3章)で返されます。 equal_range の呼び出しは、「std::make_pair(s.lower_bound(), s.upper_bound())」と同じことです。

#include <iostream>
#include <set>
#include <iterator>

typedef std::set<int> IntSet;

void func(const IntSet& iSet, int value)
{
	std::cout << std::distance(iSet.begin(), iSet.lower_bound(value)) << std::endl;
	std::cout << std::distance(iSet.begin(), iSet.upper_bound(value)) << std::endl;

	std::pair<IntSet::iterator, IntSet::iterator> itPair = iSet.equal_range(value);
	std::cout << std::distance(iSet.begin(), itPair.first) << 
	      " " << std::distance(iSet.begin(), itPair.second) << std::endl;
}


int main()
{
	const int a[] = { 0, 2, 4, 6, 8 };

	IntSet iSet(a, a + 5);

	func(iSet, 5);
	func(iSet, 15);
}

実行結果

3
3
3 3
5
5
5 5

std::distance関数(第15章)を使って、先頭位置から、各関数が返した位置までの距離を調べています。

{0, 2, 4, 6, 8} が格納されている set に対して、5 を挿入できる位置を探すと、 lower_bound、upper_bound、equal_range のいずれを使っても、3 という結果が得られました。 先頭からの距離なので、6 という値が入っている場所を指すイテレータが返されたことが分かります。 イテレータと値を渡すタイプの insertメンバ関数に渡せば、{0, 2, 4, 5, 6, 8} になります。
一方、15 を挿入できる位置を探すと、5 という結果が得られました。 これは、末尾を超えたところです。 こちらも同様に、insertメンバ関数に渡せば、{0, 2, 4, 6, 8, 15} になります。

同じことを、multiset に対して行ってみます。 今度は、同じ要素が複数あります。

#include <iostream>
#include <set>
#include <iterator>

typedef std::multiset<int> IntSet;

void func(const IntSet& iSet, int value)
{
	std::cout << std::distance(iSet.begin(), iSet.lower_bound(value)) << std::endl;
	std::cout << std::distance(iSet.begin(), iSet.upper_bound(value)) << std::endl;

	std::pair<IntSet::iterator, IntSet::iterator> itPair = iSet.equal_range(value);
	std::cout << std::distance(iSet.begin(), itPair.first) << 
	      " " << std::distance(iSet.begin(), itPair.second) << std::endl;
}


int main()
{
	const int a[] = { 0, 2, 4, 4, 4, 5, 5, 5, 8, 8, 8 };

	IntSet iSet(a, a + 10);

	func(iSet, 5);
	func(iSet, 15);
}

実行結果

5
8
5 8
10
10
10 10

すでに、5 が 3つ入った状態で、5 を挿入できる位置を探すと、lower_bound と upper_bound とで異なる結果を返します。 lower_bound なら最初の位置である 5番目のところ、upper_bound なら最後の位置である 8番目のところを指すイテレータを返しています。 equal_range はこの組み合わせなので、5番目と 8番目を指すイテレータの pair になります。

このように、set が対象の場合は、要素に重複が無いため、適切な挿入位置はいつも1カ所に定まるので、 lower_bound、upper_bound、equal_range の結果は同じになります。
一方、multiset が対象の場合は、要素が重複していると、適切な挿入位置に範囲があるかも知れず、 異なる結果を返す可能性があります。

代入

set/multiset は、テンプレート引数が同一であれば、代入演算子を使ってコピーできます。
テンプレート引数が同一でなければならないので、ソート基準やアロケータが違うと代入することはできません。 ソート基準の違いに関しては、テンプレート引数は共通にしておき、コンストラクタの引数から指定することで回避できます。 詳細は、「ソート基準」の項を参照して下さい。

C++11 (std::initializer_list対応)

C++11 では、代入演算子の引数として、std::initializer_list を使えるようになりました。

#include <iostream>
#include <set>

typedef std::set<int> IntSet;

void PrintIntSet(const IntSet& intSet)
{
	const IntSet::const_iterator itEnd = intSet.end();
	for (IntSet::const_iterator it = intSet.begin(); it != itEnd; ++it) {
		std::cout << *it << " ";
	}
	std::cout << std::endl;
}

int main()
{
	IntSet iSet;
	iSet = { 0, 2, 4, 6, 8 };

	PrintIntSet(iSet);
}

実行結果

0 2 4 6 8

std::initializer_list は、VisualC++ 2013/2015/2017、clang 3.7 のいずれも対応しています。

C++11 (ムーブ代入演算子)

C++11 では、ムーブ代入演算子が追加されています。

#include <iostream>
#include <set>

typedef std::set<int> IntSet;

void PrintIntSet(const IntSet& intSet)
{
	const IntSet::const_iterator itEnd = intSet.end();
	for (IntSet::const_iterator it = intSet.begin(); it != itEnd; ++it) {
		std::cout << *it << " ";
	}
	std::cout << std::endl;
}

int main()
{
	IntSet iSet = { 0, 2, 4, 6, 8 };
	IntSet iSet2;

	iSet2 = std::move(iSet);

	PrintIntSet(iSet);
	PrintIntSet(iSet2);
}

実行結果


0 2 4 6 8

ムーブ代入演算子は、VisualC++ 2013/2015/2017、clang 3.7 のいずれでも使用できます。

挿入

要素を挿入する方法は、シーケンスコンテナとは少し違いがあります。
まず、push_back、pop_back のように、挿入位置を指定するものは存在しません。 set/multiset は、内部でソートを行うので、挿入位置を指定することに意味が無いためです。 insert はありますが、挿入位置は指定しないようになっています (オーバーロードの1形式だけは、イテレータを指定するものがありますが、意味合いが少し異なります)。

insertメンバ関数は、幾つかの形式が存在します。
1つ目は、挿入する要素だけを指定します。これが最も基本的な使い方になります。 set と multiset とでは、戻り値の形が異なるので、まずは set の例を挙げます。

#include <iostream>
#include <set>

typedef std::set<int> IntSet;

void InsertToIntSet(IntSet& intSet, int value)
{
	std::pair<IntSet::iterator, bool> result = intSet.insert(value);
	if (result.second) {
		std::cout << value << "を挿入しました。" << std::endl;
	}
	else {
		std::cout << value << "は挿入済みです。" << std::endl;
	}
}

void PrintIntSet(const IntSet& intSet)
{
	const IntSet::const_iterator itEnd = intSet.end();
	for (IntSet::const_iterator it = intSet.begin(); it != itEnd; ++it) {
		std::cout << *it << " ";
	}
	std::cout << std::endl;
}

int main()
{
	const int a[] = { 0, 2, 4, 6, 8 };

	IntSet iSet(a, a + 5);

	InsertToIntSet(iSet, 5);
	InsertToIntSet(iSet, 6);

	PrintIntSet(iSet);
}

実行結果

5を挿入しました。
6は挿入済みです。
0 2 4 5 6 8

set の場合、戻り値の型は std::pair で、firstメンバは std::set<>::iterator、secondメンバは bool です。
挿入が行われた場合、secondメンバが true になり、行われなかった場合は false になります。 挿入が行われない場合というのは、すでに set の中に、同じキーを持った要素が存在する場合です。
firstメンバの方は、挿入された要素、あるいはすでに存在していた要素を指すイテレータです。

次に multiset の場合です。

#include <iostream>
#include <set>
#include <iterator>

typedef std::multiset<int> IntMultiSet;

void InsertToIntSet(IntMultiSet& imSet, int value)
{
	IntMultiSet::iterator it = imSet.insert(value);
	std::cout << std::distance(imSet.begin(), it) << "番目の位置に" <<
	    value << "を挿入しました。" << std::endl;
}

void PrintIntSet(const IntMultiSet& imSet)
{
	const IntMultiSet::const_iterator itEnd = imSet.end();
	for (IntMultiSet::const_iterator it = imSet.begin(); it != itEnd; ++it) {
		std::cout << *it << " ";
	}
	std::cout << std::endl;
}

int main()
{
	const int a[] = { 0, 2, 4, 6, 8 };

	IntMultiSet imSet(a, a + 5);

	InsertToIntSet(imSet, 5);
	InsertToIntSet(imSet, 6);

	PrintIntSet(imSet);
}

実行結果

3番目の位置に5を挿入しました。
5番目の位置に6を挿入しました。
0 2 4 5 6 6 8

multiset の場合、戻り値の型は std::multiset<>::iterator です。
set と違い、multiset の insert は(例外が起こらなければ)必ず挿入されるので、 挿入された位置を返すだけになっています。


insertメンバ関数の2つ目の形式は、2つのイテレータを使って表現される範囲にある値をまとめて挿入します。 こちらは、戻り値が void型になっていて、set/multiset で違いはありません。 逆に言うと、set の場合に挿入されなかった要素があったかどうかを知ることはできません。

#include <iostream>
#include <set>

typedef std::set<int> IntSet;

void PrintIntSet(const IntSet& intSet)
{
	const IntSet::const_iterator itEnd = intSet.end();
	for (IntSet::const_iterator it = intSet.begin(); it != itEnd; ++it) {
		std::cout << *it << " ";
	}
	std::cout << std::endl;
}

int main()
{
	const int a1[] = { 0, 2, 4, 6, 8 };
	const int a2[] = { 5, 5, 3, 1, 1 };

	IntSet iSet(a1, a1 + 5);

	iSet.insert(a2, a2 + 5);

	PrintIntSet(iSet);
}

実行結果

0 1 2 3 4 5 6 8

insertメンバ関数の3つ目の形式は、イテレータと要素を指定します。
ここで指定するイテレータは、挿入する位置を探すためのヒントを与えるという意味合いのものです。 set/multiset は、ソートされた状態を保つために、必ず適切な挿入位置を決める必要がありますが、 引数から適切なイテレータを指定できれば、この位置決定のパフォーマンスを高められます。 例えば、lower_bound、upper_bound のような関数を使い(「検索」の項を参照)、 挿入位置を決定したとすれば、それらの関数が返したイテレータを渡せば良いでしょう。

#include <iostream>
#include <set>
#include <iterator>

typedef std::set<int> IntSet;

void PrintIntSet(const IntSet& intSet)
{
	const IntSet::const_iterator itEnd = intSet.end();
	for (IntSet::const_iterator it = intSet.begin(); it != itEnd; ++it) {
		std::cout << *it << " ";
	}
	std::cout << std::endl;
}

int main()
{
	const int a[] = { 0, 2, 4, 6, 8 };

	IntSet iSet(a, a + 5);

	IntSet::iterator it = iSet.insert(iSet.end(), 10);
	std::cout << std::distance(iSet.begin(), it)
	          << "番目の位置に挿入しました。" << std::endl;
	
	PrintIntSet(iSet);
}

実行結果

5番目の位置に挿入しました。
0 2 4 6 8 10

戻り値は、set なら std::set<>::iterator、multiset なら std::multiset<>::iterator です。 いずれにしても、挿入された要素を指すイテレータになります。 set の場合は、すでに同じ値の要素があったかも知れませんが、それを知ることはできません。

C++11(移動による挿入)

C++11 では、移動による挿入ができるようになっています。

iSet.insert(std::move(value));
iSet.insert(it, std::move(value));

これらのメンバ関数は、VisualC++ 2013/2015/2017、clang 3.7 のいずれでも使用できます

C++11(insert の std::initializer_list対応)

C++11 では、insertメンバ関数が std::initializer_list に対応しています。

iSet.insert({10, 20, 30});

VisualC++ 2013/2015/2017、clang 3.7 のいずれも対応しています。

C++11(insert のイテレータの const化)

C++03 までの insertメンバ関数は、要素の挿入位置のヒントを指定する第1引数の型が、std::set<>::iterator型になっていました。 そのため、この引数の意味は、挿入位置を示すことだけなので constイテレータで問題ないはずなのに、constイテレータを渡すことができません。

C++11 では、第1引数の型が std::set<>::const_iterator型に改められています(multiset なら std::multiset<>::const_iterator型)。

VisualC++ 2013/2015/2017、clang 3.7 のそれぞれで対応されています。

C++11(emplace、emplace_hint)

insert は、set/multiset の外で挿入するオブジェクトを作り、それをコピー(または移動)する必要があります。 これは、少なくとも一時オブジェクトを生成するコストが掛かるため(コピーの場合は、更にコピーのコスト)、 使い方によっては非効率さがあります。

C++11 では、要素のコンストラクタに渡す引数だけを指定し、メンバ関数内でオブジェクトを作らせるという方法が使えるようになりました。 要素1つだけを指定する insert の代わりには、emplaceメンバ関数を、 挿入位置のヒントと要素を指定する insert の代わりには、emplace_hintメンバ関数を使用します。

std::set<MyClass> mySet;

mySet.insert(MyClass(10, "abc"));      // 一時オブジェクトを作ってコピー
mySet.emplace(10, "abc");              // コンストラクタの引数だけ指定し、関数内で生成

mySet.insert(it, MyClass(10, "abc"));  // 一時オブジェクトを作ってコピー
mySet.emplace_hint(it, 10, "abc");     // コンストラクタの引数だけ指定し、関数内で生成

emplace、emplace_hint は、VisualC++ 2013/2015/2017、clang 3.7 のいずれでも使用できます

削除

「削除」は、コンテナから要素を取り除くということです。 格納されている要素が new で生成されたものであるのなら、取り除くだけではなく delete を行わなければなりません。 「削除」はそういった、必要な解放処理までは面倒を見ないことに注意して下さい。

push_back や pop_back が無いのと同様に、pop_back や pop_front はありません。 使えるのは、erase と clear になります。

eraseメンバ関数は、幾つかの形式が存在します。
1つ目の形式は、イテレータを1つ渡し、指す先の要素を削除するものです。 挿入時に位置を指定することに意味はありませんが、削除する要素の位置を指定することには意味があるので、 erase にはこの形式が存在しています。

#include <iostream>
#include <set>

typedef std::set<int> IntSet;

void PrintIntSet(const IntSet& intSet)
{
	const IntSet::const_iterator itEnd = intSet.end();
	for (IntSet::const_iterator it = intSet.begin(); it != itEnd; ++it) {
		std::cout << *it << " ";
	}
	std::cout << std::endl;
}

int main()
{
	const int a[] = { 0, 2, 4, 6, 8 };

	IntSet iSet(a, a + 5);

	IntSet::iterator it = iSet.find(6);
	if (it != iSet.end()) {
		iSet.erase(it);
	}

	PrintIntSet(iSet);
}

実行結果

0 2 4 8

必ず有効な位置を指すイテレータを指定しなければならないことに注意して下さい。 例えば、このサンプルプログラムで言うと、std::set<>::find() が要素を発見できなかった場合、 末尾の要素の次を指すイテレータを返すので、そのチェックを行っています。

実際のところ、このように特定の値を持った要素を削除したいのであれば、 eraseメンバ関数の3つ目の形式を使った方が簡単です。


eraseメンバ関数の2つ目の形式は、2つのイテレータを使って表現される範囲にある要素をまとめて削除します。

#include <iostream>
#include <set>
#include <iterator>

typedef std::set<int> IntSet;

void PrintIntSet(const IntSet& intSet)
{
	const IntSet::const_iterator itEnd = intSet.end();
	for (IntSet::const_iterator it = intSet.begin(); it != itEnd; ++it) {
		std::cout << *it << " ";
	}
	std::cout << std::endl;
}

int main()
{
	const int a[] = { 0, 2, 4, 6, 8 };

	IntSet iSet(a, a + 5);

	IntSet::iterator it = iSet.begin();
	std::advance(it, 3);
	iSet.erase(iSet.begin(), it);

	PrintIntSet(iSet);
}

実行結果

6 8

eraseメンバ関数の3つ目の形式は、削除したい要素の値を指定します。 multiset の場合、条件を満たす要素が複数あったら、そのすべてが削除されます。

#include <iostream>
#include <set>

typedef std::set<int> IntSet;

void PrintIntSet(const IntSet& intSet)
{
	const IntSet::const_iterator itEnd = intSet.end();
	for (IntSet::const_iterator it = intSet.begin(); it != itEnd; ++it) {
		std::cout << *it << " ";
	}
	std::cout << std::endl;
}

int main()
{
	const int a[] = { 0, 2, 4, 6, 8 };

	IntSet iSet(a, a + 5);

	iSet.erase(6);

	PrintIntSet(iSet);
}

実行結果

0 2 4 8


最後に、要素をすべて削除する場合ですが、これは clearメンバ関数を使うだけです。

#include <iostream>
#include <set>
#include <cassert>

typedef std::set<int> IntSet;

int main()
{
	const int a[] = { 0, 2, 4, 6, 8 };

	IntSet iSet(a, a + 5);

	iSet.clear();
	assert(iSet.empty());
}

実行結果





C++11(erase のイテレータの const化)

C++03 までの eraseメンバ関数は、要素の位置を指定するイテレータが、std::set<>::iterator型になっていました(multiset は std::multiset<>::iterator型)。 そのため、この引数の意味は、位置を示すことだけなので constイテレータで問題ないはずなのに、constイテレータを渡すことができません。

C++11 では、イテレータの型が std::set<>::const_iterator型(multiset は std::multiset<>::const_iterator型)に改められています。

VisualC++ 2013/2015/2017、clang 3.7 のそれぞれで対応されています。


練習問題

問題@ 次のような3つのメンバ変数から構成される Studentクラスがあります。

class Student {
	std::string  mName;   // 名前
	int          mGrade;  // 学年
	int          mScore;  // 得点
};

複数の Studentオブジェクトを、得点の降順で管理する set で管理するプログラムを書いて下さい。 Studentクラスに、自由にメンバを追加して構いません。

問題A 問題@を変形して、名前の昇順や、学年の昇順での管理が行えるようにして下さい。


解答ページはこちら

参考リンク

更新履歴

'2017/3/25 VisualC++ 2017 に対応。

'2016/10/15 clang の対応バージョンを 3.7 に更新。

'2015/10/12 clang の対応バージョンを 3.4 に更新。

'2015/9/23 新規作成。



前の章へ

次の章へ

C++編のトップページへ

Programming Place Plus のトップページへ