Help us understand the problem. What is going on with this article?

C++の仮想関数が抽象概念に基づくアルゴリズムの実装に役立った

More than 3 years have passed since last update.

概要

C++には仮想関数というポリモーフィズムの実現に極めて有用な機能があります.
理論研究として設計したアルゴリズムの有効性を計算機で実験する際,
仮想関数機能がプログラムの拡張性を高める上で役立ったので,メモを残します.

仮想関数のおさらい

C++には,クラスのデータメンバやメンバ関数の情報を引き継ぐ継承機能があります.
ここでは継承元を基底関数,継承先を派生関数と呼びます.
基底クラスのメンバ関数をvirtual宣言により仮想関数として定義することで,
派生クラスで同名のメンバ関数を再定義し,同名ながら別の動きをする関数として利用することが出来ます.

サンプルコード

#include<iostream>
#include<iomanip>

using namespace std;

class base{
protected:
    int data;
public:
    base() : data(0){};
    virtual int depend(){ // 派生クラスでの定義に動作が依存する仮想関数
                  // 基底クラスでは,何もせずdataを返すだけと定義
        return data;
    } 
};

class derivationPlus : public base{
public:
    int depend(){ // 仮想関数の再定義(dataをインクリメント)
        data++;
        return data;
    }
};

class derivationMinus : public base{
public:
    int depend(){ // 仮想関数の再定義(dataをデクリメント)
        data--;
        return data;
    }
};

class derivationNoDefine : public base{ // 仮想関数を再定義しない(基底クラスの定義をそのまま使う)
};

int main(){
    derivationPlus P;
    derivationMinus M;
    derivationNoDefine N;
    cout << "Output of derivationPlus    : " << setw(2) << P.depend() << endl;
    cout << "Output of derivationMinus   : " << setw(2) << M.depend() << endl;
    cout << "Output of derivationNoDefine: " << setw(2) << N.depend() << endl;
}

出力結果

Output of derivationPlus    :  1
Output of derivationMinus   : -1
Output of derivationNoDefine:  0

仮想関数が役立った一つのケース:理論研究の計算機実験において

筆者は某大学院のOR系研究室に所属しており,修士論文の計算機実験用プログラムをC++で書こうという際に上記機能が必要となりました.
マトロイドと呼ばれる,グラフの無閉路性や線形代数の独立性などを抽象化した概念について研究しており,
多種多様なマトロイドをぶち込んでも動くような便利なオークションテーブルを設計したいと思っています.

マトロイドは前述の通り,高度な抽象概念のため具体例が様々考えられ,判定内容が多岐にわたります.

マトロイドの種類 オブジェクトがもつ情報 独立性判定の内容
Uniform matroid 容量(整数値) 与えられた集合の要素数がキャパシティを超えないか
Graphic matroid グラフ 与えられた枝集合が閉路(サイクル)をもつか
Transversal matroid 有限集合の部分集合族 与えられた要素集合から部分集合族への単射が存在するか

マトロイドを表すオブジェクトについて,独立性判定を行う「independenceCheck」という関数を呼び出せば,その入札者のもつ個別のマトロイドについて独立性判定を行ってくれるというインタフェースを実現したいと考えました.
上記の実装法を使えば,以下のような設計が可能となります.

  • 継承元クラスとしてのmatroidクラスにindependenceCheck関数を仮想関数として定義
  • 個々のマトロイドはmatroidクラスを継承して定義し,個別具体的にindependenceCheck関数を定義する

こうすれば,別種のマトロイドを導入したいと思ったときも,independenceCheck関数を新たに定義するだけで済み,既存のマトロイドと綯い交ぜにしたオークションテーブルも容易に生成できます.
この場合,matroidオブジェクトそのものを生成することはなさそうなので,純粋仮想関数として定義するのがより適切かもしれません.
マトロイドの理論的な抽象性をC++の継承というかたちで表現することが出来ると分かり,嬉しく思いました.

疑問

実は上述のサンプルコードは,virtual宣言を外しても出力が変わらなかったのだけど,
その場合は基底クラスのdepend関数が呼び出されるはずで,下記の出力が正しいように思える.どうしてだろう?

Output of derivationPlus    :  0
Output of derivationMinus   :  0
Output of derivationNoDefine:  0
takijuso
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした