読者です 読者をやめる 読者になる 読者になる

Rokiのチラ裏

学生による学習のログ

比較的有名だと思われるC++イディオムを巡る

前書き

この記事はC++ Advent Calender 2016、10日の記事です。

こんにちは。

f:id:Rok1:20161202130726g:plain

12月10日はイディオムの日なので、この記事では比較的有名だと思われるC++イディオムを一通り巡ります(順不同)。しかしAdvent Calenderの流れを見るに、恐らくその多くが既知のものなのではと思われるので適当に読み飛ばしてください。スイスイと読み終わるかと思います。

idiom is 何

ソフトウェア工学に於けるイディオム(英: Idiom)は、アルゴリズムやプログラミングのノウハウ、チップを集めたものである。- wikipedia

Pimpl

Pointer To Implementationの略*1で、クラスの実装を呼び出し側から完全に分離してカプセル化を図る手法です。Pimplイディオム適用前がこういった構成だとして。

// test.hpp
struct X final{
    X(const std::string& ="");
    std::size_t size()const noexcept;
private:
    std::string s;
};
#include"test.hpp"
X::X(const std::string& str):s(str){}
std::size_t X::size()const noexcept{return s.size();}

privateメンバがヘッダーに見えています。そこで各種インプリメントを内包したクラスを別途用意し間接参照する事で、privateメンバも分離させます。

// test.hpp
struct X final{
    X(const std::string& ="");
    ~X();
    std::size_t size()const noexcept;
private:
    struct Impl;
    std::unique_ptr<Impl> impl_;
};
#include"test.hpp"
struct X::Impl{
    Impl(const std::string& str):s(str){}
    std::string s;
};

X::X(const std::string& str):impl_(new Impl(str)){}
X::~X()=default;

std::size_t X::size()const noexcept{return impl_->s.size();}

Pimplイディオムによって実装の分離が行われるので、各種インプリメントを内包できるだけでなく、コンパイル時間の減少にも貢献できますが勿論処理を呼び出す際にipml_を経由した間接参照分のオーバーヘッドコストは発生してしまいます。

The Detection idiom

C++1z(17)でtype_traitsヘッダに追加されるstd::void_tを利用したイディオムです。std::void_tのインプリメントはこのようになっています。

template<class...>
using void_t=void;

何を入れてもvoidが返るので入れたい放題入れられますね。どのように使うかと言うと、例えばそのクラスがイテレータを持つかを検査してみます。

template<class,class=std::void_t<>>
constexpr bool has_iterator_v=std::false_type::value;
template<class Tp>
constexpr bool has_iterator_v<Tp,std::void_t<typename Tp::iterator::iterator_category>> =std::true_type::value;

int main()
{
    std::cout<<std::boolalpha<<has_iterator_v<std::vector<int>><<std::endl; // true
}

N4502にはこの手法を利用したdetection toolkitやimplementing toolkitなどが提案されています。

CRTP

CRTPとは、Curiously Recurring Template Patternの略でよく直訳されていますが、奇妙に再起したテンプレートパターンと言われています。

template<class Inher>
struct X{};
struct Derived:X<Derived>{}; // CRTP

基本クラスから派生クラスが見えますので、それを利用した様々なパターンもまた生まれています。例えば、純粋仮想関数などを用いずに静的に派生クラスに対して当該実装を強要したり。

template<class Tp>
struct base{
    void f()const{static_cast<Tp>(this)->f();}
};
struct derived:private base<derived>{
    void f()const{}
};

しかしこの記述だけでは派生クラス側で実装を行わなくてもメンバを呼び出さなければエラーを吐かれないので

template<class Tp,void (Tp::*)()>
struct signature_f_1{using type=Tp;};

template<class Tp,class=Tp>
struct signature_f_2:std::false_type{};
template<class Tp>
struct signature_f_2<Tp,typename signature_f_1<Tp,&Tp::f>::type>:std::true_type{};

template<class Tp>
constexpr bool signature_f_v=signature_f_2<Tp>::value;

template<class Derived>
struct base{
    virtual ~base()=default;
    base(){static_assert(signature_f_v<Derived>,"u must define function f");}
    void f(){return static_cast<Derived*>(this)->f();}
};

このようにTMPでstatic_assertなどに投げると良いかと思います。
CRTPを活用したもう一つの例として、演算子の自動生成などが有名です。*2

