C++で使えるデータ構造の比較表

はじめに

C++でコードを書いていて、データ構造の違いでメンバ関数がちょっと違っていたりして迷ったことはありませんか？

• vectorへの要素追加ってpush_backだっけ？insertだっけ？
• mapはソートされてるんだっけ？ソートされるのはどれだっけ？

私もこういうことがあって迷ったため、比較表にまとめてみました。

コードはあくまで例であり別の書き方があるものもありますが、よく使われるであろう表記を記載しました。

pair, tuple

	pair	tuple
特徴	2つの値をペアで保持できる	0個以上の値の組を保持できる
変数宣言	pair<int,string> p(1, "Two");	tuple<int, int, string> t;
値の代入	p = make_pair(1,"Two");	t = make_tuple(1,2,"Three");
値の参照	p.first p.second	int& i = get<0>(t); int& j = get<1>(t); string s = get<2>(t);
比較	若い番号の要素で比較 等しい場合には一つ後ろの要素で比較	若い番号の要素で比較 等しい場合には一つ後ろの要素で比較

vector, set, map, multimap

| |vector|set|map
unordered_map|multimap
unordered_multimap|
|:-:|:-:|:-:|:-:|:-:|:-:|
特徴|動的配列|重複のない要素集合|連想配列

unorderedがついているものはソートされていないmap|多重連想配列
キーを重複して持てるmap

unorderedがついているものはソートされていないmap
キーの重複が可能か|No|No|No|Yes|
変数宣言|vector<int> v(要素数,初期値);|set<int> s{2,1,4,5};|map<string, int> m;|multimap<string, int> m;|
値の参照|v[0]|-|m.at("One")|findを使う|
値の代入|v[0]=1;|-|m["One"] = 1;|？|
空判定|v.empty()|s.empty()|m.empty()|m.empty()|
サイズ|v.size()|s.size()|m.size()|m.size()|
末尾の要素|v.back()|auto itr=s.end();itr--;cout << *itr << endl;|-|同左|
要素を追加|v.push_back(3)
末尾に追加|s.insert(3)|m["One"] = 1;
または
m.insert(make_pair("One",2));
または
m.emplace("One",2);|m.insert(make_pair("One", 1));
要素を削除|v.erase(v.begin() + 2)
2番目の要素を削除

v.pop_back()
末尾要素を削除|s.erase(3)|m.erase("One")|s.erase(3)|
要素の検索

イテレータが返る,要素が見つからない場合はx.end()が返る||s.find(3)|m.find("One")|？|
ソートされているか(lower_boundが使えるか)|No|Yes|map Yes
unordered_map No|multimap Yes
unordered_multimap No|
ソートの計算量|O(NlogN)|-|-|-|
昇順ソート|sort(v.begin(),v.end());|-|-|-|
降順ソート|sort(v.begin(),v.end(), greater<int>());|-|-|-|
要素の順番を逆にする|reverse(v.begin(),v.end());|-|-|-|

stack, queue, priority_queue, dequeue

	stack	queue	priority_queue	deque
仕組み	LIFO backから挿入され、backから取り出す	FIFO backから挿入され、frontから取り出す	優先度付きキュー デフォルトは降順	先頭・末尾の両方から要素の追加・削除ができるキュー
宣言例	stack<int> st;	queue<int> q;	priority_queue<int> q;	deque<int> dq;
ソートされるか	No	No	Yes	No
要素数	st.size()	q.size()	同左	dq.size()
先頭に要素を追加	-	-	同左	dq.push_front(1)
先頭要素の参照	-	q.front()	同左	dq.front()
先頭要素の取り出し	-	q.pop();	同左	dq.pop_front()
末尾に要素を追加	st.push(1)	q.push(1)	同左	dq.push_back(99)
末尾要素の参照	st.top()	q.back()	同左	dq.back()
末尾要素の取り出し	st.pop()	-	同左	dq.pop_back()

まとめ

C++の基本的なデータ構造について比較してまとめてみました。

※あまり慣れていないため、誤記があれば指摘ください。