Boost学習のアルゴリズム編gather

gather
        ヘッダファイル'boost/algorithm/gather.hpp'には、アルゴリズムgatherの2つの変形関数があります.gather()は、一対の反復器で定義された要素の集合を持ち、中の要素をシーケンス内の適切な位置(ピボット位置)に移動して伝達された述語を満たす.アルゴリズム移動要素は安定である.アルゴリズムによって要素を移動すると、一対の反復器が返され、反復器が指定した範囲の要素が述語の順序を満たす.
テキストリンク:http://www.boost.org/doc/libs/1_60_0/libs/algorithm/doc/html/the_boost_algorithm_library/Misc/gather.html
API         関数gatherは、述語を満たすすべての要素を表す一対の反復器を返します.2つのバージョンのgather変異体があります.1つのバージョンには1対の反復器があり、別のバージョンにはパラメータ範囲があります.

namespace boost { namespace algorithm {
template <typename BidirectionalIterator, typename Pred>
std::pair<BidirectionalIterator,BidirectionalIterator>
gather ( BidirectionalIterator first, BidirectionalIterator last, BidirectionalIterator pivot, Pred pred );

template <typename BidirectionalRange, typename Pred>
std::pair<typename boost::range_iterator<const BidirectionalRange>::type, typename boost::range_iterator<const BidirectionalRange>::type>
gather ( const BidirectionalRange &range, typename boost::range_iterator<const BidirectionalRange>::type pivot, Pred pred );

}}

たとえば
        次のパラメータシーケンスarr{0 1 2 3 4 5 6 7 9}があり、gather(arr,arr+10,arr+4,IsEven)を呼び出すと次の結果が返されます.
1 3 0 2 4 6 8 5 7 9
    |---|-----|
  first |  second
      pivot
        上記の表現ではfirst secondは返される反復器である.
apiによれば、伝達されるパラメータはarrのシーケンス全体であり、ピボット量は4であるため、4未満は4の前に直接配置され、4より大きいものは後ろに配置される.また前述したように、gatherはアルゴリズムが安定しているため、0は2の前にあるか8は6の後ろにあるか.アルゴリズムの安定性については、いくつかのソートクラスのアルゴリズムの説明を表示できます.
反復器の要件
        gatherは双方向反復器に作用する.これはgatherがstableを使用したことに由来します.partition関数で、双方向反復器が必要です.libstdc+、libc++などの標準ライブラリがstable_を拡張しています.partitionは、これらのライブラリの関数を使用してプリアンブルを使用できるようにします.この場合、gatherは前置反復器にも作用する.
堅牢性の要件
       gatherはstable_を使用していますpartitionでは、短いメモリを開発しようとしますが、メモリが使用できない場合は追加のメモリを開発しません(既存のメモリで関数を実行します).
時間の複雑さ
        十分なメモリがある場合、実行時間はO(N)である.
        使用可能なメモリがない場合は、実行時間はO(N log N)です.