C++で爆速vectorを実装してみた - Qiita

こんにちは、kaageです。 C++のstd::vectorを使っていて、遅い、と感じたことはありませんか？僕はありません。 それはさておき、std::vectorより要素の挿入が速く、（ほぼ）同等の機能を搭載したvectorを実装してみました。 速度が圧倒的に優位というわけでもないですが、C++の言語機能を網羅的に知るという面で意味があると思うので、記事にします。 なお、配列外参照などに関しての安全性は全く保証していません。（というより、速い最大の理由はこれです） std::vectorとは C++を使っているなら知っているとは思いますが、一応std::vectorの説明をします。 std::vectorは、C++の標準ライブラリに含まれる可変長配列です。要素数に応じて長さを変化させます。 後方への挿入、後方からの削除は $O(1)$, 任意位置への挿入は、挿入位置を $x$, 長さを