8

aとを整数bにしa < bます。std::set<int> S効率的で洗練された (できれば明示的なループを使用しない) 方法を考えると、にないvectorすべての数値を検索して ( に)格納します。[a, b]S

解決策 1:

 vector<int> v;
 for(int i = a; i <= b; ++i)
 {
     if(S.find(i) == S.end())
     {
        v.push_back(i);
     }         
}

解決策 2:

から までのすべての数字を aaに押し込んで使用しますbsetstd::set_difference

Solution1 には明示的なループが含まれており、Solution2 はあまり効率的ではないようです (少なくともメモリに関して)。何を提案しますか？これを行うためのエレガントなSTLっぽい（ブーストも受け入れられる）慣用的な方法を探しています。

4

4 に答える 4

8

ソリューション＃2のようなことができます。ただし、 range を含む実際のコンテナーを作成する代わりに、数値範囲の仮想コンテナーである を[a,b]使用します。boost::irangeこの方法では、明示的なループがなく、線形時間で実行され、メモリをあまり消費しません。

さらに高速にするには、lower_bound/を使用して、セットの関連部分のみをカバーしupper_boundます。

auto abRange = boost::irange(a,b+1);
std::set_difference(abRange.begin(), abRange.end(), 
                    s.lower_bound(a), s.upper_bound(b), 
                    std::back_inserter(resultVector));

またはを使用してBoost.Range：set_difference

boost::set_difference(boost::irange(a,b+1),
                      std::make_pair(s.lower_bound(a), s.upper_bound(b)),
                      std::back_inserter(resultVector));
于 2012-05-17T12:45:57.403 に答える
2

の「セット」set_intersectionは意味ではなくstd::set、単に論理セットを意味します。もののグループ。両方のコレクションが並べ替えられている場合は、単純set_intersectionに 2 つを 3 番目のコンテナーに入れることができます。

vector<int> common;
set_intersection(v.begin(), v.end(), s.begin(), s.end(), back_inserter(common));

編集：

上記を説明する完全な例を次に示します。これは C++11 ラムダを使用しますが、C++11 がない場合、またはラムダを使用できない場合は、代わりにファンクタを使用できます。明示的なループがないことに注意してください。

#include <set>
#include <vector>
#include <algorithm>
#include <iterator>
#include <functional>
#include <iostream>
using namespace std;

static const int numbers[] = {0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181};
static const size_t num_numbers = sizeof(numbers)/sizeof(numbers[0]);

int main()
{
    /*** GET THE SET ****/
    set<int> s(begin(numbers), end(numbers));
    //copy(&numbers[0], &numbers[num_numbers], inserter(s, s.begin()));

    /*** GET THE NUMBERS TO LOOK FOR **/
    int first = 5, last = 10;
    vector<int> targets;
    generate_n(back_inserter(targets), last-first, [&first]() -> int {
        return first++;
    });

    /*** FIND THE INTERSECTION ***/
    vector<int> common;
    set_intersection(s.begin(), s.end(), targets.begin(), targets.end(), back_inserter(common));

    /*** DUMP RESULTS ***/
    cout << "Intersecton of:\n\t";
    copy(s.begin(), s.end(), ostream_iterator<int>(cout,"\t"));
    cout << "\nwith:\n\t";
    copy(targets.begin(), targets.end(), ostream_iterator<int>(cout,"\t"));
    cout << "\n= = = = = = = =\n\t";
    copy(common.begin(), common.end(), ostream_iterator<int>(cout,"\t"));
    cout << "\n";

}

出力は次のとおりです。

Intersecton of:
        0       1       2       3       5       8       13      21      34
55      89      144     233     377     610     987     1597    2584    4181

with:
        5       6       7       8       9
= = = = = = = =
        5       8
于 2012-05-17T12:42:38.353 に答える
2

以下はループを回避しますが、それがあなたが求めているものかどうかはわかりません:

void inSet(int i, int b, vector<int>& v, set<int>& S)
{
   if(S.find(i) == S.end())
        v.push_back(i);

   if(i<b)
        inSet(i+1,b,v,S);
}

// ... snip
vector<int> v;
inSet(a,b,v,S);

また、ソリューション 2 ですべての整数 [a,b] を std::set に入れるループはありませんか?

于 2012-05-17T12:43:30.940 に答える
1

から反復しS.lower_bound(a)てS.lower_bound(b)、見つからないすべての整数を収集できます。

auto end = S.lower_bound(b);
int seen = a;

for (auto it = S.lower_bound(a); it < end; ++it) {
   for (int i = seen+1; i < *it; ++i)
      v.push_back(i);
   seen = *it;
}

明示的なループが含まれていますが、どういうわけか のすべての整数を調べる必要があります[a,b]。

于 2012-05-17T12:41:08.263 に答える