スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。
 

C++ での Mixin の活用 : Comparable を使って比較演算子を簡単実装

オブジェクト指向プログラミングには Mixin という手法があります。 これを使えば、自作のクラスを比較可能な(Comparable)クラスにすることが簡単に出来ます。 今回は Comparable Mixin を例に C++ での Mixin のやり方について説明します。

Mixin とインターフェース

Mixin の前提として、 多重継承の問題点を把握しておく必要があります。 その辺の話や Mixin の概要に関しては以下の記事をみていただくとして、 C++ に限定して簡単に説明していきます。 多重継承の問題を避けるための代表的な方法はインターフェースです。
class IComparable
{
 public:
  virtual int Compare(const IComparable &other) const = 0;
};
インターフェースの制限は次の 2 つです。 この制限によりインタフェースクラスは多重継承しても問題が発生しないので、クラスに対して自由に継承させられます。
  • 属性(メンバー変数)を持たない
  • 操作(メンバー関数)は宣言のみで実装を持たない(純粋仮想関数)
インターフェースを使うことにはいろんなメリットがあります。
  • 利用側 : 操作(Compare) を持つことが保証される
  • 継承側 : 操作(Compare) の実装が強制される
例えば、ソートのような処理のインプットで ICompareble を指定すれば、 Compare() が使えることが保証されますし、 実際に ICompareble を継承するクラスでは Compare() を実装しないとコンパイルエラーとなります。

cpp_mixin_interface.png


インターフェースはインターフェースで有用です。 ただ、 多重継承で問題になるのは属性を持つことの方で、 操作の実装を禁止する必要はありません。
「操作の実装を持つ」ということは言い換えるとなんらかの「機能を持つ」ということです。 そういったクラスを継承すると元のクラスに機能を付加することになります。 継承によって機能を追加するためのクラスやその手法を Mixinと呼びます。

例えば、『鯨』というクラスを考えてみます。
ほ乳類、魚類から継承したとするとダイヤモンド継承(ひし形継承)と呼ばれる共通の祖先を持つクラスの継承となり、多重継承で最も問題になる形になります。

ダイヤモンド継承

Mixin を用いると「泳げる」(Swimable) という機能を共に持つとみなすことができます。 ダイヤモンド継承は避けられますし、こちらの方がより自然にクラスによるモデル化ができています。

Mixin

Comparable Mixin

Mixin をさらに Comparable(比較できる) Mixin を具体例として説明していきます。


次のような点クラスについて考えてみます。
ちなみに struct はデフォルトが public なことを除いて class と同じものです。
struct Point
{
  int x;
  int y;
};
点クラスのように 等比、比較演算子のオーバーロードを行うと使いやすくなるクラスは多いと思いますが、 毎回それらを実装するのは面倒です。
しかし、 それらの演算子は比較関数から導くことが出来ます。 これを実装したクラスが Comparable Mixin のクラスです。
template <class T>
class ComparableMixIn
{
 public:
  /// 比較用関数
  ///
  /// | 状態               |  戻り値  |
  /// |--------------------|----------|
  /// | other の方が大きい | 負の値   |
  /// | other と一致       |    0     |
  /// | other の方が小さい | 正の値   |
  /// 
  virtual int Compare(const T &other) const = 0;


  // 演算子の実装
  bool operator==(const T &other) const { return Compare(other) == 0; };
  bool operator!=(const T &other) const { return Compare(other) != 0; };
  bool operator< (const T &other) const { return Compare(other) <  0; };
  bool operator<=(const T &other) const { return Compare(other) <= 0; };
  bool operator> (const T &other) const { return Compare(other) >  0; };
  bool operator>=(const T &other) const { return Compare(other) >= 0; };
};
Mixin クラスの特徴は次のようなものです。 インターフェースと同様に属性を持たないので多重継承ができますが、 機能(操作の実装)を持っているところが違います。
  • 属性を持たない
  • キーとなる関数の宣言(純粋仮想関数)
  • キー関数を使って機能となる関数を実装