template<class Tp>
class equal_comp{
    friend bool operator!=(const Tp& lhs,const Tp& rhs){return !lhs.operator==(rhs);}
};

class X final:equal_comp<X>{
    std::string s;
public:
    bool operator==(const X& rhs)const{return rhs.s==s;}
    explicit X(const std::string& s):s(s){}
};

int main()
{
    using namespace std::string_literals;
    X a("hoge"s),b("foo"s);
    assert(a!=b);
}

==!=のようにそれぞれの演算子が対になっている演算子は、その片方の実装が決まった瞬間に当然もう片方の実装が確立するので自動生成が可能となります。

No Copyable mix-in

継承されたクラスはコピーが禁止であると明快に表現できるイディオムです。

class noCopyable{
    noCopyable(const noCopyable&)=delete;
    noCopyable& operator=(const noCopyable&)=delete;
protected:
    noCopyable()=default;
    ~noCopyable()=default;
};
struct X:private noCopyable{};

boost nocopyableにほぼ同様のインプリメントがあります。
しかし、この実装は多重継承を挟んだ場合、少々EBO最適化を妨げる事となります。

struct X:private noCopyable{};
struct Y:private noCopyable{};
struct Z:X,Y{};

#include<iostream>
int main()
{
    std::cout<<sizeof(Z)<<std::endl; // 2
}

noCopyableはEmpty ClassなのでEBO最適化が効いても良いはずですが、どんなに最適化レベルを高く設定してもこれは絶対に最適化されません。何故ならば異なるサブオブジェクトがそれぞれ同じ基底クラスを継承している時、双方共に異なるアドレスを持つことが規格によって定められているためです。異なるアドレスを持つためには、それぞれが最低限のサイズを持たなければなりません。そこで、CRTPと併用します。

template<class>
class noCopyable{
    noCopyable(const noCopyable&)=delete;
    noCopyable& operator=(const noCopyable&)=delete;
protected:
    noCopyable()=default;
    ~noCopyable()=default;
};
struct X:private noCopyable<X>{};
struct Y:private noCopyable<Y>{};
struct Z:X,Y{};

int main()
{
    std::cout<<sizeof(Z)<<std::endl; // 1
}

CRTPにする事でそれぞれが別の基底クラスを継承するためEBO最適化が効くようになります。

RAII

Resource Acquisition Is Initializationの略で、リソースの確保と解放をオブジェクトの初期化と破棄処理に結び付けるイディオムです。例えば、動的確保したリソースの生成と解放、Cスタイルのファイルオープンとクローズなど、初期化処理となんらかの解放処理をそれぞれコンストラクタとデストラクタに結びつけたりなど...。例としてOS XAPIを用いてインタフェースに設定されているIPアドレスを取得するコードを以下に示します。

#include<cstring>
#include<iostream>
#include<sys/types.h>
#include<sys/socket.h>
#include<sys/ioctl.h>
#include<unistd.h>
#include<netinet/in.h>
#include<net/if.h>
#include<arpa/inet.h>

struct IP final{
    explicit IP():fd(socket(AF_INET,SOCK_DGRAM,0))
    {
        ifr.ifr_addr.sa_family=AF_INET;
        std::strncpy(ifr.ifr_name,"en0",IFNAMSIZ-1);
    }
    IP(const IP&)=delete;
    IP& operator=(const IP&)=delete;
    IP(IP&& rhs):fd(socket(AF_INET,SOCK_DGRAM,0))
    {
        ifr.ifr_addr.sa_family=rhs.ifr.ifr_addr.sa_family;
        std::strncpy(ifr.ifr_name,"en0",IFNAMSIZ-1);
        close(rhs.fd);
        rhs.fd=0;
    }
    IP& operator=(IP&& rhs)
    {
        if(this==&rhs)return *this;
        ifr.ifr_addr.sa_family=rhs.ifr.ifr_addr.sa_family;
        std::strncpy(ifr.ifr_name,"en0",IFNAMSIZ-1);
        fd=socket(AF_INET,SOCK_DGRAM,0);
        close(rhs.fd);
        rhs.fd=0;
        return *this;
    }
    void print()
    {
        ioctl(fd,SIOCGIFADDR,&ifr);
        std::cout<<inet_ntoa(reinterpret_cast<sockaddr_in *>(&ifr.ifr_addr)->sin_addr)<<std::endl;
    }
    ~IP(){close(fd);}

