こいつをどう思う？
vectorとlistの速度を調べるだけのプログラム・・・なのだが、結果は明白、O(N)のvectorに対してO(1)のlistがずっと速くなるはずだ。が、

いざ実行するとvectorのが速かった。どっかミスってたら指摘して欲しいんですが、合ってたらもう　こ　れ　は　ひ　ど　い　としか。

世の中って不条理ですね！

vector.push_back();
って定数時間じゃなかったですっけ？
イテレーターによる表示の繰り返しは両方一緒だし
しいて言えばvectorはある程度変数を格納する場所が決まってるけど
listは毎回変数宣言から始まるから遅いのでは？と思ったり

あ、すいません。全然具体的な結果を書いてなかったですね。

実のところ、両者push_backにはほとんど時間がかかっておらず、eraseで倍くらいの差がつきました。なにげにこれも不思議だったりするんですけどね。
だってlistは追加のたびに毎回newしている（らしい）んですよ。だったらもうちょい追加は重くてもいいはずなんですが、なんとも。

eraseって消す順番が云々

ベンチマークの仕方がおかしいような
先頭削除するだけなら明らかにstd::dequeつかったほうがいいと思います

>しいて言えばvectorはある程度変数を格納する場所が決まってるけど
>listは毎回変数宣言から始まるから遅いのでは？と思ったり
std::vectorは連続した領域である必要があるのでいちいち再確保してます
newが遅い遅い言われてますが気にする必要があるほどではないと思います


あれ、と思ったので書いてみましたがstd::listの方が速いような...
http://ideone.com/PtP02

SUE さんが書きました:vectorとlistの速度を調べるだけのプログラム・・・なのだが、結果は明白、O(N)のvectorに対してO(1)のlistがずっと速くなるはずだ。

どうしてそんなことが言えるのでしょうか？
そもそもオーダーというのは、要素数Nに対しての作業時間の増加率にすぎません。
O(N)というのは作業時間が高々要素の数に比例するといっているだけで、別にO(1)より小さいといってるわけではありません。

y=xと y = 2000のグラフを比べたらわかるように、x<2000まではむしろy=xのほうが小さいわけです。
1024*100という数が微妙なのであって、もっと圧倒的な大きさの要素について行えば、listのほうが速くなることでしょう。

むしろこの実験で得られたことはSUEさんの環境では、その程度の要素数までならvectorを使うべきだという結論でしょう。
というより、せいぜい数百までの要素数なら大概何をするにもvectorが1番速いと思います。（どこに追加しようが、何を削除しようが。）
もちろんディープコピーするのに、とっても時間のかかるクラスなどを格納するならわかりませんが・・・。

ただ測り方に問題があるのかもしれませんので、その辺はコードがないとわかりません。

>>loweさん
いやまさか・・・そんなはずは・・・（ランダム削除プログラム書きたくない

>>roxion1377さん
すいません、先頭削除に特に意味はなくて、eraseを使ったときにどれくらい差がでるのかを確かめたかったので。

>>GRAMさん
後日改めて色んなNで計測したところ、GRAMさんの言う通り、N=１０とか１００ではvectorの方が速いのですが、N=１０＾７くらいだとlistの方が速くなりました。
なんかお騒がせした感じで申し訳ないです。

GRAM さんが書きました: 1024*100という数が微妙なのであって、もっと圧倒的な大きさの要素について行えば、listのほうが速くなることでしょう。

そうか、微妙なのか・・・なんかスケールが違うな・・・出直してきます。