“ 788 ：デフォルトの名無しさん：2007/12/16(日) 20:48:26 »784 コンテナの操作の計算量に関する要求は標準の23.1にあるわけだが、 ここで要求されている計算量は、操作に掛かる時間そのものについてじゃなくて、 「コンテナ内のオブジェクトを操作する回数」についてのものだと規定されてる たとえばvectorに対するpush_backなら、要素のコピーコンストラクタを償却O(1)回呼ぶってことだ で、libstdc++(たぶんstlportも)のdequeの実装だと、最悪O(n)回のポインタ代入が発生するけど、 要素のコピーコンストラクタは常に1回しか呼ばれないので、規格の要求するO(1)は満たしてることになる
—
【C++】STL（Standard Template Library）相談室 7
std::dequeの先頭末尾追加に関する、定数時間でいけるよ派vs償却定数時間じゃないとむりぽ派のやりとりのまとめ。
