C++：从 container1 中查找不在 container2 中的任何元素

Question

我有一个 std::set<int> (s) 和一个 std::vector<int> (v)。向量保证为sorted/unique。我想知道 v 的所有元素是否都在 s 中（或者只是停在 v 的第一个元素而不是 s 中）。我可以将 v 转换成一个集合并做 == 测试，但是有没有不改变容器类型的另一种方法？

Answer 1

我认为您正在寻找 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 中不在 s 中的所有元素，只需使用 std::set_difference

Answer 2

将订购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 3

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

C++：从 container1 中查找不在 container2 中的任何元素

C++: Find any element from container1 not in container2

c++

algorithm

stl

std