    int fd=0;
    ifreq ifr;
};

int main()
{
    IP().print();
}

RAIIはとても一般的で汎用性の高い手法です。よって、RAIIという形自体をラッピングしたunique_resourceというラッパーが標準化委員会の文書N4189で提案されていたりします*3。また、これはRAIIイディオムを用いているunique_ptrのリソース管理法に基づいています*4。 これは先取ってboostライセンスの下公開されています。unique_resourceを用いて先ほどのコードを書き直して見ると以下のようになります。*5

#include<cstring>
#include<iostream>
#include<my_experimental/unique_resource.hpp> // % git clone https://github.com/okdshin/unique_resource.git

#include<sys/types.h>
#include<sys/socket.h>
#include<sys/ioctl.h>
#include<unistd.h>
#include<netinet/in.h>
#include<net/if.h>
#include<arpa/inet.h>

int main()
{
    auto fd=std_experimental::make_unique_resource(socket(AF_INET,SOCK_DGRAM,0),[](auto fd){close(fd);});
    
    ifreq ifr;
    ifr.ifr_addr.sa_family=AF_INET;
    std::strncpy(ifr.ifr_name,"en0",IFNAMSIZ-1);
    ioctl(fd,SIOCGIFADDR,&ifr);
    
    std::cout<<inet_ntoa(reinterpret_cast<sockaddr_in *>(&ifr.ifr_addr)->sin_addr)<<std::endl;
}

(ラッピング範囲が異なりますがキニシナイ...)

cheked delete

規格5.3.5/5で、delete 式によって不完全型をdeleteに渡すことが許可されています。しかしトライバルなデストラクタでないか、独自のdelete演算子を定義している場合、未定義動作になります。未定義動作はよろしくないので、delete 対象の型が不完全型の場合にコンパイラにエラーを出させようというイディオムです。

template <class T>
inline void cheked_delete(T*& p)
{
    typedef char type[sizeof(T)?1:-1];
    (void)sizeof(type);    
    delete p;
    p=nullptr;
}

不完全型が渡された時、配列の要素数を負数としてtypedefするためエラーになるという寸法です。boost::checked_deleteに同様のインプリメントがあります。

Expression Template

式テンプレートと呼ばれるイディオムです。まず、このようなクラスがあったとします。*6

template<std::size_t N>
struct Vector final{
    Vector():data{}{}
    template<class... Float>
    explicit Vector(Float&&... x)noexcept:data{std::forward<Float>(x)…}
    {}
    Vector(const Vector& x)noexcept
    {
        int c=0;
        for(auto& value:data)value=x[c++];
    }
    Vector& operator=(const Vector&)=default;
    float operator[](const std::size_t& index)const noexcept{return data[index];}
    Vector operator+(const Vector& x)noexcept
    {
        auto tmp=x;
        std::size_t i=0;
        for(auto& value:tmp){value+=data[i]; ++i;}
        return tmp;
    }
private:
    std::array<float,N> data;
};

テンプレートパラメータで次元数を指定する簡単な線形代数ベクトルクラスです。このクラスを使って以下のような操作をします。

template<class... Float>
Vector<sizeof...(Float)> make_Vector(Float&&... fl)
{
    return Vector<sizeof...(Float)>(std::forward<Float>(fl)...);
}

int main()
{
    auto ar=std::experimental::make_array(make_Vector(1.1f,2.2f,3.3f),make_Vector(1.2f,2.3f,3.4f),make_Vector(1.3f,2.4f,3.5f));
    Vector<3> result;
    result=ar[0]+ar[1]+ar[2];
}

この時、加算の部分で一時オブジェクトが少なくとも二回は生成されてしまいます。op+の部分で一時オブジェクトを生成しているので当然の結果と言えますが、もっと効率良く数値演算ができないものでしょうか。この問題に対して、式の構造を一旦保存し対象部分がきたらその式内容の演算を行わせるというのが、Expression templateイディオムと言われるものです。この場合では、加算式が渡されるコンストラクト時とop=時で適応させます。
まず、加算の式構造を保存するためのクラスとそれを受け取れるようop+を用意します。

template<class LType,class RType>
struct Plus{
    Plus(const LType& lhs,const RType& rhs)noexcept:l_(lhs),r_(rhs){}
    float operator[](const std::size_t& index)const noexcept{return l_[index]+r_[index];}
private:
    const LType& l_;
    const RType& r_;
};

