C++でrangeライブラリを作った

#はじめに
どうもどうも, C++で毎度おなじみいなむ先生ですわ.
この記事はIQが1 Advent Calendar 2017の17日目くらいの記事ですわ.
（IQが１すぎて前日の夕方から構成を考えて、よなよな書いていたのを許して下さい）

#Cranberries Library
Cranberries Libraryはgithubのリポジトリで色々なC++ライブラリが集まってますわ.
言ってしまえば, わたしが趣味でC++14で書いたライブラリの墓場ですわ.

#Craberries.Ranges

まだexperimantalなのですけど, 最近熱心に書いてるライブラリですわ.
rangeライブラリ, IQが１なので車輪の再開発ですわ.

#何ができるの？

rengeを1から作るCreate Module
rangeからrangeを作るView Module
rangeに対する操作を行うOperation Module
の３つからなりますわ.

operator<=(range, module)のようなオーバーロードされた演算子が同名前空間に定義されていてviewを連続で適用することでなんかいい感じのrangeを作ることだできるみたいなものですわ.
そんでもってoperationでなんかいい感じの処理を適用できるのですわ.

create::range(1, 20)                                 // [1,2,3,...,19]
	<= view::take_while([](auto i) {return i < 8; }) // [1,2,3,4,5,6,7]
	<= view::drop(4)                                 // [5,6,7]
	<= operation::write_line();

output

5 6 7

actionというrange自体に操作を行うModuleも作ってみたけど全然ダメ, 設計から考え直しですわ.

#現状実装されているモジュール一覧

##Create Module

• generate_canonical()
  • [0,1)に正規化された一様浮動小数点数乱数の無限レンジ
• generate(generator)
  • generator()によって値を生成する無限レンジ
• range(a,b)
  • [a,b)の整数列を作る有限レンジ
• iterate(init, next)
  • 初期値がv=initで, 次の値をv=next(v)によって生成する無限レンジ
• repeat(value)
  • 永遠にvalueが続く無限レンジ
• read_line(stream)
  • streamから一行づつ値を読み込む有限レンジ
• of(...args)
  • [args...]からなる有限レンジ

##View Module

• range <= take(n)
  • rangeの先頭n要素からなる有限レンジを作る
• range <= chunk()
  • rangeをN要素づつのtupleに固めたレンジを作る
• range1 <= concat(range2)
  • range1の後ろにrange2をくっつけたレンジを作る
• range <= cyclic()
  • rangeが最後までいったら最初に戻って繰り返される無限レンジ作る
• range <= transform(f)
  • 全要素に関数fを適用したレンジを作る
• range <= transform_with_index(f)
  • 全要素eに関数fを適用しつつインデックスiと一緒に固めたtuple, (i,f(e))のレンジを作る
• range1 <= zip_with(range2)
  • range1要素e1とrange2の要素e2をtupleに固めた(e1,e2)のレンジを作る.要素数は要素が少ない方とおなじになる.
• range <= take(n)
  • 先頭からn要素のレンジを作る
• range <= take_while(pred)
  • 先頭の要素から始めて, 初めてpred(e)falseになるまでの要素でレンジを作る.
• range <= drop(n)
  • 先頭のn要素を除いたレンジを作る
• range <= drop_while(pred)
  • 先頭から始めて, 初めてpred(e)がfalseになるまでの要素を除いたレンジを作る
• range <= indexed()
  • インデックスiと要素eのtuple, (i,e)からなるレンジを作る
• range <= filter(pred)
  • pred(e)がtrueになる要素からなるレンジを作る
• range <= shuffle()
  • ランダムにシャッフルされたレンジを作る.無限レンジをシャッフルすることはできない.
• range <= span(i,n)
  • 多分レンジの(0-originで)インデックスi番目からn要素までのレンジを作ると思う

##Operation Module

• range <= write_line(os)
  • 要素をスペース区切りしてosに一行出力する
• range <= peek(f)
  • 全要素に関数fを適用してrangeをそのまま返す
• range <= all(pred)
  • 全要素がpredを満たすかを返す
• range <= none(pred)
  • 全要素がpredを満たさないかを返す
