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
Antwort
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
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
Das ist O (n log m), aber die anderen vorgeschlagenen Optionen sind O (n + m), was besser ist. –
Können wir annehmen, dass s std :: unordered_set ist? Dann ist es O (n) – lllllllllll
True, obwohl OP angegeben 'set'. –
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;
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;
}
}
Eine Schleife, 'std :: find_if()' und ein Lambda? –
Wie wäre es mit 'std :: Mismatch'? –
'std :: set_difference'? –