std::vectorは早いと思うの

まずは普通に適当にベンチマークしてみる。
http://codepad.org/K1OkB8h1

Windows+MinGW(gcc4.5.0)の場合で、1000万個(SIZE)のデータに100回(LOOP)づつアクセス。
xorしているのは最適化によって使わない変数への処理を省いてしまうのを防止するため。

最適化なし(-O0)
array: 4187 clock
vector:5391 clock

最適化あり(-O2)
array: 921 clock
vector:1016 clock

ほら！最適化すればなかなか早いよ！！

バイナリも見る

OllyDbgが逆アセンブルした処理を眺める

最適化なし

配列

CPU Disasm
Address   Hex dump          Command                                  Comments
004013F4  |.  E8 5F0B0000   CALL                  ; Jump to msvcrt.clock
004013F9  |.  894424 24     MOV DWORD PTR SS:[ESP+24],EAX
004013FD  |.  C64424 3B 00  MOV BYTE PTR SS:[ESP+3B],0
00401402  |.  EB 39         JMP SHORT 0040143D
00401404  |>  C74424 3C 000 /MOV DWORD PTR SS:[ESP+3C],0
0040140C  |.  EB 1C         |JMP SHORT 0040142A
0040140E  |>  8B4424 3C     |/MOV EAX,DWORD PTR SS:[ESP+3C]
00401412  |.  034424 28     ||ADD EAX,DWORD PTR SS:[ESP+28]
00401416  |.  8B5424 3C     ||MOV EDX,DWORD PTR SS:[ESP+3C]
0040141A  |.  035424 28     ||ADD EDX,DWORD PTR SS:[ESP+28]
0040141E  |.  8A12          ||MOV DL,BYTE PTR DS:[EDX]
00401420  |.  325424 3B     ||XOR DL,BYTE PTR SS:[ESP+3B]
00401424  |.  8810          ||MOV BYTE PTR DS:[EAX],DL
00401426  |.  FF4424 3C     ||INC DWORD PTR SS:[ESP+3C]
0040142A  |>  817C24 3C 7F9 ||CMP DWORD PTR SS:[ESP+3C],98967F
00401432  |.  0F9EC0        ||SETLE AL
00401435  |.  84C0          ||TEST AL,AL
00401437  |.^ 75 D5         |\JNE SHORT 0040140E
00401439  |.  FE4424 3B     |INC BYTE PTR SS:[ESP+3B]
0040143D  |>  807C24 3B 63  |CMP BYTE PTR SS:[ESP+3B],63
00401442  |.  0F9EC0        |SETLE AL
00401445  |.  84C0          |TEST AL,AL
00401447  |.^ 75 BB         \JNE SHORT 00401404
00401449  |.  E8 0A0B0000   CALL                  ; Jump to msvcrt.clock

vector

CPU Disasm
Address   Hex dump          Command                                  Comments
004014DF  |.  E8 740A0000   CALL                  ; Jump to msvcrt.clock
004014E4  |.  894424 24     MOV DWORD PTR SS:[ESP+24],EAX
004014E8  |.  C64424 3B 00  MOV BYTE PTR SS:[ESP+3B],0
004014ED  |.  EB 3D         JMP SHORT 0040152C
004014EF  |>  C74424 3C 000 /MOV DWORD PTR SS:[ESP+3C],0
004014F7  |.  EB 20         |JMP SHORT 00401519
004014F9  |>  8B4424 3C     |/MOV EAX,DWORD PTR SS:[ESP+3C]
004014FD  |.  894424 04     ||MOV DWORD PTR SS:[ESP+4],EAX
00401501  |.  8D4424 10     ||LEA EAX,[ESP+10]
00401505  |.  890424        ||MOV DWORD PTR SS:[ESP],EAX
00401508  |.  E8 FF0D0000   ||CALL 0040230C
0040150D  |.  8A10          ||MOV DL,BYTE PTR DS:[EAX]
0040150F  |.  325424 3B     ||XOR DL,BYTE PTR SS:[ESP+3B]
00401513  |.  8810          ||MOV BYTE PTR DS:[EAX],DL
00401515  |.  FF4424 3C     ||INC DWORD PTR SS:[ESP+3C]
00401519  |>  817C24 3C 7F9 ||CMP DWORD PTR SS:[ESP+3C],98967F
00401521  |.  0F9EC0        ||SETLE AL
00401524  |.  84C0          ||TEST AL,AL
00401526  |.^ 75 D1         |\JNE SHORT 004014F9
00401528  |.  FE4424 3B     |INC BYTE PTR SS:[ESP+3B]
0040152C  |>  807C24 3B 63  |CMP BYTE PTR SS:[ESP+3B],63
00401531  |.  0F9EC0        |SETLE AL
00401534  |.  84C0          |TEST AL,AL
00401536  |.^ 75 B7         \JNE SHORT 004014EF
00401538  |.  E8 1B0A0000   CALL                  ; Jump to msvcrt.clockmsvcrt.clock