• range <= any(pred)
  • ある要素がpredを満たすかを返す
• range <= foldl(op)
  • レンジの要素[e1, e2, e3, ...]に対して, op(op(op(e1,e2), e3),e4)のように関数を適用し畳み込んだ結果を返す
• range <= foldr(op)
  • レンジの要素[e1, e2, e3, ...]に対して, op(e1, op(e2, op(e3, ...)))のように関数を適用し畳み込んだ結果を返す
• range <= sum()
  • 多分, 全要素を足し算して返すやつでしょう
• range <= deconstruct()
  • 先頭からN要素をtupleに固めて返すと思われます
• range <= convert()
  • rangeをContainerに変換するはずです

#内部実装

基本的にrangesは全部がoutput iteratorを取得できるiterableなクラスになっている.
しかし普通のコンテナとおもむきが大分と違う.
C#のLinqに近い気がするな.

##Sentinel Range

rangesライブラリによって生成されるレンジを勝手にそう呼称している.
Sentinel Rangeは内部に配列で全部の値を格納していたりはしない.
必要な情報だけを保持している.

###Create系

初期値や漸化式, 終了条件等の情報を保持している.
例えば, Create Moduleによって作られるRangedクラスを見てみる.

ranged.hpp

#ifndef CRANBERRIES_RANGES_SENTINEL_RANGES_RANGE_HPP
#define CRANBERRIES_RANGES_SENTINEL_RANGES_RANGE_HPP
#include "../ranges_tag.hpp"
#include "../sentinel_iterator.hpp"
#include "../concepts.hpp"
#include "../../functional.hpp"


namespace cranberries {
namespace experimental {
namespace ranges {


template < class ValueType, bool Reversable >
class Ranged
	: private tag::sentinel_range_tag
{
	class forward_sentinel {
		ValueType value;
		ValueType upper_bound;
		equal_to<> eq{};
	public:
		using value_type = ValueType;
		forward_sentinel(ValueType _1, ValueType _2) : value{ _1 }, upper_bound{ _2 } {}
		forward_sentinel(const forward_sentinel&) = default;
		auto get() { return value; }
		void next() { ++value; }
		bool is_end() { return eq(upper_bound, value); }
	};
	class reverse_sentinel {
		ValueType value;
		ValueType lower_bound;
		equal_to<> eq{};
	public:
		using value_type = ValueType;
		reverse_sentinel(ValueType init, ValueType upper) : value{ --upper }, lower_bound{ --init } {}
		reverse_sentinel(const reverse_sentinel&) = default;
		auto get() { return value; }
		void next() { --value; }
		bool is_end() { return eq(value, lower_bound); }
	};
public:
	using forward_sentinel = forward_sentinel;
	using reverse_sentinel = reverse_sentinel;
	using iterator = sentinel_iterator<forward_sentinel>;
	using reverse_iterator = sentinel_iterator<reverse_sentinel>;
	using value_type = ValueType;

	Ranged(value_type _1, value_type _2) : init{ _1 }, bound{ _2 } {}

	iterator begin() const { return { std::make_unique<forward_sentinel>(init, bound) }; }
	iterator end() const { return {}; }
	reverse_iterator rbegin() const { return { std::make_unique<reverse_sentinel>(init, bound) }; }
	reverse_iterator rend() const { return {}; }
private:
	value_type init;
	value_type bound;
};

template < class ValueType >
class Ranged<ValueType, false>
	: private tag::sentinel_range_tag
{
	class forward_sentinel {
		ValueType value;
		ValueType upper_bound;
		equal_to<> eq{};
	public:
		using value_type = ValueType;
		forward_sentinel(ValueType _1, ValueType _2) : value{ _1 }, upper_bound{ _2 } {}
		forward_sentinel(const forward_sentinel&) = default;
		auto get() { return value; }
		void next() { ++value; }
		bool is_end() { return eq(upper_bound, value); }
	};
public:
	using forward_sentinel = forward_sentinel;
	using iterator = sentinel_iterator<forward_sentinel>;
	using value_type = ValueType;

	Ranged(value_type _1, value_type _2) : init{ _1 }, bound{ _2 } {}

	iterator begin() const { return { std::make_unique<forward_sentinel>(init, bound) }; }
	iterator end() const { return {}; }
private:
	value_type init;
	value_type bound;
};


namespace create {

