【C++】簡単なvectorテクニック

メモ書きです。

削除する項目を判断する関数を与えて、指定した要素を削除します。
これを読んだだけでは要素数は変化しません

削除すべき要素が末尾に集中するので、eraseメソッドでの処理が高速化できます

条件式となる関数を与えるだけなので、クラスなどでも利用可能。
ただし、条件分岐に使う関数の引数にはそのベクタの要素となる型を指定すること。

vectorの処理においてボトルネックになりやすいポイント

eraseメソッドを使う場合だとは指定した要素を削除して、その後、その空白を埋めるために、先頭方向にずらす(コピーが発生する)ため、
要素数1000のvectorの先頭要素を削除すると、
2番目移行の要素全てずらすため、999回のコピーが発生します。

この場合、削除したい項目を末尾に移動して削除するようにすると、
pop_backメソッドで削除できるため、削除にかかる処理がO(1)で済みます

この場合だと先程の方法はうまく使えません。削除のたびに位置が変わりますからね。

でもこの場合もかんたんです。
予め、vectorを逆順に並び替えて、末尾からアクセスしていけばいいだけです。
逆順に並び替えると、実際の先頭は末尾へ。実際の末尾は先頭へいくからです。

この場合、ただ返すだけだと大量のコピーが発生して大変なことになります。(メモリも大量に消費します)
解決法としてはムーブセマンティクスを使います。
ムーブセマンティクスはこちらの方が書いてる記事が参考になるんじゃないかなぁと。

そしてこの方法はおそらくすべてのSTLで使えるんじゃないかなぁと。(全部は試してないので例外ありそうですが)
是非サンプルのmoveを外してただの戻り値にして、速度差を確認してくださいね

あ、僕はこの方法実用的なプログラムで使ったことないです。
いつも参照で解決してるので(笑)。

集中切れちゃったので今回はこれまでとします。

他にはstd::countやsort、mergeなどもありますので興味あれば調べてくださいな

msty開発メモ