在std::set中查找std::vector的元素

Question

在std::set中查找std::vector的元素

3

我有两个容器，一个是std::set，另一个是std::vector。我的任务是从std::vector返回存在于std::set中的元素。最有效的方法是什么？简单的解决方案：遍历向量的元素, 对每个元素调用set.find，然后如果未找到，就调用vector.erase函数去除。

- rublow

3

这个向量是有序的还是无序的？ - NathanOliver

1

听起来你可能想要类似 std::set_union 的东西（但需要对向量进行排序）。 - Some programmer dude

抱歉不一致。目前（可能仍然如此），向量未排序且较小。但是，集合具有更多元素。 - rublow

5个回答

0

最短的方法可能是使用std::set_intersection。但是您应该对向量进行排序才能使其正常工作：

int main()
{
    std::set<int>    s{1,2,3,4,5,6,7,8};
    std::vector<int> v{7,5,10,9};
    std::sort(v.begin(), v.end()); // should not bother you if vector is small

    std::vector<int> intersection;
    std::set_intersection(s.begin(), s.end(), v.begin(), v.end(), std::back_inserter(intersection));

    for(int n : intersection)
        std::cout << n << ' ';
}

输出：5 7

- Nikolai Shalakin

1

如果n是向量的大小，m是集合的大小，则时间复杂度为O(n*lg(n) + n + m)。可以用O(n*lg(m))的时间复杂度完成。（而且集合迭代很慢。） - molbdnilo

0

根据集合和向量的相对大小，remove_if可能是正确的选择...

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

int main()
{
    std::set<int>    s{1,2,3,4,5,6,7,8};
    std::vector<int> v{7,5,10,9};

    v.erase(std::remove_if(v.begin(), v.end(), [&](int e){return s.count(e) == 0;}), v.end());


    for(int n : v)
        std::cout << n << ' ';
}

- user3458

0

你可以使用更多的STL :)

#include <algorithm>
#include <set>
#include <vector>
#include <iostream>
#include <iterator>

int main() {
    std::vector<int> v {5, 4, 3, 2, 1};
    std::set<int> s {1, 3, 5};

    v.erase(std::remove_if(v.begin(), v.end(), 
                          [&s](int a) { return s.find(a) == s.end(); }),
            v.end());

    std::copy(v.begin(), v.end(), std::ostream_iterator<int>(std::cout, " "));
}

- tmp

由于我想保留在集合中存在的向量元素，因此解决方案需要进行小修正 return s.find(a) == s.end(); - rublow

0

如果你想要在复杂度方面寻找最有效的方式，并且有额外的内存和良好的哈希函数，那么可以使用O(n + m)的方法来完成此操作。

std::vector<int> v;
std::set<int> s;
std::unordered_set<int> us{s.cbegin(), s.cend(), s.size()};

v.erase(
    std::remove_if(v.begin(), v.end(),
        [&us] (const int entry) { return us.find(entry) == us.cend(); }),
    v.end());

解释：您首先迭代一次您的set（O(m)），以准备unordered_set。然后您遍历一次您的vector（O(n)），每步执行unordered_set::find（0(1)）。这给出了O(n+m)的结果复杂度。

此外，unordered_set的大小等于set的大小，并且良好的哈希函数有助于减少std::unordered_set::find的复杂度中的常数部分。

请参见实时示例。

但是，请记住，更低的复杂度并不一定意味着在特定情况下执行更快（例如，因为存在额外的分配）。

- Dev Null

谢谢您的解释。然而（正如您所提到的），我想在不使用额外内存的情况下 "动态" 擦除元素。 - rublow

在这种情况下，如果您不关心set的排序属性，可以将其替换为unordered_set，或者使用[boost :: multi_index_container]（http://www.boost.org/doc/libs/1_64_0/libs/multi_index/doc/tutorial/index.html）与`ordered_unique`索引类型一起使用，以利用类似于`set`的属性，并使用`hashed_unique`过滤掉不需要的条目，复杂度为O（n）。 - Dev Null

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- The Quantum Physicist · Accepted Answer

如果您的向量未排序，则只需查找每个元素如何？那么就可以避免 n log(n) 的时间复杂度。

#include <algorithm>

std::vector<int> result;
for(auto&& el: myvector) {
    auto it_found = myset.find(el);
    if(it != myset.end())
        result.push_back(*it_found);
}

现在result包含了两个数组中共同存在的元素。

PS：代码未编译，可能存在轻微错误。