	template < typename ValueType,
		concepts::concept_required<ValueType,
			concepts::incrementable,
			concepts::regular_type
		> = nullptr
	>
	Ranged<ValueType, concepts::required_v<ValueType, concepts::decrementable>>
	range(ValueType init, ValueType upper_bound)
		{ return {init, upper_bound}; }
}



}}}
#endif // !CRANBERRIES_RANGES_SENTINEL_RANGES_GENERATE_CANONICAL_HPP

とてもごちゃごちゃしているが, 重要なのはメンバ変数がValueTypeの配列ではなく初期値と上界値になっていることだ.
Sentinel Rangeは実際の計算を遅延評価している.
よって, Sentinel Range自体にアクセスして値を取り出したり書き換えたりはできない設計になっている.
View ModuleのRangeも全てこのコンセプトになっている.
Sentinel Rangeから値を取り出すにはイテレータインターフェイスを用いる.

###View系

viewはrangeを束縛し, ラップするクラスである.
viewにrangeを束縛するとき, rangeが左辺値なら参照で
右辺値ならムーブ（ムーブがなければコピー）で束縛する.

右辺値のrangeからviewを作った場合, viewはイテレータを作るする際にムーブができない場合range自体をコピーする.

連続で適用するとviewクラスに多重ラップされる.
右辺値のrangeからviewを作った場合, viewはイテレータを作るする際にムーブができない場合range自体を何度もコピーする.
ムーブできたとしてもムーブコンストラクトが繰り返されることになる.

例えば, 値を抽出するview::filterの実装を見てみる.

#ifndef CRANBERRIES_RANGES_VIEW_ADAPTORS_FILTER_HPP
#define CRANBERRIES_RANGES_VIEW_ADAPTORS_FILTER_HPP
#include "../ranges_tag.hpp"
#include "../sentinel_iterator.hpp"
#include "../../../utility/utility.hpp"
#include "../detail/default_sentinel.hpp"
#include <type_traits>

namespace cranberries {
namespace experimental {
namespace ranges {

template < class Range, class Pred >
class Filter
	: private tag::sentinel_range_tag
{
	class forward_sentinel {
	public:
		using value_type = typename std::decay_t<Range>::value_type;
		forward_sentinel(Range range, Pred pred)
			: range_{ range }
			, iter{ cranberries::back_magic::begin(range_) }
			, last{ cranberries::back_magic::end(range_) }
			, pred(pred)
		{
			if (!pred(*iter)) next();
		}

		auto get() { return *iter; }
		void next() {
			++iter;
			while (!pred(*iter) && iter != last) ++iter;
		}
		bool is_end() { return iter == last; }
	private:
		Range range_;
		typename std::decay_t<Range>::iterator iter;
		typename std::decay_t<Range>::iterator last;
		Pred pred;
	};
public:
	using value_type = typename std::decay_t<Range>::value_type;
	using sentinel = forward_sentinel;
	using iterator = sentinel_iterator<sentinel>;
	using reverse_sentinel = magic_arts::default_reverse_sentinel<value_type>;
	using reverse_iterator = sentinel_iterator<reverse_sentinel>;

	template < class Range_, class Pred_ >
	Filter(Range_&& range, Pred_&& pred)
		: range{ std::forward<Range_>(range) }
		, pred{ std::forward<Pred_>(pred) }
	{}

	iterator begin() const { return { std::make_unique<sentinel>(range, pred) }; }
	iterator end() const { return {}; }
	reverse_iterator rbegin() const { return { std::make_unique<reverse_sentinel>(*this) }; }
	reverse_iterator rend() const { return {}; }

private:
	Range range;
	Pred pred;
};

namespace view {
	template < typename Pred >
	auto filter(Pred&& pred) { return make_proxy<Filter>::embedded(std::forward<Pred>(pred)); }
}

}}}
#endif

ごちゃごちゃしているが, rangeと関数オブジェクト（filter用の条件）のみを保持しているというところが大事である.

