特定の間隔内にある値のソートされたリストのサブリストを取得する最短方法

Question

今日、a以上のソートされたベクトルstd::vector<double>のすべての値を取得するための最短のコードと、 b以下。

std::vector<double> cutValues2(const std::vector<double>& sortedValues, double start, double end) { 
    std::vector<double> ret; 
    std::copy_if(sortedValues.begin(), sortedValues.end(), std::back_inserter(ret), [&start, &end](auto v) { return v >= start && v <= end; }); 
    return ret; 
} 

しかし、唯一の非常に小さな部分を除去する場合を考える：私の第二の考えは以下のように非常にシンプルなものだった

#include <vector> 
#include <algorithm> 
#include <iterator> 
#include <iostream> 

// Returns all values in sortedValues being greater equal start and smaller equal end; 
std::vector<double> cutValues(const std::vector<double>& sortedValues, double start, double end) { 
    std::vector<double> ret; 

    auto startIter=std::lower_bound(sortedValues.begin(), sortedValues.end(), start); 
    auto stopIter = std::upper_bound(sortedValues.begin(), sortedValues.end(), end); 
    std::copy(startIter, stopIter, std::back_inserter(ret)); 
    return ret; 
} 

int main(int argc, char **args) { 
    { 
     auto ret = cutValues({ 0.1,0.2,0.3 }, 0.1, 0.3); 
     std::copy(ret.begin(), ret.end(), std::ostream_iterator<double>(std::cout, ",")); 
     std::cout << std::endl; 
    } 
    { 
     auto ret = cutValues({ 0.12,0.2,0.31 }, 0.1, 0.3); 
     std::copy(ret.begin(), ret.end(), std::ostream_iterator<double>(std::cout, ",")); 
     std::cout << std::endl; 
    } 
    { 
     auto ret = cutValues({ 0.1,0.2,0.3 }, 0.2, 0.2); 
     std::copy(ret.begin(), ret.end(), std::ostream_iterator<double>(std::cout, ",")); 
     std::cout << std::endl; 
    } 
} 

：

私の最初のアプローチは、次のようなものでした大規模なベクトルそれはいくつかの効率の問題があるかもしれません。

今、もっと良い方法があるのか​​どうか、自分に尋ねています。

Answer 1

ビットは、最初のバージョンを変更：

std::vector<double> cutValues(const std::vector<double>& sortedValues, double start, double end) { 
    auto startIter = std::lower_bound(sortedValues.begin(), sortedValues.end(), start); 
    auto stopIter = std::upper_bound(startIter, sortedValues.end(), end); 
    return std::vector<double>(startIter, stopIter); 
} 

Answer 2

間隔がどこで開始されるか分かったら、穴のベクトルをもう一度見て、終了イテレータを見つける必要はありません。 start_iteratorの代わりに検索を開始

auto startIter = std::lower_bound(sortedValues.begin(), sortedValues.end(), start); 
if (startIter == sortedValues.end()) { 
    // either the last element was inside the interval (return it) or not (return empty vector) 
    return *(--startIter) == start ? {start} : {}; 
} 
auto stopIter = std::upper_bound(++startIter, sortedValues.end(), end); 
           // start from here 
std::copy(--startIter, stopIter, std::back_inserter(ret));  

その他の最適化はコンテンツによって異なります。例えば。あなたのインターバル内の最後の要素が、むしろベクトルの終わりにあることが分かっているなら、それを逆に反復する方が意味があります。

aがb以上であれば、不要な実行を防ぐために間隔を最初に確認することを検討することもできます。

Answer 3

短くないが、一般的に、より効率的な：「面白い」間隔の開始を見つけるためにstd::lower_boundを使用して、要素は以下である限りコピーに行きますあなたの最大値。あなたが素早く探し出している（O（log N））ビッグベクトルであっても開始し、バイナリ検索を行う時間を無駄にしないでください間隔の終わりを探しています - とにかくコピーループ。 doubleが自分自身を比較して

おそらく余分な比較は、とにかく事実上無料で非常に安価であり、枝はよく予測（それはコピーの終わりまでいつも同じだ）とキャッシュ内に既にデータに依存しています。メモリ内で「ジャンプ」する（キャッシュのローカリティが悪化する）余分なバイナリ検索と比較し、予測可能な分岐が少なくなっています。

std::vector<double> cutValues(const std::vector<double>& sortedValues, double minv, double maxv) { 
    std::vector<double> ret; 
    auto end = sortedValues.end(); 
    for(auto it = std::lower_bound(sortedValues.begin(), end, minv); 
     it != end && *it <= max; ++it) { 
     ret.push_back(*it); 
    } 
    return ret; 
} 

これはあなたのcutValues2使用してSTLアルゴリズムと同様に書き換えることができ、私はそれが改善のあまりだか分かりません。

std::vector<double> cutValues(const std::vector<double>& sortedValues, double minv, double maxv) { 
    std::vector<double> ret; 
    std::copy_if(
     std::lower_bound(sortedValues.begin(), sortedValues.end(), minv), 
     sortedValues.end(), 
     std::back_inserter(ret), 
     [=](double v) { return v <= maxv; }); 
    return ret; 
} 

Answer 4

あなたは、あなたの関数のSTLスタイルを書いて、それが（そしてそれは、よりエレガントな私見になります）任意の型のいずれかのコンテナで動作させることができます。

template <typename ForwardIt, typename T> 
auto bounded_range(ForwardIt first, ForwardIt last, T lb, T ub) { 
    return std::pair{std::lower_bound(first, last, lb), std::upper_bound(first, last, ub)}; 
} 

std::vector<double> v1{0.1, 0.1, 0.2, 0.3, 0.3, 0.5, 0.7, 0.9}; 

auto [beg, end] = bounded_range(std::begin(v), std::end(v), 0.3, 0.5); 
std::vector<double> v2{beg, end}; 

// Or using 'std::make_from_tuple'. 
auto v3 = std::make_from_tuple<std::vector<double>>(bounded_range(std::begin(v), std::end(v), 0.3, 0.5)); 

_{注：例としては、C++ 17 template argument deduction for class templates、及びstructured bindings使用します。}