C++にてPImplイディオムを使ってUnion Findクラスを実装する

「C++のためのAPIデザイン」(AA) をKindleで購入し、読み始めました。残念ながらページレイアウトが固定で、スマホなどで読むにはまったく向いていません。しかしKindle Cloud ReaderにアクセスするとPCからでも本を開けるようになったので、27インチのディスプレイで読んでいます。

この本を読んで、前から気になっていたPimplイディオムを習得したので、試しに使ってみたいと思います。題材として、プログラミングコンテスト界隈で必須のUnion Find木を取り上げます。Union Findの詳細はプログラミングコンテストでのデータ構造がとてもわかりやすいので、こちらをご覧ください。

まずはPimplイディオムを使わない場合の実装です。やたら長いですが、詳細を読む必要はありません。ヘッダだけで十分です。

UnionFind.h

#pragma once

// Union-Find木
// クラスとして実装
// 参考：プログラミングコンテストチャレンジブック 第一版 p84

#include <vector>

class UnionFind
{
public:
    UnionFind(){};
    ~UnionFind(){};

    void Init(int num_entries);
    int Find(int x);
    void Unite(int x, int y);
    bool Same(int x, int y);

private:
    int num_entries_;
    std::vector<int> par_;
    std::vector<int> rank_;
};

UnionFind.cpp

#include <vector>
#include <algorithm>
#include <utility>
#include "UnionFind.h"

using namespace std;

void UnionFind::Init(int num_entries) {
    num_entries_ = num_entries;
    par_.resize(num_entries_);
    rank_.resize(num_entries_, 0);
    for (int i = 0; i < num_entries_; ++i)
    {
        par_[i] = i;
    }
}

int UnionFind::Find(int x) {
    if (par_[x] == x)
    {
        return x;
    }
    else
    {
        return par_[x] = Find(par_[x]);
    }
}

void UnionFind::Unite(int x, int y) {
    x = Find(x);
    y = Find(y);
    if (x == y) return;

    if (rank_[x] < rank_[y])
    {
        par_[x] = y;
    }
    else
    {
        par_[y] = x;
        if (rank_[x] == rank_[y])
        {
            rank_[x]++;
        }
    }
}

bool UnionFind::Same(int x, int y) {
    return Find(x) == Find(y);
}

main.cpp

#include "UnionFind.h"
#include <iostream>

int main(){
    int num_entries = 8;

    UnionFind uf;
    uf.Init(num_entries);

    uf.Unite(0, 2);
    uf.Unite(0, 5);
    uf.Unite(6, 7);
    uf.Unite(7, 4);

    for(int i = 0; i < num_entries; ++i)
    {
        std::cout << i << "'s group members:" << std::endl;
        for(int j = 0; j < num_entries; ++j)
        {
            if (uf.Same(i, j)) std::cout << j << ", ";
        }
        std::cout << std::endl;
    }

    return 0;
}

注目すべきはUnionFind.hのprivate部です。アクセスレベルをprivateに設定しているため、外部からこれらの値にアクセスすることは防げているので一見問題はないように見えます。しかし内部に保持するデータ型がvectorであることが露見しており、本質的には必要のない<vector>をUnionFind.hにてインクルードせざるを得ない実装になっています。

そこでPImplイディオムを使った例が以下です。PImplイディオムを使うことで不必要な露見を防げています。以下のコードはC++11必須です。

UnionFind.h

#pragma once

// Union-Find木
// クラスとして実装
// 参考：プログラミングコンテストチャレンジブック 第一版 p84

#include <memory>

class UnionFind
{
public:
    UnionFind();
    ~UnionFind();

    void Init(int num_entries);
    int Find(int x);
    void Unite(int x, int y);
    bool Same(int x, int y);

private:
    // Pimplイディオム
    class Impl;
    std::unique_ptr<Impl> m_Impl;
};

UnionFind.cpp

#include <vector>
#include <algorithm>
#include <utility>
#include "UnionFind.h"

class UnionFind::Impl
{
public:
    void Init(int num_entries) {
        num_entries_ = num_entries;
        par_.resize(num_entries_);
        rank_.resize(num_entries_, 0);
        for (int i = 0; i < num_entries_; ++i)
        {
            par_[i] = i;
        }
    }

    int Find(int x) {
        if (par_[x] == x)
        {
            return x;
        }
        else
        {
            return par_[x] = Find(par_[x]);
        }
    }

    void Unite(int x, int y) {
        x = Find(x);
        y = Find(y);
        if (x == y) return;

        if (rank_[x] < rank_[y])
        {
            par_[x] = y;
        }
        else
        {
            par_[y] = x;
            if (rank_[x] == rank_[y])
            {
                rank_[x]++;
            }
        }
    }

    bool Same(int x, int y) {
        return Find(x) == Find(y);
    }

private:
    int num_entries_;
    std::vector<int> par_;
    std::vector<int> rank_;
};

UnionFind::UnionFind()
    : m_Impl(new UnionFind::Impl) // C++14だとmake_uniqueを使ってもよい
{
}

UnionFind::~UnionFind()
{
}

void UnionFind::Init(int num_entries) {
    return m_Impl->Init(num_entries);
}

int UnionFind::Find(int x) {
    return m_Impl->Find(x);
}

void UnionFind::Unite(int x, int y) {
    return m_Impl->Unite(x, y);
}

bool UnionFind::Same(int x, int y) {
    return m_Impl->Same(x, y);
}

以上のように、実装の詳細を内部クラスのUnionFind::Implクラスに任せることで、ヘッダファイルにpublic関数以外の情報を載せないようにすることができます。これにより<vector>をインクルードする必要もなくなっています。

上記の例ではstd::unique_ptrというC++11で導入されたスマートポインタを使用しています。これによりポインタをプログラマが手動でdeleteする手間を省いています。