2016-06-01 11 views
9

Ich habe eine std::set<int> (s) und eine std::vector<int> (v). Der Vektor ist garantiert sortiert/eindeutig. Ich möchte wissen, ob alle Elemente von v in s sind (oder halt einfach beim ersten Element von v nicht in s). Ich könnte v in ein Set konvertieren und == testen, aber gibt es einen anderen Weg, ohne den Containertyp zu ändern?C++: Finden Sie ein beliebiges Element aus Container1 nicht in Container2

+0

Eine Schleife, 'std :: find_if()' und ein Lambda? –

+5

Wie wäre es mit 'std :: Mismatch'? –

+0

'std :: set_difference'? –

Antwort

9

Was ist los std::includes Algorithmus?

Hier ein kurzes Verwendungsbeispiel:

vector<int> v1 { 1, 2, 4, 8 }; 
vector<int> v2 { 1, 2, 3, 8 }; 
set<int> s { 0, 1, 2, 4, 8, 16 }; 
cout << includes(s.begin(), s.end(), v1.begin(), v1.end()) << endl; 
cout << includes(s.begin(), s.end(), v2.begin(), v2.end()) << endl; 

Ausgang:

1 
0 
2

Ich glaube, Sie suchen std::set::count oder std::unordered_set::count:

if(v.size() > s.size()) 
{ 
    // since v has unique values 
    // v is not subset of s 
    // if you need to find a first element of v not in s 
    // you need to run the loop below anyway 
} 
for(auto i : v) 
{ 
    if(!s.count(i)) 
    { 
     // i not in s 
    } 
} 

Wenn Sie alle Elemente von v nicht in s benötigen, verwenden Sie nur std::set_difference

+0

Das ist O (n log m), aber die anderen vorgeschlagenen Optionen sind O (n + m), was besser ist. –

+0

Können wir annehmen, dass s std :: unordered_set ist? Dann ist es O (n) – lllllllllll

+0

True, obwohl OP angegeben 'set'. –

1

Die std::set<int> wird bestellt. Wenn die std::vector<int> garantiert sortiert ist und eindeutige Werte enthält, können Sie beide über iterieren und die Werte der Elemente vergleichen.

std::set<int> s = {...}; 
std::vector<int> v = {...}; 

// Default answer. If v.size() > s.size(), the answer is 
// definitely false. Otherwise, assume the answer to be true. 
bool ans = (v.size() <= s.size()); 

auto si = s.begin(); 
auto vi = v.begin(); 

// We need to check for si != s.end() 
for (; ans == true && vi != v.end() && si != s.end(); ++si) 
{ 
    if (*si == *vi) ++vi; 
    else if (*si > *vi) ans = false; 
} 
if (vi != v.end()) ans = false; 
// ... 
return ans; 
0

O (n) Lösung:

#include <iostream> 
#include <set> 
#include <vector> 

bool incCase(std::set<int> &s, std::vector<int> &v) 
{ 
    if(v.size() > s.size()) 
     return false; 

    auto si = s.begin(); 

    for(int& vv : v) 
    { 
     for(;;si++) 
     { 
      if(si==s.end() || *si>vv) 
       return false; 
      if(*si==vv) 
      { 
       si++; 
       break; 
      } 
     } 
    } 

    return true; 
} 

int main() 
{ 
    std::set<int> s { 0, 1, 2, 4, 8, 16 }; 
    std::vector< std::vector<int> > vv { 
     { 0, 1, 2, 4, 8, 16 }, 
     { 0, 2 }, 
     { 4, 16 }, 
     { 2, 8, }, 
     { 4}, 
     { 1, 4, 16 }, 
     { 0, 2, 8}, 
     { }, 
     { -1, 1, 2, 4, 8, 16 }, 
     { 0, 1, 2, 4, 8, 32 }, 
     { 0, 2, 3 }, 
     { 4, 5, 16 }, 
     { 3, 8, }, 
     { 5}, 
     { 1, 5, 16 }, 
     { 0, 3, 8}, 
    }; 

    int i = 1; 
    for(auto &v : vv) 
    { 
     std::cout<< i++ << (incCase(s,v)?" = True":" = False") << std::endl; 
    } 
}