ここではキーとなる関数は Compare() です。 この Compare() を使って、 比較できる(Comparable)という機能、 すなわち 等比や比較演算子のオーバーロードの実装を行っています。


一方、使う側である点クラスでは ComparableMixIn を継承し、 Compare() を実装します。
ここには実装のちょっとしたテクニックがあります。 ComparableMixIn は継承先の型をとるテンプレートです。こうすることによって継承先の型による演算子のオーバーロードを可能にしています。
struct Point : public ComparableMixIn<Point>
{
   :

  /// 比較関数.
  /// x で比較し、同じなら y で比較
  virtual int Compare(const Point &other) const override
  {
    return ((x != other.x) ? (x - other.x) : (y - other.y));
  }
};
cpp_mixin.png

この Mixin によって、 点クラスは比較の機能をもつことができるようになります。
  Point a(1, 2), b(2, 3);

  cout << boolalpha;
  cout << "a == b : " << (a == b) << endl;
  cout << "a != b : " << (a != b) << endl;
  cout << "a <  b : " << (a <  b) << endl;
  cout << "a <= b : " << (a <= b) << endl;
  cout << "a >  b : " << (a >  b) << endl;
  cout << "a >= b : " << (a >= b) << endl;
実行結果 :
a == b : false
a != b : true
a <  b : true
a <= b : true
a >  b : false
a >= b : false
なお、Boost::Operators を使うと == から != 、 < から他の不等号を定義できます。 厳密に言うと < さえ定義されていれば、 すべての等、不等号 を導くことができます。 (a == b は a < b && b < a)
これは < 演算子をキー関数とした Mixin ということもできます。

ソースファイル

以上のように Comparable Mixin を使うと Compare() を実装するだけで、等号、不等号の機能を簡単に追加することができます。
大したコード量ではありませんが、ヘッダーを公開していますので、ダウンロード(リンク先を保存)して自由に使ってください。[MIT ライセンス]



 

C++11 範囲に基づく for 文

多くのスクリプト言語では for in の形式でコンテナーの要素にアクセスできます。 Boost や Qt などでは C++ でもなんとかそれを実現させようとマクロを駆使して for_each として定義されていました。
しかし、とうとう C++11 で範囲 for は言語機能として正式に追加されました。
今回はそんな 範囲 for について紹介します。

範囲 for とは

範囲 for というのは C++11 で The range-based for statement(範囲に基づく for 文) として規定されたもので、 配列、リストといったコンテナーの各要素に順にアクセスする for です。


プログラミング中では、配列などのコンテナーに対してループを回して要素にアクセスする というのはよく行う処理です。
その際、 今まではループカウンターを回したり、イテレーターを使っていたと思います。 範囲 for を使えば次のように書けます。
  vector<int> ary = { 3,2,9,6 };

  for (auto elem : ary) {
    cout << elem << endl;
  }  
ループカウンターやイテレーターを書く必要がなく、簡単に書けるようになります。 すっきりしたので、 "コンテナーの要素にアクセスしている" というコードの意図が分かり易くなるという利点もあります。
また、添え字アクセスと違い、イテレーターのようにランダムアクセス以外にも使える汎用性があります。

なお、この考えを一歩進めると関数型のデータ処理となり、 for の逐次処理以外のいろんな処理ができるようになります。

範囲 for の対象

範囲 for に使えるコンテナーは次の 3 つです。
  • STL のコンテナーなど begin(), end() メソッドを持つクラス
  • 配列
  • 初期化リスト
前章のコンテナー以外もサンプルをあげておきます。

配列:
  int cary[] = { 3,2,9,6 };
  
  for (auto elem : cary) {
    cout << elem << endl;
  }
初期化リスト:
  for (auto elem : { 3,2,9,6 }) {
    cout << elem << endl;
  }

要素の型

範囲 for の要素(elem)の定義にはコンテナーの要素の型を記述します。 これには C++11 に型変換として追加された auto が使えます。

その際、関数の引数のようにコンテナーに変更を加えるかどうかによって、 参照(auto&)か const 参照(const auto &)になります。