template<class LType,class RType>
auto operator+(const LType& l,const RType& r){return Plus<LType,RType>(l,r);}

これにより関数型言語的な式構造を作る事ができます。そしてこれらを展開するコンストラクタとop=を設定します。

template<std::size_t N>
struct Vector final{
// ... 
    template<class LType,class RType>
    Vector(const Plus<LType,RType>&r)noexcept
    {
        std::size_t c=0;
        for(auto& value:data)value=r[c++];
    }

    template<class LType,class RType>
    Vector& operator=(const Plus<LType,RType>& r)noexcept
    {
        std::size_t c=0;
        for(auto& value:data)value=r[c++];
        return *this;
    }
// ...

これらによって、op=まで演算処理が遅延され一時オブジェクトが一切生成されなくなります。 これだけでも問題自体は解決していますが、さらに汎用的にするため、他の演算子と併用する事のできる設計にします。

template<class LType,class Operator,class RType>
struct Expression{
    Expression(const LType& lhs,const RType& rhs):l_(lhs),r_(rhs){}
    constexpr float operator[](const std::size_t& index)const noexcept{return Operator::Apply(l_[index],r_[index]);}
private:
    const LType& l_;
    const RType& r_;
};

struct Plus{
    template<typename T>
    static  T Apply(const T& lhs,const T& rhs){return lhs+rhs;}
};
struct Minus{
    template<typename T>
    static T Apply(const T& lhs,const T& rhs){return lhs-rhs;}
};
struct Multiply{
    template<typename T>
    static T Apply(const T& lhs,const T& rhs){return lhs*rhs;}
};
struct Division{
    template<typename T>
    static T Apply(const T& lhs,const T& rhs){return rhs?lhs/rhs:rhs;}
};

template<class LType,class RType>
constexpr auto operator+(const LType& l,const RType& r){return Expression<LType,Plus,RType>(l,r);}
template<class LType,class RType>
constexpr auto operator-(const LType& l,const RType& r){return Expression<LType,Minus,RType>(l,r);}
template<class LType,class RType>
constexpr auto operator*(const LType& l,const RType& r){return Expression<LType,Multiply,RType>(l,r);}
template<class LType,class RType>
constexpr auto operator/(const LType& l,const RType& r){return Expression<LType,Division,RType>(l,r);}
// etc..

template<std::size_t N>
struct Vector final{
// ...
    template<class LType,class Operator,class RType>
    Vector(const Expression<LType,Operator,RType>& r)noexcept
    {
        std::size_t c=0;
        for(auto& value:data)value=r[c++];
    }   
    template<class LType,class Operator,class RType>
    Vector& operator=(const Expression<LType,Operator,RType>& r)noexcept
    {
        std::size_t c=0;
        for(auto& value:data)value=r[c++];
        return *this;
    }
// ...

このように演算子ごとにインプリメントを分離する事で汎用性だけでなく内部インプリメント自身に注力する事ができます。

Type Erasure

型情報を消去する手法です。この手法を用いたダックタイピングなどは有名です。*7

struct Duck{
    void call()const noexcept{std::cout<<"gaa"<<std::endl;}
};
struct Dog{
    void call()const noexcept{std::cout<<"bow"<<std::endl;}
};

struct Human{
    template<class Tp,class=std::enable_if<!std::is_same<std::remove_reference_t<Tp>,Human>::value>>
    Human(Tp&& x):ptr(new Erasure<Tp>(std::forward<Tp>(x))){} 
    void touch()const noexcept{ptr->invoke();}
private:
    struct ErasureBase{
        virtual ~ErasureBase()=default;
        virtual void invoke()const noexcept=0;
    };
    template<class Tp>
    struct Erasure final:ErasureBase{
        constexpr Erasure(const Tp& target)noexcept:target_(target){}
        void invoke()const noexcept override{target_.call();}
    private:
        Tp target_;
    };
    std::shared_ptr<ErasureBase> ptr;
};

int main()
{
    Duck duck;
    Dog dog;

    Human h(std::move(duck));
    h.touch(); // gaa
    Human h1(std::move(dog));
    h1.touch(); // bow
}

テンプレート派生クラスの動的生成されたインスタンスを非テンプレート基底クラス型のポインターで指す事で型情報を消去しています。
また、TypeErasureには仮想関数テーブルを自作するといったような手法も存在します。

struct X{
    template<class Tp>
    explicit X(Tp& oth)noexcept
        :this_(&oth),
        vptr_(&vtable_init<Tp>::vtbl)
    {}
    void func()const noexcept{vptr_->func(this_);}
private:
    struct vtable{void (*func)(void*);}* vptr_;
    template<class Tp>
    struct vtable_init{
        static vtable vtbl;
        static void func(void* this_){static_cast<Tp*>(this_)->func();}
    };
    void* this_;
};

template<class Tp>
X::vtable X::vtable_init<Tp>::vtbl={&X::vtable_init<Tp>::func};

struct A{
    void func()const noexcept{std::cout<<"A::"<<__func__<<std::endl;}
};

int main()
{
    A a;
    X x(a);
    x.func();
}

staticであるvtblオブジェクトは、同クラスのfunc関数のポインタを持っています。それをvptr_が指します。このタイミングで型消去と同時にvtable_initへ型情報を送出していると言えるでしょう。func()関数がユーザーから呼び出されると、vptr_の指すfunc関数ポインタの引数はvoidであり、差し込む変数もvoid*8ですが、vptr_がインスタンス化される時に_Tpが確定しているため、static_castが正しく処理されA::func()が呼び出されます。このTypeErasureという手法はBoost.any*9やstd::function、スマートポインタなどで使われている事でも有名です。

Address of

operator&() がオーバーロードされていたりプライベートにあってもアドレスを取得する事ができるイディオムです。

struct useless_type{};
class non_addressable{
    useless_type operator&()const;
};

template<class Tp>
Tp* address_of(Tp& v)
{
    return reinterpret_cast<Tp*>(& const_cast<char&>(reinterpret_cast<const volatile char&>(v)));
}

int main()
{
    non_addressable na;
    non_addressable* naptr=address_of(na);
}

C++11以降、<memory>ヘッダに同機能が実装されています。*10

Coercion by Member Template

クラスBがAから派生されていてB型のオブジェクトへのポインタはA型のポインタに代入できますがこれらの型の複合型は、その基となった型の関係を共有しません。例えばtemplate_class<B>はtemplate_class<A> に代入可能ではありません。

class A{};
struct B:A{};
template<class T>
class template_class{};

A* aptr;
B* bptr;
aptr=bptr;

template_class<A> tca;
template_class<B> tcb;
tca=tcb; // ill-formed

しかしこれを許容する事でスマートポインタのようなラッパークラスでの扱いで有用的となる時があります。それを実現するのがCoercion by Member Templateイディオムです。

class A{};
struct B:A{};

template<class T>
struct ptr_wrapper{
    ptr_wrapper():ptr(nullptr){}
    // ...
    template<class U>
    ptr_wrapper(const ptr_wrapper<U>& p):ptr(p.ptr){}
    template<class U>
    ptr_wrapper& operator=(const ptr_wrapper<U>& p)
    {
        ptr=p.ptr;
        return *this;
    }   
    T* ptr;
};

非常に単純です。初期化、代入時に暗黙の変換が認められていなければならないので、その部分で型チェックができます。

Concrete Data Type

ヒープ割り当てを強制、許可、禁止等制御する事でオブジェクトのスコープと生存期間を制御できるイディオムです。これらは単純にクラスでのアクセス指定子を用いる事で簡単に実現ができます。例えば、クラスに動的な割り当てを強制する場合。

namespace n{
    struct X{
        virtual ~X(){}
    };
    struct Y:X{
        Y()=default;
    protected:
        ~Y()override=default;
    };
}

namespace n1{
    struct Y final{
        static Y* instance(){return new Y();}
        void destroy(){delete this;}
    protected:
        Y()=default;
        ~Y()=default;
    };
}

int main()
{
    n::Y obj; // protectedのため通らない
    std::unique_ptr<n::X> ptr(new n::Y());

    n1::Y obj1; // protectedのため通らない
    n1::Y* ptr1=n1::Y::instance();
    ptr1->destroy();
}

逆に、scoped variable(a.k.a. automatic variable)を強制する場合。

class Scoped_variable{
    static void* operator new(std::size_t);
    static void* operator new(std::size_t,void*);
};

int main()
{
    Scoped_variable a; // possible

    Scoped_variable* b=new Scoped_variable(); // Standard new and nothrow new are not allowed

    void* buf=::operator new(sizeof(Scoped_variable));
    Scoped_variable* c=new(buf) Scoped_variable; // Placement new is also not allowed
}

Extension Member Function

C♯の拡張メゾッドのような、既存のクラスに対してメンバ関数の拡張をoperatorオーバーロードを駆使してシミュレートするイディオムです。 例えば、std::vectorへprintなる全要素を出力させる拡張メンバを作成するとすると...*11

const struct Listed_print{
    using result_type=void;

    template<class Range>
    void operator()(const Range& r)
    {
        std::copy(r.cbegin(),r.cend(),std::experimental::make_ostream_joiner(std::cout,","));
    }
}listed_print={};

template<class Range,class F>
typename std::result_of<F(Range&)>::type operator|(const Range& r,F function)
{
    return function(r);
}


int main()
{
    std::vector<int> v{1,2,3,4,5};
    v | listed_print;
}

とても単純ですね。戻り値が必要な場合、シグネチャからargument部分を抽出してresult_ofメタ関数から戻り型を引き抜きます。

template<class>
struct argument_of;
template<class R,class Arg>
struct argument_of<R(Arg)>{
    using type=Arg;
};

const struct Listed_print{
    template<class Sig>
    struct result:public std::decay_t<std::remove_cv_t<typename argument_of<Sig>::type>>{};

    template<class Range>
    const Range& operator()(const Range& r)const
    {
        std::copy(r.cbegin(),r.cend(),std::experimental::make_ostream_joiner(std::cout,","));
        std::cout<<std::endl;
        return r;
    }
}listed_print={};

template<class Range,class F>
typename std::result_of<F(const Range&)>::type
operator|(const Range& r,F function)
{
    return function(r);
}

まあ、現代ではこれは以下のように書けます。便利な時代になったものですね。

const struct Listed_print{
    template<class Range>
    const Range& operator()(const Range& r)const
    {
        std::copy(r.cbegin(),r.cend(),std::experimental::make_ostream_joiner(std::cout,","));
        std::cout<<std::endl;
        return r;
    }
}listed_print={};

template<class Range,class F>
auto operator|(const Range& r,F function)
{
    return function(r);
}

また、Extention Member Functionではイテレータアダプタを作る事でより効率的な操作が可能になる場合があります。例えば以下のように、連続的にExtention Member Functionを適用する場合...

static const auto reverse=[](auto& r){
    std::reverse(r.begin(),r.end());
    return r;
};
static const auto print=[](const auto& r){
    std::copy(r.cbegin(),r.cend(),std::experimental::make_ostream_joiner(std::cout," "));
    return r;
};
template<class Range,class Functor>
auto operator|(Range& r,const Functor& func)
{
    return func(r);
}
int main()
{
    std::vector<int> v{1,2,3,4,5};
    v | reverse | print;
}

reverseとprintでそれぞれ範囲を横断していますので二度の横断処理がされる事になります。この場合では、単純に後方から参照さえしてくれれば期待した動作になります。そこでiteratorアダプタであるreverse_iteratorを用いてreverse rangeアダプタを作成します。*12

template<class Iterator>
struct range_iterator{
    using iterator=Iterator;
    using const_iterator=iterator;
    using value_type=typename std::iterator_traits<iterator>::value_type;
    using pointer=typename std::iterator_traits<iterator>::pointer;
    using reference=typename std::iterator_traits<iterator>::reference;
    using difference_type=typename std::iterator_traits<iterator>::difference_type;

