Rokiのチラ裏

学生による学習のログ

iterator requirementsにassignableを要求される事による問題

C++

※追記
当エントリは「STLコンテナの気まぐれな実装によってiteratorをassignされる事による問題」というタイトルであったが、これは気まぐれな実装ではなく、標準の文面に規定されたルールの範囲内での話であったため、誤った解釈に基づくようなタイトルや文面が編集されている。

標準が定めるイテレータの要件としてcopy assignableである事が明記されている。 *1

A type X satisfies the Iterator requirements if: X satisfies the CopyConstructible, CopyAssignable, and Destructible requirements (17.5.3.1) and lvalues of type X are swappable (17.5.3.2), and ...

STLコンテナには、アルゴリズムらの計算量を除いた実装規定というものが特にない。よって、本エントリの題名のように気まぐれにiteratorをassignしたところで何の違反性もないのだが、これについては規定した方が良いんじゃないかという意見。上記の通りcopy assignableでなければならないと定められている。

例えば、大抵のSTLコンテナはbegin/endのイテレータで初期化する事が可能である。

std::vector<int> v1(10,42);
std::vector<int> v2(v1.begin(),v1.end());

そして、かの有名なライブラリ、Boost C++ Librariesにはboost range adaptorsというイテレータアダプタを利用した効率的な範囲横断を促す事のできるライブラリが存在する。中でも、例えばboost::adaptors::filteredはクロージャを渡す事によってその条件に応じた範囲横断を行えるイテレータアダプタである。

std::vector<int> v(10);
boost::iota(v,0);
    
boost::range::copy(v | boost::adaptors::filtered([](const typename decltype(v)::value_type& x){return x%2==0;}),std::ostream_iterator<int>(std::cout," "));

では、このfilteredイテレータアダプタを用いて、範囲を初期化する。イテレータアダプタから直接初期化するためにはOvenToBoostなどのas_containerが、Boostと互換性があり良い。

std::vector<int> v1(10);
boost::iota(v1,0);
    
std::vector<int> v2 = v1 | boost::adaptors::filtered([](const typename decltype(v1)::value_type& x){return x%2==0;}) | boost::as_container; // v2は偶数のみで初期化される。

このコードは、GCC、Clangともに正しくコンパイルに成功する。ここで例えば、コンテナをstd::dequeにするとどうなるだろうか。

std::deque<int> v1(10);
boost::iota(v1,0);
    
std::deque<int> v2 = v1 | boost::adaptors::filtered([](const typename decltype(v1)::value_type& x){return x%2==0;}) | boost::as_container;

clang(3.5〜5.0.0)のライブラリ実装上では正しくコンパイルに成功する。しかし、このコードはGCC(7.0.1までの全てのバージョン)でコンパイルに失敗する。エラー文は、この場合BoostをインクルードしているのでBoostライブラリでのassign失敗の旨が出力されるが、std::dequeの実装を実際に見て見ると、直接的にassign操作を行なっているコードが目につく(gcc7.0.1であれば、/c++/7.0.1/bits/deque.tcc:458:11)。これは、predに、ラムダ式が使えない事を意味する。boost::adaptors::filteredはfiltered_iteratorというイテレータアダプタを生成しその内部に指定されたクロージャオブジェクトを保持する。ラムダ式のoperator=は規格によってdelete指定されているため、イテレータをassignした段階で失敗する。

ラムダ式でないクロージャであればコンパイルに成功するが、ベンダによって異なる内部実装を気にしてpredをラムダ式で書かないというプログラマ側の負担は無駄であるように思う。

struct functor{
    template<class T>
    bool operator()(const T& t){return t%2==0;}
};

std::deque<int> v1(10);
boost::iota(v1,0);
std::deque<int> v2 = v1 | boost::adaptors::filtered(functor()) | boost::as_container; // v2は偶数のみで初期化される。

GCCの実装では、何故イテレータをassignする必要があったのか、そこまではコードを追っていないので分からないが、このような仕様は少なくともイテレータアダプタによる初期化を妨げる要因となる。よってSTLコンテナのbegin/endコンストラクタはassignableを強要すべきではないと私は考える。

一つ、妥協策ではあるが、解決策はある。内包するpredをラッパーで包み、無理やりassignableに見せかける事でコンパイルに成功する。

自作ライブラリ、srook range adaptor filterd_iteratorなどでは内部に当ラッパーを用いたクロージャを保持しており、gccで無事コンパイルを通している。

#include<srook/range/adaptor/copied.hpp>
#include<srook/range/adaptor/filterd.hpp>
#include<srook/range/adaptor/print.hpp>
#include<deque>
#include<boost/range/irange.hpp>

struct functor{
    template<class T>
    bool operator()(const T& t){return t%2==0;}
};

int main()
{
    std::deque<int> deq1 = boost::irange(1,9) | srook::adaptors::copied;
    std::deque<int> deq2 = deq1 | srook::adaptors::filterd([](const typename decltype(deq2)::value_type& x){return x%2==0;}) | srook::adaptors::copied;
    std::deque<int> deq3 = deq1 | srook::adaptors::filterd(functor()) | srook::adaptors::copied;
    deq2 | srook::adaptors::print();
    deq3 | srook::adaptors::print();
}

しかし、依然としてラッパーを噛ませている分オーバーヘッドが発生するので、あまり心地よくはない。

*1:N4618 24.2.2 Iteratorから引用