変更を加える:
  vector<string> strs = { "foo", "bar", "baz" };
  
  for (auto &elem : strs) {
    elem += "!";
  }
  // { "foo!", "bar!", "baz!" }   
変更を加えない:
  vector<string> strs = { "foo", "bar", "baz" };
  
  for (const auto &elem : strs) {
    cout << elem << endl;
  }  
ただし、最初のサンプルのように要素が int などサイズが小さい場合は、 コピーしても問題がないため、ただの auto にします。
また、参照ではなく、ポインターを指定することも出来ます。

std::map の場合

Boost の for_each の時は std::map だとちょっと面倒でした。 範囲 for の場合は問題なく使えます。
  map<string, int> strmap = {
      { "foo", 3 },
      { "bar", 2 },
      { "baz", 9 }
  };
  for (const auto &elem : strmap) {
    cout << elem.first << " - " << elem.second << endl;
  }
std::map の場合の要素は std::pair です。
範囲 for の対象は begin(), end() を持つ必要がありました。 すなわち、各要素にはイテレーターを使ってアクセスしています。
前章では要素の型をいくつか紹介しましたが、 「イテレーターから導けるものが型として使える」と言えます。

範囲 for は次の記述を簡略化したものと考えると分かりやすいと思います。
  for (auto itr = ary.begin() ; itr != ary.end() ; itr++) {
    auto elem = *itr;
    // 要素に対する処理
  }  

サンプルコード

記事中で紹介したサンプルコードのファイルです。


 

C++14 Streams を使った関数型のデータ処理

C# の LINQ、Java の Stream のように「関数型のデータ処理」が多くの言語で取り入れられてきています。 そんな中、C++11,14 での機能追加によって、 C++ でもとうとう Steams ライブラリーを使えば、それができるようになりました。
そこで今回はこの関数型のデータ処理の魅力と Streams の使い方について紹介したいと思います。

関数型データ処理の魅力

関数型データ処理の何が素晴らしいのかを端的にいえば、従来よりもコードを短くかつわかりやすく記述することができることです。

範囲 for の魅力

C++11 では 範囲に基づく for 文 という機能も追加されました。 関数型データ処理の良さの説明のために、まず「範囲 for 」の良さを見てみます。

例えば、 STL コンテナーの各要素に対して、何か処理をする場合、 vector であればループカウンターを回すと思います。 より汎用性を高めるにはイテレーターを使うでしょう。
  vector<int> ary = { 3,2,9,6 };

  for (auto itr = ary.begin() ; itr != ary.end() ; itr++) {
    cout << *itr << endl;
  }  
これを 範囲 for を使って書くと次のようになります。
  vector<int> ary = { 3,2,9,6 };

  for (auto elem : ary) {
    cout << elem << endl;
  }  
比べてみると 何故この機能が追加されたのか分かりやすいのではないでしょうか?
カウンターやイテレーターをいじる操作が無くなるので、短く書けています。 それでいて、余計な処理がないので、コンテナーの要素に対する何か処理しているという意図が分かり易くなっています。

関数型データ処理

関数型データ処理の魅力は 範囲 for に通じるものです。 範囲 for では逐次処理しかできませんが、それを多くの処理に展開したものと言えます。

範囲 for は見方を変えると 要素を引数とした処理を行うコードの固まり(コードブロック)をコンテナーに適用しています。 関数型データ処理ではこのコードブロックの記述に関数内に関数定義が書けるラムダ式を使っています。
  vector<int> ary = { 3,2,9,6 };

  MakeStream::from(ary) |
      for_each([](auto elem) {
          cout << elem << endl;
        });
なお、先ほどの for やラムダ式の引数を (auto elem) にしていますが、 これは要素が整数だからです。サイズの大きな要素の場合はもちろん (const auto &elem) にしておく必要があります。

また、詳しくは後述しますが、 処理を連結できることも分かりやすさを向上しています。 その際、遅延評価によって、効果的な連結になるようになっています。

言語への広がり

関数型のデータ処理というのは特に呼び名がなかったので、 関数型プログラミングでよく使われていることから、私がてきとうに付けた名前です。
関数型のパラダイムでは変数を変更することができません(参照透過性)。 そのため、ループカウンターなどは使えず、こういった高階関数を使うスタイルになります。