    explicit range_iterator(iterator first,iterator last):first_(first),last_(last){}
    iterator begin()const{return first_;}
    iterator end()const{return last_;}
    const_iterator cbegin()const{return first_;}
    const_iterator cend()const{return last_;}
private:
    iterator first_;
    iterator last_;
};

template<class Iterator>
range_iterator<Iterator> make_range_iterator(Iterator first,Iterator last)
{
    return range_iterator<Iterator>(first,last);
}

template<class>
struct argument_of;
template<class R,class Arg>
struct argument_of<R(Arg)>{
    using type=Arg;
};
template<class Tp>
using copy_argument_t=std::remove_reference_t<std::remove_cv_t<typename argument_of<Tp>::type>>;

template<class R>
struct reversed_range{
    using type=range_iterator<std::reverse_iterator<typename R::iterator>>;
};

const struct reversed_t{
    template<class Signature>
    struct result:public reversed_range<copy_argument_t<Signature>>{};
    template<class Range>
    typename reversed_range<Range>::type operator()(const Range& r)const
    {
        return make_range_iterator(std::make_reverse_iterator(r.cend()),std::make_reverse_iterator(r.cbegin()));
    }
}reverse={};

reverse rangeアダプタを用いる事で

v | reverse | print;

としても一回一回reverse処理をするのではなく、実際のイテレータ操作時で純粋に後方から参照していきますので、無駄なループ処理を削減する事ができます。
まあ、これもまた現代ではラムダによって以下のように記述できます。

template<class Iterator>
struct range_iterator{
    // …
};

template<class Iterator>
range_iterator<Iterator> make_range_iterator(Iterator first,Iterator last)
{
    return range_iterator<Iterator>(first,last);
}

static const auto reverse=[](const auto& r){
    return make_range_iterator(std::make_reverse_iterator(r.cend()),std::make_reverse_iterator(r.cbegin()));
};

便利な時代になったものですね。このように、要求されるアルゴリズムに対応したrangeアダプタやイテレータをそれぞれ作る事で効率的な処理と記述が可能になります。以下のコードでは例としてコピーとフィルターを実装しています。

template<class Range,class Functor>
auto operator|(const Range& r,const Functor& f)
{
    return f(r);
}

template<class Iterator>
struct range_iterator final{
    using iterator=Iterator;
    using const_iterator=iterator;
    using value_type=typename std::iterator_traits<Iterator>::value_type;
    using difference_type=typename std::iterator_traits<Iterator>::difference_type;
    using reference=typename std::iterator_traits<Iterator>::reference;
    using pointer=typename std::iterator_traits<Iterator>::pointer;

