C++: Найти любой элемент из контейнера1 не в контейнере2

Question

У меня есть std::set<int> (s) и std::vector<int> (v). Вектор гарантированно сортируется/уникален. Я хочу знать, все ли элементы v находятся в s (или просто останавливаются в первом элементе v не в s). Я мог бы преобразовать v в набор и выполнить == test, но есть ли другой способ без изменения типа контейнера?

Answer 1

Что насчет std::includes алгоритма?

Вот короткий пример использования:

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; 

Выход:

1 
0 

Answer 2

Я думаю, что вы ищете std::set::count или 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 
    } 
} 

Если вам нужны все элементы V не с, просто использовать std::set_difference

Answer 3

std::set<int> будет заказан. Если гарантируется, что std::vector<int> будет заказано и содержит уникальные значения, вы можете перебирать их по обоим и сравнивать значения элементов.

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; 

Answer 4

О (п) раствор:

#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; 
    } 
}