C++ : container2에없는 container1의 요소를 찾으십시오.

Question

저는 std::set<int> (s)이고 std::vector<int> (v)입니다. 벡터는 정렬 된/고유 한 것이 보장됩니다. 나는 v의 모든 요소가 s에 있는지 (또는 s의 v가 아닌 v의 첫 번째 요소에서 멈추는 지) 알고 싶다. v를 집합으로 변환하고 == test를 할 수 있지만 컨테이너 유형을 변경하지 않고 다른 방법이 있습니까? 당신이 V의 모든 요소가 필요한 경우

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

는하지의에서, 단지 std::set_difference

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를 찾고 있습니다 생각합니다. 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 3

std::set<int>는 명령을 받게됩니다 사용

Answer 4

O (N) 용액 :

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