C++ std::list, std::vector, std::dequeをまとめておく

# vector [cplusplus](http://www.cplusplus.com/reference/vector/vector/) arrayのように連続ストレージ系のコンテナ。 ＋ * arrayと違って可変長。 * ランダムアクセス性が高い。 * endに対してのaddやremoveはlist,dequeに対して効率的 ー * 頻繁なallocationを防ぐために余分にメモリ確保される。 * （actual sizeに対してcapacityを大きく確保するから。ライブラリによってallocationタイミングは分かれるが、一般的いはlogインターバル） * end以外へのinsertやremoveはlist,dequeに対して遅い * iteratorの定常性というかconsistencyはlistに比べると低い # list [cplusplus](http://www.cplusplus.com/reference/list/list/) 固定処理時間でのinsert、erase（場所によらない）が特徴の双方向リストコンテナ ＋ * insert, erase, moveが他のコンテナと比較して速い ー * ランダムアクセス性は低い、begin/endとかからたどる必要がある（はず）O(n) # deque [cplusplus](http://www.cplusplus.com/reference/deque/deque/) Double-Ended-Queueの略。Queueの一種なのでbeginとendからしか拡張できない。 ＋ * arrayと違って、可変長 * listと違って、ランダムアクセス性は高い * vectorと違って分割されたChunk（＋ランダムアクセス用の情報）に分けてデータを保存しているらしい。 * vectorと違って、endだけでなくbeginへのaddやremoveも効率的 ー * vectorと違って、連続的な保存は保証されない（ポインタ＋オフセットでアクセスしちゃダメ） * beginやend以外へのinsert、removeは遅い * iteratorの定常性というかconsistencyはlistに比べると低い

• ツイート