2次元のvectorを高速にコピーする方法

Question

2次元のvectorを別の変数にコピーする時
new_vec = old_vec
のように元のvectorを新しいvectorに代入する方法だと時間が多くかかってしまいます。
このような場合に高速にコピーできる方法はどのようなものが存在するのでしょうか？

Answer 1

単に値を参照するのが目的であり、変更しないのであれば、次のように参照を作成すればよいです。

const std::vector<double> &new_vec = old_vec;

そうでなく、値を変更し、コピー元とは別の実体を作りたいのであれば、メモリの確保及び値のコピーが必要なので、コピーコンストラクタの呼び出しより、高速化するのは難しいでしょう。

new_vec = old_vec;

Answer 2

単純にコピーした場合は全ての要素をコピーすることになるためO(mn)になります(mとnは行と列の数)。そこで次のような方法で改善できる可能性があります。

Copy-On-Writeなvectorを使う

Copy-On-Writeとは、コピーの時は参照のようなものをしておくだけで、要素を変更するときにコピーを行うというものです(実装によって細部は異なります)。実装例としてはPHPの配列が有名です。コピー自体はO(1)になりますが、いざ、要素に変更があるときは、コピー処理が遅れて走ることになります。しかし、二次元配列の一段階目もCopy-On-WriteであればそれぞれO(1)でコピーされますので、O(m+n)で処理できることになります。

Copy-On-Writeなvector実装を探したのですが、見つけられませんでした。探せばあるかも知れませんが、単純な実装では浅いコピーになってしまう恐れがあり難しいかも知れません。初めから2次元のmatrixとして作り込んだ方がいいかもしれません。

immutableなvectorを使う

実装方法によりますが、もし、immutableなvectorであれば、代入はコピーが不要になるため、O(1)になります。要素変更はCopy-On-Writeと同じくO(m+n)になるはずです。理論上はですが。

immerというライブラリがあるようです。全く試していませんので、どうなるかはわかりません。また、immutableはコードの書き方は通常のmutableと全く異なってきますし、場合によっては全体として遅くなることもあります。