swap技法とshrink_to_fitの違い
こんにちはtatsyです。
最近リーダブルコードを読んでおりまして、この世の中にはvectorのswap技法と呼ばれるものがあることを知りました。
swap技法とは？
swap技法というのは、vectorがreserve等で確保している内部的なメモリのサイズ(capacityで確認できる)を切り詰めるための方法です。
通常、reserveというのはメモリ容量を増やすことはあっても減らすことはありません。つまり、
x;
x.reserve(128); // 容量が128になる
std::cout << x.size() << std::endl; // 0
std::cout << x.capacity() << std::endl; // 128
x.reserve(10); // 容量は変化しない
std::cout << x.size() << std::endl; // 0
std::cout << x.capacity() << std::endl; // 128
というふうに、いったん大きめの要領を確保したあとに小さ目の要領をreserveしても容量は変化しません。
で、こいつをどうにかするためにswap技法という方法があり、reserve後に次のようなコードを呼んであげるとメモリ容量が正しく変化します。
x;
x.reserve(128); // 容量が128になる
std::cout << x.size() << std::endl; // 0
std::cout << x.capacity() << std::endl; // 128
x.reserve(10); // 容量は変化しない
vector<int>(x).swap(x); // 容量が切り詰められる
std::cout << x.size() << std::endl; // 0
std::cout << x.capacity() << std::endl; // 10
なんでこうなるかというと、vectorのコピーコンストラクタはコピー元のvectorのsizeを見て、コピー先のvectorの要領を決定するからです。
でも、最初にこのコードを見たときに思ったのは、こんなことしたらコンテナに入っているインスタンスが死ぬほどコピーされて計算に時間がかかちゃったりするんじゃないかということです。
そこで登場するのがshrink_to_fitという関数です。
shrink_to_fitとは？
shrink_to_fitはc++0xで導入された関数で、基本的な動作は上記のswap技法と同じです。
ただし、これまたc++0xで導入されたmove semanticsを使うと、微妙に動作が変わります。
試しにmove semanticsを導入した次のようなクラスを定義してみます。
class Var {
private:
int val;
public:
explicit Var(int v = 0)
: val(v)
{
std::cout << "Construct" << std::endl;
}
Var (const Var& v)
: val(v.val)
{
std::cout << "Copy" << std::endl;
}
Var(Var&& v) noexcept
: val(v.val)
{
std::cout << "Move" << std::endl;
}
Var& operator=(const Var& v) {
std::cout << "Assign" << std::endl;
this->val = v.val;
return *this;
}
Var& operator=(Var&& v) noexcept {
std::cout << "Move" << std::endl;
this->val = v.val;
return *this;
}
};
単にクラス内にvalで変数を格納しているだけのクラスです。このクラスだと別にコピーコンストラクタもmoveも動作は変わらないのですが、今回は単なる例ですので、これで許してください。
さて、当たり前ではありますが、move semanticsを使ってあげると、
x.push_back(Var(i));
というように呼び出した時のコピーコンストラクタの呼び出しを抑制してくれます。まぁ、もっともc++11にはemplace_backという関数があるので、
x.emplace_back(i);
と呼べば、moveすら呼ばれないわけですが。ちなみにnoexceptという識別子をmoveのコンストラクタにつけてあげないと、この機能はONにならないです。
さて、少し話がそれましたがshrink_to_fitはこのmoveを使ってコピーをしないようにしてくれます。
swap技法の場合には単にコピーコンストラクタを呼んでるだけなので、要素がコピーされますし、swapされた後にはコピー元のvectorは使わないわけですからmoveで代替するというのは妥当な選択と言えると思います。
コードを書いてみる
実際に上のクラスを使って、次のようなコードを書いてみました。
int main() {
std::vector<Var> x;
x.reserve(128);
std::cout << "Init" << std::endl;
std::cout << x.size() << std::endl;
std::cout << x.capacity() << std::endl;
for (int i = 0; i < 100; i++) {
x.emplace_back(i);
}
std::cout << "Added" << std::endl;
std::cout << x.size() << std::endl;
std::cout << x.capacity() << std::endl;
x.resize(10);
std::vector<Var>(std::move(x)).swap(x);
// x.shrink_to_fit();
std::cout << "Resize" << std::endl;
std::cout << x.size() << std::endl;
std::cout << x.capacity() << std::endl;
}
上のコードではswap技法を使っていますが、その際の出力は次のようになります(該当箇所のみ)。
Copy
Copy
...
Copy
つまりコピーコンストラクタが10回呼ばれます。一方でshrink_to_fitを使った場合には次のようになります。
Move
Move
...
Move
つまりmoveコンストラクタが10回呼ばれます。こちらの方が明らかに賢いですね。
ちなみに、「それだったら、swap技法のコピーコンストラクタ呼び出しをmoveに代えればよいのでは？」と思うかもしれないですが、それだとcapacityが変化しません。
vector<int> x;
x.reserve(128); // 容量が128になる
std::cout << x.size() << std::endl; // 0
std::cout << x.capacity() << std::endl; // 128
x.reserve(10); // 容量は変化しない
vector<int>(std::move(x)).swap(x); // 容量変化なし
std::cout << x.size() << std::endl; // 0
std::cout << x.capacity() << std::endl; // 128
まとめ
というわけで、C++x0以上が使えるならshrink_to_fitの方が賢いです。いやぁ、move semanticsはすごいですね。
というわけで今回の記事は以上です。最後までお読みいただきありがとうございました！