    explicit range_iterator(Iterator first,Iterator last)noexcept:first_(first),last_(last){}
    iterator begin()const{return first_;}
    iterator end()const{return last_;}
    const_iterator cbegin()const{return first_;}
    const_iterator cend()const{return last_;}
private:
    Iterator first_,last_;
};
template<class Iterator>
range_iterator<Iterator> make_range_iterator(Iterator first,Iterator last){return range_iterator<Iterator>(first,last);}

template<class Iterator>
struct range_copyer{
    using value_type=typename std::iterator_traits<Iterator>::value_type;

    explicit range_copyer(Iterator first,Iterator last)noexcept:first_(first),last_(last){}
    Iterator begin()const{return first_;}
    Iterator end()const{return last_;}
    Iterator cbegin()const{return first_;}
    Iterator cend()const{return last_;}
    template<class ResultType>
    operator ResultType(){return ResultType(first_,last_);}
private:
    Iterator first_,last_;
};
template<class Iterator>
range_copyer<Iterator> make_range_copyer(Iterator first,Iterator last)
{
    return range_copyer<Iterator>(first,last);
}

template<class Predicate,class Iterator>
struct filterd_iterator{
    using iterator_category=std::forward_iterator_tag;
    using iterator=Iterator;
    using const_iterator=Iterator;
    using value_type=typename std::iterator_traits<Iterator>::value_type;
    using difference_type=typename std::iterator_traits<Iterator>::difference_type;
    using reference=typename std::iterator_traits<Iterator>::reference;
    using pointer=typename std::iterator_traits<Iterator>::pointer;

