श्रेणी में सभी संख्याएं खोजें [ए, बी] जो दिए गए std :: set S

Question

में नहीं हैं a और b पूर्णांक, a < b बनें। std::set<int> S को देखते हुए में [a, b] से सभी संख्याओं को खोजने और स्टोर करने के लिए एक कुशल और सुरुचिपूर्ण (अधिमानतः स्पष्ट लूप के बिना) तरीका है (vector में)।

समाधान 1:

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

समाधान 2:

पुश सभी a से b करने के लिए एक set में संख्या और उपयोग करने std::set_difference

solution1, एक स्पष्ट पाश होता है और समाधान 2 बहुत कुशल प्रतीत नहीं होता है (कम से कम स्मृति के मामले में)। आप क्या सुझाव देंगे? मैं ऐसा करने के लिए एक सुंदर एसटीएल-आश (बूस्ट भी स्वीकार्य है) की तलाश में हूं।

Answer 1

आप अपने समाधान # 2 जैसे कुछ कर सकते हैं। लेकिन [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)); 

Answer 2

आप 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] में सभी पूर्णांकों को देखने के लिए होगा ।

Answer 3

set_intersection में "सेट" का मतलब std::set नहीं है - इसका मतलब केवल तार्किक सेट है; चीजों का एक समूह। यदि दोनों संग्रहों को क्रमबद्ध किया गया है, तो आप केवल set_intersection दोनों को तीसरे कंटेनर में कर सकते हैं।

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

संपादित करें:

यहां एक संपूर्ण उदाहरण है कि इसके बाद के संस्करण को दिखाता है। यह सी ++ 11 लैम्ब्डा का उपयोग करता है, लेकिन यदि आपके पास सी ++ 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 

Answer 4

खैर निम्नलिखित एक पाश से बचा जाता है, लेकिन मुझे यकीन है कि यह आप क्या कर रहे हैं के बाद है नहीं कर रहा हूँ:

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 में सभी integers [ए, बी] एक std :: सेट में डाल?