関数型というと 「関数型言語は C++ や Java のようなオブジェクト指向言語よりも短く書ける」 と以前は言われていました。
しかし、そのコードが短くなる理由のほとんどが関数型のデータ処理にあります。 このデータ処理スタイルは「関数型でなければ使えない」 といったものではありません。 実際、今では多くの言語で取り入れられてきており、そのメリットを享受することができます。 なかでも、Ruby は言語レベルでコードブロックの機能を持ち、高階関数を使うよりもエレガントに書けるようになっています。

C++14 Streams

関数型のデータ処理を C++ で使えるようにするためのライブラリーが Streamsです。 その実現には C++11, 14 の機能を使っており、 C++14 以上に対応していないとコンパイルは通りません。

ただ、 Java の Streams から来ているのでしょうが、 C++ では stream というのはすでにあるので、名前が紛らわしいです。 処理のイメージとしては stream であっているのですが、「もうちょっと名前はなんとかならなかったのかな」 とは思います。


Streams はヘッダーをインクルードすれば、使えるタイプのライブラリーです。
ヘッダーはホームページの [Download Streams] のリンクからからダウンロードできます。

cpp_streams_dl.png


圧縮ファイルを展開した source ディレクトリーにヘッダーファイルがあります。 インクルードパスに追加し、 "Streams.h" をインクルードすると使えるようになっています。
#include "Stream.h"
Streams ライブラリーのクラスはすべて stream の名前空間で定義されています。
また、 +, - などの演算子のオーバーロードが定義されていますが、 そちらは stream::op の名前空間です。
使用する場合 stream:: をつけるか、 using を使うかです。演算子を使う場合は using を使います。
以降のサンプルでは using を使ったとして、名前空間は記述していません。
using namespace stream;
using namespace stream::op;

Streams の対象となるデータ

Streams の対象となるデータは 配列 と std::vector のような STL コンテナー などです。
ただ、そのままでは適用できないので、 MakeStream::from() の関数で Stream のオブジェクトにします。
Stream<T> MakeStream::from(const Container& cont);
Stream<T> MakeStream::from(T* arr, size_t length);
Stream<T> MakeStream::from(std::initializer_list<T> init);
  vector<int> vec = { 3,2,9,6 };
  int cary[] = { 3,2,9,6 };
  MakeStream::from(vec);
  MakeStream::from(cary, sizeof(cary)/sizeof(cary[0]));  // 配列はサイズも必要
  MakeStream::from({ 3,2,9,6 });                         // 初期化リストでも OK  
Container は正確には STL のコンテナーである必要はなく、 begin, end のメソッドが定義されているクラスであれば何でもかまいません。開始、終了のイテレーターを渡してオブジェクトを作ることもできます。
Stream<T> MakeStream::from(Iterator begin, Iterator end);
他言語ではコンテナー以外のいろいろなものを同じように処理できるのがメリットの一つなのですが、 C++ ではそこまでではありません。しかし、イテレーターにすることによって、多少いろいろなものが処理できるようにはなっています。

input_iterator.cpp : (入力ストリームのイテレーターのサンプル)
  auto seq = MakeStream::from(istream_iterator<int>(cin), istream_iterator<int>());
  cout << endl;
  for (const auto &elem : seq) {
    cout << elem << endl;
  }
$ ./a.exe 
3 2 9 6 <Ctrl+D>
3
2
9
6
また、 from() 以外にも 0,1,2, ... といった無限順列を生成する counter() など多くの生成関数(Genelator)が用意されています。 ただ、テストやサンプル以外で使うことはあまりないです。

基本的な関数

Stream にはたくさんのメソッドが使えます。 しかし、多すぎて関数型のデータ処理になれていない人にとっては 「どれを使えばいいの」ということになると思います。
そこで、まず抑えておくべき重要な 3 つのメソッドについて紹介します。
  1. 写像(map_)
  2. フィルター(filter)
  3. 畳み込み、縮退(reduce)