viewから値を取り出すのもイテレータインターフェイスを用いる.

##Sentinel Iterator

Sentinel Rangeからbegin-endでSentinel Iteratorを取得できる.
Sentinel IteratorはOutput Iteratorである.
値を取り出すこと, イテレータを前進することができる.

つまり, Operation Moduleなど介さなくてもfor文で愚直にイテレートできる.

for ( auto const& e: create::range(1,10) ){
    std::cout << e << "\n";
}

Sentinel IteratorはSentinel Rangeから初期状態, 値を進める方法, 終端判定方法などを知っているクラス（Sentinel）をunique_ptrとして受取る.
Sentinelを介してSentinel Iteratorは値を進めることができるし, 終端に達したかを知ることができる.
SentinelはSentinel Rangeのプライベートな内部クラスとして実装されている.
先程のコードで出てきたforward_sentinelとかreverse_sentinelがそれである.
Sentinel Iteratorはデフォルトコンストラクタが終端イテレータを返すタイプのイテレータになっていて, Sentinel Rangeのendはそれを返す.

enum class sentinel_flag {
	on, off
};


template < class Sentinel >
class sentinel_iterator
	: private tag::sentinel_iterator_tag
{
protected:
	// copy construct/copy asignment implementation
	sentinel_iterator deep_copy(const sentinel_iterator& iter) & {
		this->swap(sentinel_iterator{ iter });
		return *this;
	}
public:
	// For std::iterator_traits<sentinel_iterator>
	using value_type = typename Sentinel::value_type;
	using difference_type = int;
	using pointer = std::nullptr_t; // disable
	using reference = value_type&;
	using iterator_category = std::output_iterator_tag;

	// Constructor for Sentinel Range
	sentinel_iterator(std::unique_ptr<Sentinel>&& ptr)
		: sentinel{ std::move(ptr) }, is_sentinel{ sentinel_flag::off } {}


	// Default Constructor for End Sentinel
	sentinel_iterator()
		: sentinel{ nullptr }, is_sentinel{ sentinel_flag::on } {};

	// Copy constructor/Copy assignment operator
	/*[Note: Copy constructor makes deep-copied sentinel_iterator.
		It meens copying current state of sentinel.
		- end note ]*/
	sentinel_iterator(const sentinel_iterator& iter)
		: sentinel{ std::make_unique<Sentinel>(iter.sentinel) } {}
	
	sentinel_iterator& operator=(const sentinel_iterator& rhs) { return deep_copy(rhs); }


	// Move constructor/Move assignment operator
	sentinel_iterator& operator=(sentinel_iterator&&) = default;
	sentinel_iterator(sentinel_iterator&&) = default;
	
	// Destructor
	~sentinel_iterator() = default;

	// For iterator requirements
	void swap(sentinel_iterator& iter) & { std::swap(sentinel, iter.sentinel); }
	void swap(sentinel_iterator&& iter) & { std::swap(sentinel, iter.sentinel); }

	// Dereferene 
	decltype(auto) get() const { return sentinel->get(); }
	decltype(auto) operator*() const { return sentinel->get(); }

	// Increment
	bool next() { return sentinel->next(); }
	decltype(auto) operator++() { return sentinel->next(), *this; }
	auto operator++(int) { return make_finally([&]() { sentinel->next(); }), deep_copy(*this); }

	// Sentinel invoke
	bool is_end() const { return sentinel->is_end(); }

	bool operator==(const sentinel_iterator& iter) const {
		return is_sentinel == sentinel_flag::off ?
			iter.is_sentinel == sentinel_flag::off ? false : this->is_end()
			: iter.is_end();
	}
	bool operator!=(const sentinel_iterator& iter) const {
		return is_sentinel == sentinel_flag::off ?
			iter.is_sentinel == sentinel_flag::off ? true : !this->is_end()
			: !iter.is_end();
	}

private:
	// Iteration state
	/*[Note: This is implementation of Sentinel Iterator.
		It manages iteration, value access and end-point checking.
	-end note]*/
	std::unique_ptr<Sentinel> sentinel;

	sentinel_flag is_sentinel;
};

#まとめ

range-v3を使いましょう.