vectorではループ中にCALLをしており、明らかに効率が悪そう。
1000clock以上の差が出るわけです。

最適化あり

配列

CPU Disasm
Address   Hex dump          Command                                  Comments
004013F3  |.  E8 400B0000   CALL                  ; Jump to msvcrt.clock
004013F8  |.  89C6          MOV ESI,EAX
004013FA  |.  31D2          XOR EDX,EDX
004013FC  |.  8D8B 80969800 LEA ECX,[EBX+989680]
00401402  |.  66:90         NOP                                      ; Superfluous operand size prefix
00401404  |>  89D8          /MOV EAX,EBX
00401406  |.  66:90         |NOP                                     ; Superfluous operand size prefix
00401408  |>  3010          |/XOR BYTE PTR DS:[EAX],DL
0040140A  |.  40            ||INC EAX
0040140B  |.  39C8          ||CMP EAX,ECX
0040140D  |.^ 75 F9         |\JNE SHORT 00401408
0040140F  |.  42            |INC EDX
00401410  |.  80FA 64       |CMP DL,64
00401413  |.^ 75 EF         \JNE SHORT 00401404
00401415  |.  E8 1E0B0000   CALL                  ; Jump to msvcrt.clock

ループに入る前(0x004013FC)にLEA命令で、アドレスの演算を行います。
EBXにはnewで確保したchar配列が1000万(=0x989680)個はいっているので、その終端をECXに代入。
その後ループに入り、EAXにEBXを代入し、EAXの先にある値をXORで計算し、EAXを1づつ増加させECXに到達したら、1000万回処理したことになり、ループを抜けます。
なんのこっちゃ、というと、添え字を使ったアクセスではないということです。

for(i=0; i!=n; ++i){ /* arr[i] を使った処理; */ }

というコードではなく、

char *earr = arr + n;
for(char *parr=arr; arr!=earr; ++parr){ /* *parrを使った処理; */ }

という感じになっているわけです。C++のSTLのイテレータを使っているような感じです。
やってる事は同じですが、後者の方が早く動かせるのでしょう。

CPU Disasm
Address   Hex dump          Command                                  Comments
004014E0  |.  E8 530A0000   CALL                  ; Jump to msvcrt.clock
004014E5  |.  89C6          MOV ESI,EAX
004014E7  |.  31C9          XOR ECX,ECX
004014E9  |.  8D76 00       LEA ESI,[ESI]
004014EC  |>  31C0          /XOR EAX,EAX
004014EE  |.  66:90         |NOP                                     ; Superfluous operand size prefix
004014F0  |>  8B5424 14     |/MOV EDX,DWORD PTR SS:[ESP+14]
004014F4  |.  01C2          ||ADD EDX,EAX
004014F6  |.  300A          ||XOR BYTE PTR DS:[EDX],CL
004014F8  |.  40            ||INC EAX
004014F9  |.  3D 80969800   ||CMP EAX,989680
004014FE  |.^ 75 F0         |\JNE SHORT 004014F0
00401500  |.  41            |INC ECX
00401501  |.  80F9 64       |CMP CL,64
00401504  |.^ 75 E6         \JNE SHORT 004014EC
00401506  |.  E8 2D0A0000   CALL                  ; Jump to msvcrt.clock