各関数は " | " 演算子でStream オブジェクトを受け取って適用する形になります。

map_ : 写像

写像というのは map, mapping とも呼ばれる処理で、 配列などのコレクションのメンバーに一つずつ関数を適用して 戻り値で新しいコレクションを作ります。

cs_linq_map.png

Streams では、map はすでに std::map があるので、 map_ という関数名になっています。
MakeStream::from({3, 2, 9, 6})
    | map_([](auto elem) { return elem * 2; });  // 6 4 18 12 
map_ に渡す関数は、各要素を引数にとる関数で、その戻り値が新しいコレクションの要素となります。 渡す関数の戻り値の型を変えれば、 型を変えた新しいコレクションを作ることもでき、用途の広いメソッドです。

filter : フィルター

フィルターはコレクションの中から条件にあう要素を取り出す処理です。

cs_linq_filter.png

MakeStream::from({3, 2, 9, 6})
    | filter([](auto elem) { return elem % 2 == 1; });  // 3 9

reduce : 縮退(畳み込み)

要素を順に取得し、それらを計算に使った結果を返す処理です。
cs_linq_fold.png
この処理は指定した関数の結果を重ねていくため 畳み込み(fold)と呼ばれます。
また、要素が順に減っていって一つの値になるため、縮退(reduce)とも呼ばれます。 Streams では縮退の方の reduce という関数名です。
std::vector<int> src = {3, 2, 9, 6};
MakeStream::from(src) | reduce([](auto sum, auto elem) { return sum + elem; }); // 20
MakeStream::from(src) | reduce([](auto max, auto elem) { return (max < elem) ? elem : max; }); // 9
reduce に渡す関数は 2 つの引数を取り、 2 つ目が各要素で、 関数の戻り値が次に呼ばれた時の 1 つ目の引数です。
合計の例を順に記述すると次のようになります。
{3, 2, 9, 6}

(3, 2) => 3 + 2 ↓
                (5, 9) => 5 + 9  ↓
                                (14, 6) => 14 + 6  ↓
                                                   20
  
渡した関数は 2 つの目の要素から呼ばれ、最初の引数 1 つ目の要素になります。 identity_reduce() を使って、初期値を渡して、最初の要素から処理することもできます。
MakeStream::from(src) | identity_reduce(0, [](auto count, auto elem) { return count + 1; })); // 4
map, filter がコレクションから新しいコレクションを返す関数の基本なのに対し、 reduce はコレクションの各要素から値(スカラー値)を算出 する関数の中でもっとも基本的な関数です。
sum(), max() や count() の関数は予めライブラリーに用意されていますが、 サンプルコードのように reduce() で記述ことが出来ます。

その他の関数

データ処理の定番の関数以外で、抑えておいた方がいいかなと思うものも挙げて置きます。
limit
指定した範囲の要素を取得
MakeStream::counter(1) | limit(3);  // {1 2 3}
    
any, all
要素どれか一つ(すべて)が条件を満たすかどうかの判定。
MakeStream::from({3, 2, 9, 6}) | any([](auto elem) { return (elem % 3) == 0;});  // true
MakeStream::from({3, 2, 9, 6}) | all([](auto elem) { return (elem % 3) == 0;});  // false
    
sort
要素のソート
MakeStream::from({3, 2, 9, 6}) | sort();  // {2 3 6 9}      
    
演算子
Stream オブジェクトに対する四則演算など。
MakeStream::from({3, 2, 9, 6}) / 3.0; // {1.0 0.666667 3.0 2.0}
5 * MakeStream::from({3, 2, 9, 6});   // {15 10 45 30}
MakeStream::from({3, 2, 9}) + MakeStream::from({1, 2, 3}); // {4 4 12}

    
print_to
Stream オブジェクトのダンプ
MakeStream::from({3, 2, 9, 6}) | print_to(std::cout);  // 3 2 9 6      
    

メソッドの連結と遅延評価

メソッドの連結

