基本的なデータ構造の操作
queue
q.cpp
queue<int> que; // queue型の変数queの定義
| 関数名 | 機能 | 計算量 |
|---|---|---|
| size() | キューの要素数を返す | O(1) |
| front() | キューの先頭の要素を返す | O(1) |
| pop() | キューから要素を取り出して削除する | O(1) |
| push(x) | キューに要素xを追加する | O(1) |
| empty() | キューが空の時trueを返す | O(1) |
stack
st.cpp
stack<int> stck; // stack型の変数stckの定義
| 関数名 | 機能 | 計算量 |
|---|---|---|
| size() | スタックの要素数を返す | O(1) |
| top() | スタックの頂点を返す | O(1) |
| pop() | スタックから要素を取り出して削除する | O(1) |
| push(x) | スタックに要素xを追加する | O(1) |
| empty() | スタックが空の時trueを返す | O(1) |
deque
先頭、最後尾の要素の追加、削除が定数時間でできるのが強み。
値xの検索と削除、i番目の要素の削除などはO(n)かかってしまう。
deque.cpp
deque<int> deq(要素数,初期値); // stack型の変数deqの定義
deque<int> deq{1,2,3};
| 関数名 | 機能 | 計算量 |
|---|---|---|
| size() | デックの要素数を返す | O(1) |
| front() | デックの先頭の要素の参照を返す | O(1) |
| back() | デックの先頭の要素の参照を返す | O(1) |
| emplace_front(x) | デックの先頭に要素xを追加する | O(1) |
| emplace_back(x) | デックの末尾に要素xを追加する | O(1) |
| push_front(x) | デックの先頭に要素xを追加する | O(1) |
| push_back(x) | デックの末尾に要素xを追加する | O(1) |
| pop_front() | デックの先頭要素を削除する | O(1) |
| pop_back() | デックの最終要素を削除する | O(1) |
| insert(itr,x) | イテレータが表す場所に値xを挿入するx | O(N) |
| erace(itr) | デックからイテレータがitrの要素を削除する | O(N) |
| empty() | デックが空の時trueを返す | O(1) |
| 全要素をfor文で見るときは下のようにする |
deque.cpp
deque<int> dq{1,2,3,4,5};
for(auto itr = dq.begin();itr != dq.end();++itr){
(*itr)++; // それぞれの要素に1足される
}
for(auto itr = dq.begin();itr != dq.end();++itr){
cout<<*itr<<endl; // 2,3,4,5,6
}
priority_queue
ヒープ。
priorityqueue.cpp
priority_queue<int, vector<int>, greater<int>> pq1;//最小値を取り出す
priority_queue<int, vector<int>, less<int>> pq2;//最大値を取り出す
| 関数名 | 機能 | 計算量 |
|---|---|---|
| size() | 優先度付きキューの要素数を返す | O(1) |
| top() | 優先度付きキューの頂点を返す | O(log N) |
| pop() | 優先度付きキューから要素を取り出して削除する | O(log N) |
| push(x) | 優先度付きキューに要素xを追加する | O(log N) |
| empty() | 優先度付きキューが空の時trueを返す | O(1) |
set
平衡二分探索木。小さいものから大きいものへとソートされている。
k番目に小さい要素の取得のメソッドはない。g++拡張のtreeにはある。
set.cpp
set<int> st; // set型の変数stの定義
| 関数名 | 機能 | 計算量 |
|---|---|---|
| size() | セットの要素数を返す | O(1) |
| begin() | セットの先頭を指すイテレーターを返す | O(1) |
| end() | セットの末尾(最後の要素の次)を指すイテレーターを返す | O(1) |
| insert(x) | セットに要素xを追加する(既にxがあるなら追加しない) | O(log N) |
| erace(x) | セットから要素xを削除する | O(log N) |
| erace(itr) | セットからイテレータがitrの要素を削除する | O(log N) |
| lower_bound(x) | セットにx以上である最小の要素を指すイテレータを返す | O(log N) |
| find(x) | xと等価な要素のイテレータを返す。見つからなければend()を返す | O(log N) |
| count(x) | xと等価な要素の個数を返す | O(log N) |
| clear() | セットを空にする | O(log N) |
| empty() | セットが空の時trueを返す | O(1) |
multiset
list
双方向リスト。
| 関数名 | 機能 | 計算量 |
|---|---|---|
| size() | リストの要素数を返す | O(1) |
| begin() | リストの先頭を指すイテレーターを返す | O(1) |
| end() | リストの末尾(最後の要素の次)を指すイテレーターを返す | O(1) |
| push_front(x) | リストの先頭に要素xを追加する | O(1) |
| push_back(x) | リストの末尾に要素xを追加する | O(1) |
| pop_front() | リストの先頭要素を削除する | O(1) |
| pop_back() | リストの最終要素を削除する | O(1) |
| insert(p,x) | リストのpの位置に要素xを挿入する | O(1) |
| erase(p) | リストのpの位置の要素を削除する | O(1) |
| clear() | リストの要素を全て削除する | O(n) |
map
setと同じく平衡二分探索木。keyを指定してvalueをO(log N)で取り出すことができる。
map<keyの型,valueの型> mp; //keyは順序付け可能である必要がある。
map<string, int> mp; //string → int の map
map<string,int> copied_mp(mp); // mpをコピーして同じ値を持つ
| 関数名 | 機能 | 計算量 |
|---|---|---|
| size() | 要素数を返す | O(1) |
| begin() | マップの最初の要素を指すイテレーターを返す | O(1) |
| end() | マップの最後の要素の次を指すイテレーターを返す | O(1) |
| erase(key) | keyとそのvalueを削除して削除した要素数を返す(mapなら0 or 1) | O(log N) |
| erase(itr) | イテレータがitrの要素を削除する | O(log N) |
| erase(firs,last) | [first,last)の範囲の要素を削除する | O(log N) |
| lower_bound(key) | key以上である最初のノードを指すイテレータ(なければend())を返す | O(log N) |
| find(key) | keyと値のペアのイテレータを返す なければend()を返す | O(log N) |
| clear() | 要素をdeleteし、メモリを解放する | O((N) |
| empty() | 空の時trueを返す | O(1) |
map<string,int> mp;
mp["abc"] = 1;
auto itr = mp.find("abc");
if(itr != mp.end()){
itr -> second = 100; // 値の書き換え
}
mp.erase(mp.lower_bound("i"), mp.upper_bound("k")); // keyがiからkまでの要素を全て削除
unordered_map
連想配列(ハッシュ)。vector などはキーの型として指定できないがハッシュ関数オブジェクトを指定するとキーの型として使えるようになる (詳しくはhttp://vivi.dyndns.org/tech/cpp/unordered_map.htmlを参照
操作はmapと等しい。
unordered_map<string,int> mp1; // string → int のハッシュテーブル
mp["abc"] = 1;
const unordered_map<string,int> mp2(mp);
cout<<mp2.at("abc")<<endl; // const のハッシュテーブルには[]が使えないので.at()を使う
for(auto itr = mp1.begin();itr != mp.end();itr++){
cout<<itr->first<<" "<<itr->second<<endl;
}
multimap
多重連想配列。要素の重複が可能で格納された要素をソートする。
データが動的に追加されない場合ではvectorにデータを入れてソートして使った方がメモリ効率が良い。
multisetの型は順序付けが可能である必要がある。operator<を自分で定義してもいい。
| 関数名 | 機能 | 計算量 |
|---|---|---|
| size() | セットの要素数を返す | O(1) |
| begin() | セットの先頭を指すイテレーターを返す | O(1) |
| end() | セットの末尾(最後の要素の次)を指すイテレーターを返す | O(1) |
| insert(x) | 要素xを追加する | O(log N) |
| erace(x) | セットから要素xを削除して削除したデータの個数を返す | O(log N) |
| erace(itr) | セットからイテレータがitrの要素を削除して削除した次のイテレータを返す | O(log N) |
| erase(firs,last) | [first,last)の範囲の要素を削除する | O(log N) |
| lower_bound(x) | x以上である最初の要素を指すイテレータ(なければend())を返す | O(log N) |
| upper_bound(x) | xより大きい最初の要素を指すイテレータ(なければend())を返す | O(log N) |
| find(x) | xと等価な要素のイテレータを返す。見つからなければend()を返す | O(log N) |
| count(x) | xと等価な要素の個数を返す | O(log N) |
| clear() | 要素を全て削除する | O(N) |
| empty() | セットが空の時trueを返す | O(1) |
multiset<int> mst{1,2,3,3};
for(auto itr = mst.begin();itr != mst.end();itr++){
cout<<itr->first<<" "<<itr->second<<endl; // []でアクセスすることはできない
*itr = 5; // Error イテレータ経由で値の書き換えはできない
}