XOR ECX,ECX でEAXを初期化（i=0に相当）
MOV EDX,DWORD PTR SS:[ESP+14] で、vectorが持つ配列へのアドレスをEDXに代入。
ADD EDX,EAX で、EDXのアドレスの位置を移動します。(EDX[i]に相当)
EDXに対する処理をして、
EAXを1加算し、1000万回になったらループを抜けます。

ということから、vectorでは添え字によるアクセスを行っていることがわかります。
配列はイテレータっぽくアクセスし、vectorでは添え字を使ったアクセスを行っている事になります。
その違いが、最適化の場合のベンチマーク結果の100clockの差でしょう。

ならなぜ、vectorの時も、配列で行われたような最適化をしないんだろうか？
vectorではsizeが記録されているので、イテレータのようにアクセスが出来るはずです。
（普通にiteratorを生成してたらそのオーバーヘッドを食ってしまう気もします）
配列の時と同じような最適化すれば、ほぼ同等な速度を出せるはずです。
アセンブリ言語と格闘してためしにやってみました。

CPU Disasm
Address   Hex dump              Command                                  Comments
004014F9      8D76 00           LEA ESI,[ESI]
004014FC      31C0              XOR EAX,EAX
004014FE      66:90             NOP                                      ; Superfluous operand size prefix
00401500      8B5424 14         MOV EDX,DWORD PTR SS:[ESP+14]
00401504      01C2              ADD EDX,EAX
00401506      300A              XOR BYTE PTR DS:[EDX],CL
00401508  |.  40                INC EAX
00401509      3D 80969800       CMP EAX,989680
0040150E    ^ 75 F0             JNE SHORT 00401500
00401510      41                INC ECX
00401511      80F9 64           CMP CL,64
00401514    ^ 75 E6             JNE SHORT 004014FC

ここらへんを

CPU Disasm
Address   Hex dump              Command                                  Comments
004014F9      8B74E4 14         MOV ESI,DWORD PTR SS:[ESP+14]
004014FD      8D96 80969800     LEA EDX,[ESI+989680]
00401503   .  90                NOP
00401504      89F0              MOV EAX,ESI
00401506   >  3008              XOR BYTE PTR DS:[EAX],CL
00401508   .  40                INC EAX
00401509      39D0              CMP EAX,EDX
0040150B   .  90                NOP
0040150C   .^ 75 F8             JNE SHORT 00401506
0040150E   .  41                INC ECX
0040150F   .  80F9 64           CMP CL,64
00401512   .^ 75 F0             JNE SHORT 00401504
00401514      90                NOP
00401515      90                NOP

こんなふうにすれば

array: 906 clock
vector:891 clock

誤差程度になります:)
LEA EDX,[ESI+989680]の989680は、要素の数(==10,000,000)なんですが、
コレは最適化によって定数展開されたものです。
この値は実際はsize()なりで現在の要素数を得るべきなんですが、まぁこれは定数時間で終わる処理だし、そのコード埋め込むのも面倒だからいいよね。ってことで決めうちしてます。

使ったバイナリ晒し
http://rying.net/arc/vector_vs_array.zip

最適化すればvectorも速くなりますね。
配列には若干劣るようです。

・・・ちょっとまて！！

いやいや、ここまでの話は、
最適化すればなぜか配列のほうが優れた展開してくれるって話で、
vectorより配列のほうが優れてるって話ではない！！
そう！配列にvectorが負けたわけじゃない！！まだ終わってないんだ！！！

それにあれはただのシーケンシャルアクセスじゃないか！！
vectorと配列はランダムアクセスが定数時間で行える事が利点だろ！！
そこで勝負しようぜ！おん？

というわけで、ランダムアクセスでベンチマーク。
(srandによりrand関数が返す値の順番は保証され手いる事を利用し、1000万回ランダムアクセス。)
http://codepad.org/foS4inMs

最適化無し(-O0)
array: 4234 clock
vector:4484 clock

最適化あり(-O2)
array: 4062 clock
vector:4047 clock

ほらね！vectorと配列はあんま変わらないんだよ！
vector最強！今日から君もvectorするしかないね！
そしてvector使いが明かした真実に配列厨、顔面レッドスクリーンｗｗｗｗｗｗｗｗｗ