STL のオーダーに関する覚え書き
 
 総じてclearを使うとO(N)のオーダーがかかるので注意する。
 vectorのeraseはO(N)かかるので注意する。
 mapのma[key]のアクセスもO(logN)かかるので注意する。
 listはオーダーが特殊なので場合によって利用できる。
 queueとpriority_queueは扱いがだいぶ違うので覚えると良い。
 ランダムアクセスできない場合はイテレーターで++、--は使えるが+、-が使えない。
 begin()は先頭の要素だが、end()は最後の要素の次の要素なので注意。

１、vector

最後に追加する、ランダムアクセスするのはO(1)で可能。
vectorは最後にO(1)で追加できるが先頭にO(1)で追加できるデータ構造では無い。
双方向から追加できるようにする場合はdequeを使う。
挿入や削除の場合は再構築が必要なのでO(N)が必要。
insertやeraseを使った場合にO(N)かかるのは忘れがちなので注意。

v.push_back : O(1)
v.pop_back  : O(1)
v[n]        : O(1)
v.insert    : O(N)
v.erase     : O(N)
v.clear     : O(N)

要素の検索にはfind(v.begin(),v.end,value)を使うがこれは先頭からの探索でO(N)。
ソートした後、vector::iterator itr = lower_bound(v.begin(),v.end,value)でO(logN)。
if((*itr)==value)で判定。

２、set

setのアクセスは概ねO(logN)になる。
setのeraseはイテレータでも値を指定しても消せる。
setはランダムアクセスできないのでイテレーターの++、--はできるが+、-はできないので注意。
i番目の要素を得たい場合には先頭からitr++しながら数えるしかない。
i番目の要素はBITと2分探索を使えばO(logNlogN)で。

se.insert   : O(logN) 自動でソートされる
se.find     : O(logN) 見つからない場合はse.end()を返す
se.count    : O(logN) 実質0か1しか返さない
se.erase    : O(logN)
se.lower_bound(x): O(logN) x について <= になるような最も小さいインデックスを返す
se.upper_bound(x): O(logN) x について < になるような最も小さいインデックスを返す
se.clear    : O(N)

３、multiset

setとの違って同じ値が複数入る。
findでは複数該当する場合は最初の位置を返す。
countでは0と1以外の値も返す。

４、map

mapはアクセスにO(logN)かかるのが忘れがちで注意したい。
キーが無いかの判定はma.findがma.endであるかもしくはma.countが0かで判定できる。
mapのeraseもイテレータでもキーを指定しても消せる。

ma[x]       : O(logN)
ma.find     : O(logN)
ma.count    : O(logN)
ma.erase    : O(logN)
v.clear     : O(N)

５、list

listはランダムアクセスする方法が無い。
ランダムアクセスする場合はイテレータを使って先頭から探索する。
この場合のオーダーはもちろんO(N)となる。
ただし、listは挿入や削除がO(1)と早いのが特徴。

li.push_front : O(1)
li.push_back  : O(1)
li.pop_front  : O(1)
li.pop_back   : O(1)
li.insert(itr): O(1)
li.erase(itr) : O(1)
li.clear      : O(N)

６、queue

q.frontで先頭の値を得る。q.popで先頭の値を1つ捨てる。
q.pushでqueueの最後に値を追加。

q.front      : O(1)
q.back       : O(1)
q.push       : O(1)
q.pop        : O(1)

７、deque

queueと違い先頭に値を戻せる。

q.front      : O(1)
q.back       : O(1)
q.push_front : O(1)
q.pop_front  : O(1)
q.push_back  : O(1)
q.pop_back   : O(1)

８、priority_queue

priority_queueはqueueとは挙動がだいぶ異なる。
pushすると機動的に降順にソートされる。
pq.topで最大値を得る。
pq.pushで値を追加、q.popで最大値を1つ捨てる。

最小値を得るpriority_queueは以下のようにする。

priority_queue<int, vector<int>, greater<int> > q; 

pq.top       : O(1)
pq.push      : O(logN)
pq.pop       : O(logN)