C++ swapの計算量について

Question

C++ swapについて質問です。

string aとbがあるときswapの操作の計算量はO(1)ですか？
その場合はアドレスの参照先を単純に入れ替えているということでよろしいでしょうか？
解答をいただけるとありがたいです。

string a = "aaa";
string b = "bbb";

// ここの計算量が知りたいです
swap(a, b);

Answer 1

string aとbがあるときswapの操作の計算量はO(1)ですか？

はい。C++標準ライブラリ仕様にて計算量 O(1) が担保されています。

Answer 2

string aとbがあるときswapの操作の計算量はO(1)ですか？

そうですね、中身の分量には依存しません。

その場合はアドレスの参照先を単純に入れ替えているということでよろしいでしょうか？

ムーブの繰り返しと等価な操作、とのことです（cpprefjp）。aやbのインスタンス自体は再作成されますが、中身の文字列はムーブでそのまま引き回されていきます。

Comments

[ameagari_hare]

std::stringの実装がSSOを採用している場合
文字数が実装定義以下の時は、計算量がO(n)でアドレス交換もされないですね。
https://wandbox.org/permlink/jwyW81elIbFDm3ZU

たいした違いは無いと思いますが、思わぬバグになったりするので一応。