備忘録 @ ウィキ

tips

最終更新：2009年08月11日 15:44

mlnk

- view

管理者のみ編集可

暗黙の型変換を引数に使う
目的別探索方法
lower_bound、uppder_bound、equal_range の返すイテレータの場所
- 要素がある場合
- 要素がない場合
イテレータの無効化のタイミング
テンプレートクラスをフレンドクラスにする
効率のいいmapへの追加・更新
モジュールを超えたメンバ関数呼び出し

暗黙の型変換を引数に使う

暗黙の型変換を引数に使うためには引数は値渡しでないといけない。

struct A{
	A(){}
	A(int){}
};
 
void f(A, A) {}
void g(A&, A&) {}
 
int main()
{
	f(1, 2); // OK
	//g(1, 2); // エラー
 
	return 0;
}

目的別探索方法

何を知りたいか	使用するアルゴリズム		使用するメンバ関数
何を知りたいか	未ソートの範囲	ソート済み範囲	set または map	multiset または multimap
必要な値が存在するか?	find	binary_search	count	find
必要な値が存在するか? 存在するなら、その値を持つ最初のオブジェクトはどこにあるか?	find	equal_range	find	find または lower_bound(*1)
必要な値より前にない値を持つ最初のオブジェクトはどこにあるか?	find_if	lower_bound	lower_bound	lower_bound
必要な値の次にある値を持つ最初のオブジェクトはどこにあるか?	find_if	upper_bound	upper_bound	upper_bound
必要な値を持つオブジェクトはいくつあるか?	count	equal_range	count	count
必要な値を持つすべてのオブジェクトはどこにあるか	find (繰り返し処理)	equal_range	equal_range	equal_range

lower_bound、uppder_bound、equal_range の返すイテレータの場所

lower_bound は同値の最初の要素を返す。同値の要素がない場合はそれ未満で最大の要素の次を返す。
upper_bound は同値の要素の中で一番後ろの要素の次を返す。同値の要素がない場合はそれより大きい最小の要素を返す。
equal_range はlower_bound と upper_bound の戻り値の組を返す。
- というか lower_bound も upper_boundも「その値が挿入されるべき位置」という意味では同じか。それが前か後ろかの違いだけで。

要素がある場合

1 を探す場合

1 1 3 3 5 5

lower_bound upper_bound

3 を探す場合

1 1 3 3 5 5

lower_bound upper_bound

5 を探す場合

1 1 3 3 5 5

lower_bound upper_bound

要素がない場合

0 を探す場合

1 1 3 3 5 5

lower_bound
upper_bound

2 を探す場合

1 1 3 3 5 5

lower_bound
upper_bound

6 を探す場合

1 1 3 3 5 5

lower_bound
upper_bound

イテレータの無効化のタイミング

vector
- Reallocationが起きると参照・ポインタ・イテレータ全て無効化される。
- reserve…reserveする大きさが現在のcapacityより大きければReallocationが起きる
- insert,push_back…sizeがcapacity超えるとReallocationが起きる
- erase…eraseした点より後ろの全ての参照・イテレータ無効化
deque
- insert…中間点への挿入はイテレータ・参照ともに全て無効化、最後への挿入(==push_back)はイテレータは全て無効化するが参照は有効のままである。
- erase…中間点の削除はイテレータ・参照ともに全て無効化、最後の削除は削除された要素に対するイテレータ・参照のみ無効化
list
- insert,push_front,push_back…イテレータ・参照ともに全て有効のまま
- erase…削除された要素に対するイテレータ・参照のみ無効化
- splice
  - splice(pos, x)は第二引数のリストの要素に対する全ての参照・イテレータ無効化
  - splice(pos, x, it)は第二引数のリストのspliceされた要素の参照・イテレータ無効化
  - splice(pos, x, start, end)は第二引数のリストのspliceされた要素全ての参照・イテレータ無効化
連想コンテナ(set,map,multiset,multimap)
- insert…イテレータ・参照ともに全て有効のまま
- erase…削除された要素に対するイテレータ・参照のみ無効化
他
- swapはイテレータ・参照は有効のままである
- 上記以外でも内部で上記のメンバ関数がよばれれば同様の無効化がおきる

テンプレートクラスをフレンドクラスにする

template<typename T> class hoge; // 前方宣言
 
class foo {
	template<typename T> friend class hoge; // フレンドクラスの宣言
};

効率のいいmapへの追加・更新

template <class map_type, class key_type, class value_type>
typename map_type::iterator efficientAddOrUpdate(map_type& m, const key_type& k, const value_type& v)
{
	typename map_type::iterator lb = m.lower_bound(k);
	if(lb!=m.end() && !(m.key_comp()(k, lb->first))) {
		// キーが存在した
		lb->second = v;
		return lb;
	} else {
		// キーが存在していない
		typedef typename map_type::value_type map_value_type;
		return m.insert(lb, map_value_type(k, v));
	}
}