んぐのルーズリーフ

んぐの日記。最近はScrapBoxが主

swap関数の実装を丁寧に追っていく

アイドルみたいに可愛い絵文字を使って、自撮りを撮ってそれを載せて。そんなブログを書きたい。


どうも、るりんぐです。


今日はswap関数の話をしたいと思います。

swap関数とは変数の値を交換を交換する関数のことをいいます。 例えば、変数a, bにそれぞれ10, 20が入っていたとして、swap関数を通すとa == 20, b == 10になります。


この関数をC++で実装しましょう。

void swap(int *p, int *q)
{
    int tmp = *p;
    *p = *q;
    *q = tmp;
}


int tmp というアイデアが初心者のときには思わず感心してしまいます。

*p = *q;
*q = *p;

としてしまうと、*pと*qが等しくなってしまいますからね。意図した動作になりません。


さて、簡単にswap関数を実装してしまいましたが、この実装のままでは2つの問題があります。

  1. swap(&a, &b)というように関数を使うときにはアドレスを渡さなければならない
  2. 任意の型に対してswapできない

順に解決していきましょう。


1 に関してはそのままでも良い気がしますが、swapというのは2つの変数の値が変更されるのは分かりきっていますし、自然にswap(a, b)としたいところです。 そこで「参照渡し」を使ってみましょう。

void swap(int &p, int &q)
{
    int tmp = p;
    p = q;
    q = tmp;
}

参照渡しとは 関数に渡される実引数と仮引数がメモリ上で同じ場所を指すようになる。いわば同じものに対する「別名」を作る感じ。

int &p = aとするとpaも名前が違うだけで指すものは全く同じになるんですね。(*pとしなくても!&aを代入しなくても!)

これを利用してswapを書き換えてみました。swap(a, b)と書けるようになりましたし、ポインタを使ってないので見た目的にも気持ちに的にもすっきりです。


それでは次に 2 を解決しましょう。

これは「テンプレート」を使えば一発です。

template <class Type> // template <typename Type>などでも良い
void swap(Type &p, Type &q)
{
    Type tmp = p;
    p = q;
    q = tmp;
}

テンプレートとは 簡単に言えば、引数の型を勝手に決めてくれる機能です。

テンプレートについてはまた詳しく解説しようと思います。

ともかく、テンプレートを使えばdouble, charなどはもちろん、MyClassに対してもswapをすることが可能です。


これで万事解決?と思いきや、実はそうではないんですね。 このままだと、例えば、

class MyClass
{
    int value[1000];
    double hoge[1000];
};

みたいなアホみたいなクラスがあるとして、これのインスタンスa, bをswapすることを考えてみます。

    Type tmp = p; // 1回コピー
    p = q; // 2回コピー
    q = tmp; // 3回コピー

と3回もこのMyClassのコピーをしています。コンピュータさんからしてみれば、この巨大なクラスを3回も書き写すのは、かなり大変で時間がかかりそうです。

昔の私であれば「それはしょうがないやろ」と済ましていました。しかし、C++11から「ムーブ」という、素晴らしく、そして理解するのが難しい機能が追加されました。 こいつを使えば、このコピーをせずともswapを実装できます。それが以下です。

template <class Type>
void swap(Type &p, Type &q) {
    Type tmp = std::move(p);
    p = std::move(q);
    q = std::move(tmp);
}

C++初心者の方からするとわけがわからないでしょうが、この実装が今(C++14)のところ最善解かと思われます。 std::moveについてここで話しているとキリがないのでこの話もまた今度。


MyClassはかなり巨大なので単純にコピーしてしまうと動作が遅くなりそうなのが分かりますが、普通に作るようなクラスでも速さが勝負になるプログラムの場合はかなり痛いです。コピーというのは我々が思っている以上に時間がかかります。


単純なswap関数もモダンな実装をしようとするとそれなりに勉強が必要ということが分かりましたね。



今日は雨が降っていました。昔は雨の雰囲気とか好きだったんですけど、最近はただただ鬱陶しいと感じるばかりです。


それではまた。