>>786
メモリの reallocation とコピーは別問題だよ。

>>790
deque のランダムアクセスは O(M) （M は内部バッファの分割数）。
O(N) よりははるかにマシだが、O(1) ではない。