Swap技法について

Question

リーダブルコードという本でSwap技法なるものを知りました。
調べてみるとvector型でClearを呼ぶ際にメモリが正常に開放されないからSwapを使うというものらしいです。
ただそれってvectorにあるeraseをfor文で回すのと変わらなくないかと思っています。
swapによるメモリ解放とeraseによるメモリ開放違いってなんなんでしょうか？

Answer 1

swap技法は今から約10年前に過去の産物となった技法です。他の方の指摘の通りshrink_to_fitを使いましょう。いずれもあまりに巨大に確保されたcapacityを適切なサイズに落とすことを要求する(実際にそうなるとは言っていない)ものです。

古い本のベストプラクティスとして紹介されている技法はとくにC++11の登場によって不要になるかバッドプラクティスとなっているものが多いので、適用してみようとする前にその技法が今どういう評価を受けているかは慎重に調べることをおすすめします。

---

追記

class A
A *a = new A();
vector<A> avec;
a.push_buck(a);

このavecを開放しようとなると

```cpp

delete a;
shrink_to_fit();

と呼ばないと全メモリは開放されない感じなんですかね？
aで確保したアドレスとavecに挿入後のアドレスは変らないようですが 

待ってください、そのコードはだいたい全部おかしいです。

型の問題

変数avecの型はstd::vector<A>です。ですから要素の型はAです。A*ではありません。したがってa.push_buck(a); はコンパイルエラーになります。

std::vectorのデータ構造について

swap技法にしろshrink_to_fitにしろ、何を目的としたものなのか把握されていないように思います。間違っても全メモリーを開放することを目的としたものではありません。
std::vectorはどのようにメモリーを使うか理解していないのではありませんか？

std::vectorを単純化すると次のような構造体になります(現実にはアロケータがここに加わりますが割愛します)。

template<typename T>
struct vec {
    T* p;
    std::size_t size;
    std::size_t capacity;
};

capacityは確保されているメモリー領域の大きさ、sizeは格納されている要素数です。つねにsize <= capacityの関係になります。
例えばstd::vector::push_backのようなメンバ関数を呼び出すとき、もしsize == capacityの状態にあると、新たな要素を追加することはできません。そこでメモリーを新規に確保して(一般にcapacityの1.5～2倍)、すでにある要素をそちらに移して(厳密にはmove操作が無例外で行えるならmove, さもなくばcopy)、今まで割り当てていたメモリーを開放し、capacityを更新して、末尾に新規要素を追加し、sizeを更新します。

vectorに様々な操作をするにつれて、時としてcapacityがsizeよりも遥かに大きい状態になることがあります。例えば要素の大量削除をしたときなどです。このとき、実行速度を犠牲にしてでも(一般にメモリーの確保作業にはとても時間がかかります)メモリー使用量を削減したいという需要が発生します。この需要を満たすための手段がかつてのswap技法や、std::vector::shrink_to_fitの呼び出しです。

ここでお示しのコードを上述の型の問題を解決するように書き直してみましょう。

class A;

void foo()
{
    A* a = new A();
    std:vector<A*> v;
    v.push_back(a);
    delete a;
    a.shrink_to_fit();
}

さて、変数aはA*型の変数で、new演算子によって割り当てられたメモリーを指し示すポインタです。
これを変数vのvectorに追加します。つまりv.push_back(a);の直後ではnew演算子によって割り当てられたメモリーを指し示しているポインタは、aとv[0]の2つ存在しています。
delete a;については一度飛ばします。

では、a.shrink_to_fit();の意味をここで考えましょう。変数v、つまりvectorには要素が追加されるだけで削除はしていません。このときcapacityがsizeよりも遥かに大きい状態になることは起こりえません。するとa.shrink_to_fit();は無意味ということが言えます。

SHOMIさんやepistemeさんの回答にあるサンプルコードをよく見てください。

##　dangling pointer

delete aについて考えます。ここでnew演算子によって割り当てられたメモリーが開放されます。つまりaとv[0]は存在しない領域へのポインタになったわけです。存在しない領域へのポインタのことを一般にdangling pointerと呼びます。例えばこのあとに*v[0]とかやるとdangling pointerをdereferenceしていますから未定義動作となりコンパイラはタイムトラベルしたり鼻から悪魔を召喚したりする可能性がありえます。

Comments

[apa]

回答ありがとうございます。
つまり
class A
A *a = new A();
vector<A> avec;
a.push_buck(a);
このavecを開放しようとなると
delete a;
shrink_to_fit();と呼ばないと全メモリは開放されない感じなんですかね？
aで確保したアドレスとavecに挿入後のアドレスは変らないようですが

[apa]

返信おくれました　
あとvector<A>の＊抜けのところ完全にうちミスです。混乱させてしまいすいません。

なるほどだいぶわかった気がします。
ただそもそもなにもさしていない(deleteで空になっている)vector型の avecっていくらcapacityがあろうが空である以上メモリに何ら影響がないように思えてしまいます。
そうではないなにか特殊な規約があるのでしょうか？

[apa]

ただこの質問はvector型に対してになってしまうので
もう少しvectorについて調べてきます。

[apa]

capacityについて調べてきました。
ゲームループなどでメモリが増えつつづけることはないですが、
メモリ領域の圧迫につながるため
shrink_to_fit()を呼ぶことを推奨されているという
認識であっていますでしょうか？

[yumetodo]

>shrink_to_fit()を呼ぶことを推奨されている

いえ、実行速度を犠牲にしてでも(一般にメモリーの確保作業にはとても時間がかかります)メモリー使用量を削減したいという需要が発生したときに呼び出します。

[apa]

メモリが足りているようなら大丈夫みたいですね！
なるほどわかりやすい説明ありがとうございました！！
また一歩成長できました

[yumetodo]

いい忘れてましたが
> (deleteで空になっている)vector型の

そのdeleteはvectorのsize/capacityになんら関係のないものです。全くの無関係です。念の為。

Answer 2

vectorにあるeraseをfor文で回すのと変わらなくないかと思っています。

swapによるメモリ解放とeraseによるメモリ開放違いってなんなんでしょうか？

erase()やclear()ではvectorが確保したメモリは解放されません。
C++11以降ならerase()やclear()の後にshrink_to_fit()を呼ぶことでも解放するよう要求できます。(解放される保証はないですが)

#include<iostream>
#include<vector>

int main()
{
    std::vector<char> v;
    std::cout << "Initial:" << v.capacity() << std::endl;

    v.resize(10000);
    std::cout << "resize:" << v.capacity() << std::endl;

    while (!v.empty())
    {
        v.erase(v.begin());
    }
    std::cout << "erase all:" << v.capacity() << std::endl;

    std::vector<char>().swap(v);
    std::cout << "swap:" << v.capacity() << std::endl;

    v.resize(10000);
    std::cout << "resize:" << v.capacity() << std::endl;

    v.clear();
    std::cout << "clear:" << v.capacity() << std::endl;

    std::vector<char>().swap(v);
    std::cout << "swap:" << v.capacity() << std::endl;

    v.resize(10000);
    std::cout << "resize:" << v.capacity() << std::endl;

    while (!v.empty())
    {
        v.erase(v.begin());
    }
    v.shrink_to_fit();
    std::cout << "erase all & shrink_to_fit:" << v.capacity() << std::endl;


    v.resize(10000);
    std::cout << "resize:" << v.capacity() << std::endl;

    v.clear();
    v.shrink_to_fit();
    std::cout << "clear & shrink_to_fit:" << v.capacity() << std::endl;

    return 0;
}

実行結果

Initial:0
resize:10000
erase all:10000
swap:0
resize:10000
clear:10000
swap:0
resize:10000
erase all & shrink_to_fit:0
resize:10000
clear & shrink_to_fit:0

Answer 3

Swap技法

は，
既存のvector Aと空のvector Bとでswapすることで，管理しているメモリ領域を交換する→Bが解体される際に（元々Aが管理していた）メモリが解放される
という話．

eraseをfor文で回すのと変わらなくないか

eraseだとcapacityが減らないという点では，clearと変わらないです．

Comments

[fana]

他の回答にて述べられているように，Swap技法はもはや使うことはないでしょうが…

複数の人間がたずさわる場面でこのような技法を使う際には，コードの該当箇所にコメントを書きましょう．
//Swap技法
みたく．
それを怠ると，その技法を知らない人にコードを意図しない形に修正されたり（例えばSwap技法ならば，clear()に書きなおされるとか），さらには「あいつは意味不明なクソコードを書く」とかいう悪評まで流されたりもします．

Answer 4

vector型でClearを呼ぶ際にメモリが正常に開放されない

要素が削除されてもcapacityが小さくならないってーおハナシかしら。
C++11以降、shrink_to_fit() ってメンバ関数が追加されてます。

#include <iostream>
#include <vector>

int main() {
  std::vector<int> v(10000);
  std::cout << "capacity before clear : " << v.capacity() << std::endl;
  v.clear(); // 削除してもキャパは変わらず
  std::cout << "capacity after  clear : " << v.capacity() << std::endl;

#if 1
  {
  std::vector<int> empty; // 空のvectorを用意して
  v.swap(empty); // 入れ替え
  }
  std::cout << "capacity after  swap  : " << v.capacity() << std::endl;
#else
  v.shrink_to_fit();
  std::cout << "capacity after  shrink_to_fit : " << v.capacity() << std::endl;
#endif

}