    explicit filterd_iterator(const Predicate& predicate,Iterator first,Iterator last)noexcept:pred(predicate),first_(first),last_(last){skip();}
    filterd_iterator& operator++()
    {
        ++first_;
        skip();
        return *this;
    }
    filterd_iterator& operator++(int)
    {
        filterd_iterator tmp=*this;
        ++first_;
        skip();
        return tmp;
    }
    value_type operator*()const{return *first_;}
    bool operator==(const filterd_iterator& rhs)const{return first_==rhs.first_;}
    bool operator!=(const filterd_iterator& rhs)const{return !operator==(rhs);}
private:
    void skip(){while(first_!=last_ && !pred(*first_))++first_;}
    Predicate pred;
    iterator first_,last_;
};
template<class Predicate,class Iterator>
filterd_iterator<Predicate,Iterator> make_filterd_iterator(const Predicate& pred,Iterator first,Iterator last){return filterd_iterator<Predicate,Iterator>(pred,first,last);}
template<class Predicate>
struct range_filter{
    explicit range_filter(const Predicate& predicate)noexcept:pred(predicate){}
    template<class Range>
    auto operator()(const Range& r)const{return make_range_iterator(make_filterd_iterator(pred,r.cbegin(),r.cend()),make_filterd_iterator(pred,r.cend(),r.cend()));}
private:
    Predicate pred;
};
template<class Predicate>
range_filter<Predicate> filterd(const Predicate& pred){return range_filter<Predicate>(pred);}

namespace{
const auto reverse=[](const auto& r){return make_range_iterator(std::make_reverse_iterator(r.cend()),std::make_reverse_iterator(r.cbegin()));};
const auto print=[](const auto& r){
    std::copy(r.cbegin(),r.cend(),std::ostream_iterator<typename std::remove_reference_t<decltype(r)>::value_type>(std::cout," "));
    std::cout<<std::endl;
    return make_range_iterator(r.cbegin(),r.cend());
};
const auto copied=[](const auto& r){return make_range_copyer(r.cbegin(),r.cend());};
}

int main()
{
    std::vector<int> v(10);
    boost::iota(v,1);

    std::vector<int> result = v | reverse | filterd([](const typename decltype(v)::value_type& x){return x%2==0;}) | print | copied; // 10 8 6 4 2
    result | print; // 10 8 6 4 2
}

コピーはoperator type()を使ってそのままイテレータの範囲から任意の戻り値のコンテナをインスタンス化して返しています。また述語などを受け取る機能を実装する際は補助的な関数テンプレートを実装する事でテンプレート引数を指定する必要がなくなります*13。このような実装はboost.rangeなどが代表的です。

...取り敢えずここまで

無駄に長くなるとアレなので、ここら辺で終わりにしたいと思います。また記事内で気になる点や間違いなどございましたらご教授くださると有難いです。ここまでお付き合い頂きありがとうございました。

C++ Advent Calender 2016、11日目の@mate_gaiさんに続きます。

※追記

2016 12/30:そういえばあんまりリアクション貰えなかったなぁ...と思いツイッターエゴサーチしてみたところ、リアクションを頂けていた事に今頃気づいた。

という事で修正しました。ご指摘ありがとうございます。
しかし、以前自分でこのような識別子は名付けてはならないというように書いたのに( The-polite-way-learn-to-C-/21-変数とデータ型.md at master · falgon/The-polite-way-learn-to-C- · GitHub)自分で忘れるとは...

参照

*1:Private Implementationの略とされる場合もある

*2:Barton-Nackman trick

*3:N3830からN3949でscoped_resourceからunique_resource_tへ改名、N3949からN4189でunique_resourceに改名された。一番古いものはN3677。またこの提案における執筆時での最新の文書はP0052R2。

*4:The Standard Template Library provides RAII classes for managing pointer types, such as std::unique_ptr and std::shared_ptr. This proposal seeks to add a new generic RAII class which ties zero or more resources to a clean-up/completion routine which is bound by scope, ensuring execution at scope exit (as the object is destroyed) unless released or executed early or returned by moving its value. - N3830

*5:詳しくはジェネリックなRAIIラッパーunique_resource - Rokiのチラ裏を参照

*6:コードを簡易にするためspecialize member functionなどを含み定義していない。オーバーロードを考慮するとsizeof…でVariadic templateの数とNを照合したり、丸め演算もあるのでパラメータパック1つ1つをチェックするなどでSFINAEさせた方が良いとも考えられるが、こちらも同じくコードを簡潔にするためそのような記述は省いている。

*7:コンストラクタのオーバーロードを考慮してenable_ifのイディオムを厳密に考えるとenable_if_t<Condition,nullptr_t> =nullptrの形が好ましいがコード簡潔化のためと、そもそもこのコードではオーバーロードをしていないためそのような記述はしていない。しかしenable_ifで自分自身を弾かなければ面倒な事となるので最低限の条件を記述している。

*8:this_のこと

*9:C++1z(17)ではstd::anyとして標準化される予定

*10:Boostではutilityヘッダーに。

*11:グローバル名前空間の問題やそれに対するADLの利用、ADL Firewallなどは内容としてイディオムの範囲外であるので触れていない

*12:rbegin、rendを呼び出せば良いのですが、それでは話が終わってしまうため今回は使わない。

*13:C++1z(17)ではTemplate parameter deduction for constructorsが使えるようになるため補助的な関数テンプレートを実装する必要はない