Stream の関数は " | " 演算子の後に記述しますが、 これを連結して書けるようになっています。
Unix 系のコマンドラインをご存じの人にはパイプみたいと思われるはずです。 パイプのイメージを持ってもらって間違いないです。
MakeStream::from({3, 2, 9, 6})
      | filter([](auto elem) { return elem % 2 == 1; })  // {3 9 }
      | map_([](auto elem)  { return elem * 2; })        // {6 18 }
      | reduce([](auto sum, auto elem) { return sum + elem; });  // 6+18 => 24

連結の終わり

連結できるのは map_() や filter() 関数の戻り値が Stream のオブジェクトだからです。
最後に forEach で逐次処理したり、 reduce で値の算出に使うと連結が終わります。 終わらずに得た変数は範囲 for で使うこともできます。
しかし、 STL コンテナーなどに戻したいといった場合には to_container を呼ぶ必要があります。 container には vector や list を記述し、それぞれのコンテナーへ変換します。
MakeStream::from({3, 2, 9, 6})
      | filter([](auto elem) { return elem % 2 == 1; })  // {3 9 }
      | map_([](auto elem)  { return elem * 2; })        // {6 18 }
      | to_vector();                                     // [6 18 ]

遅延評価

関数を連結して書くと、要素を溜めているため、 ループで書くよりもメモリーがもったいないと思われる人もいるかもしれません。
しかし、必要になるまで実行(評価)されないという遅延評価(Lazy evaluation) の機能によって、 無駄がないようになっています。

前節の連結の処理は一見、次のように処理してるように見えます。
              filter           map
{3, 2, 9, 6}    →   {3, 9}    →   {6, 18}
しかし、実際には遅延評価により、メソッドごとに結果をためるのではなく、 1 要素ずつ流すように次のメソッドに渡していきます。
   filter        map
3    →    3     →    6
2    →    ☓
9    →    9     →    18
6    →    ☓
実際に上記の順で処理されているかは peek() で確認できます。 peek() は渡した関数を実行し、要素をそのまま次に渡す確認用のメソッドです。
  auto lazyseq =
      MakeStream::from({3, 2, 9, 6})
      | peek([](auto elem) { std::cout << "[in]  : " << elem << std::endl; })
      | filter([](auto elem) { return elem % 2 == 1; })
      | peek([](auto elem) { std::cout << " - filter : " << elem << std::endl; })
      | map_([](auto elem)  { return elem * 2; })
      | peek([](auto elem) { std::cout << " - map    : " << elem << std::endl; });
  
  for (auto &elem : lazyseq) {
    std::cout << "[out] : " << elem << std::endl;
  }
実行結果:
[in]  : 3
 - filter : 3
 - map    : 6
[out] : 6
[in]  : 2
[in]  : 9
 - filter : 9
 - map    : 18
[out] : 18
[in]  : 6
なお、遅延評価では必要な時に処理されるため、 sort() だと少し注意が必要です。
ソートという処理を考えたらわかると思いますが、 ソートは全要素が揃わないと完了しない処理です。 そのため、 sort() に関しては流れるように次に渡すのではなく、 そこで一旦要素が溜められることになります。

今回紹介しているサンプルの多くは以下に記述しています。 こちらには sort() の確認用のコードも記述しています。


 
このページをシェア
アクセスカウンター
アクセスランキング
[ジャンルランキング]
コンピュータ
10位
アクセスランキングを見る>>

[サブジャンルランキング]
プログラミング
3位
アクセスランキングを見る>>
カレンダー(アーカイブ)
プルダウン 降順 昇順 年別

10月 | 2017年11月 | 12月
- - - 1 2 3 4
5 6 7 8 9 10 11
12 13 14 15 16 17 18
19 20 21 22 23 24 25
26 27 28 29 30 - -


はてな新着記事
はてな人気記事
ブロとも申請フォーム
プロフィール

yohshiy

Author:yohshiy
職業プログラマー。
仕事は主に C++ ですが、軽い言語マニアなので、色々使っています。

はてブ:yohshiy のブックマーク
Twitter:@yohshiy

サイト紹介
プログラミング好きのブログです。プログラミング関連の話題や公開ソフトの開発記などを雑多に書いてます。ただ、たまに英語やネット系の話になることも。
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。