有两个未排序的int向量和对int的向量，int
std::vector <int> v1;
std::vector <std::pair<int, float> > v2;
包含数百万个项目。
如何尽快从v1中删除v2.first独有的项目（即不包括在v2.first中）？
示例：
v1: 5 3 2 4 7 8
v2: {2,8} {7,10} {5,0} {8,9}
----------------------------
v1: 3 4
我会用两个技巧来尽快做到这一点：
-
使用某种关联容器（可能是
std::unordered_set）来存储第二个向量中的所有整数，从而显著提高查找是否应该删除第一个向量中某个整数的效率。 -
优化从初始向量中删除元素的方式。
更具体地说，我会做以下事情。首先创建一个std::unordered_set，并将第二个向量中的第一个整数相加。这给了（预期的）O（1）查找时间来检查集合中是否存在特定的int。
既然已经完成了，那么就使用std::remove_if算法从哈希表中存在的原始vector中删除所有内容。您可以使用lambda来执行此操作：
std::unordered_set<int> toRemove = /* ... */
v1.erase(std::remove_if(v1.begin(), v1.end(), [&toRemove] (int x) -> bool {
return toRemove.find(x) != toRemove.end();
}, v1.end());
在unordered_set中存储所有内容的第一步需要预期的O（n）时间。第二步通过将所有删除集中到最后并使查找花费很小的时间来完成预期的O（n）工作。这就给出了整个过程的预期O（n）-时间，O（n）空间的总和。
如果允许您对第二个向量（对）进行排序，那么您也可以在O（n log n）最坏情况时间、O（log n）更坏情况空间中通过按关键字对向量进行排序来执行此操作，然后使用std::binary_search来检查是否应该消除第一个vector中的特定int。每个二进制搜索花费O（logn）时间，因此排序所需的总时间为O（n-logn），第一个向量中每个元素的O（logN）时间（总共O（n-log n）），删除所需的O（n）时间（总计O（n-对数n））。
希望这能有所帮助！
假设两个容器都没有排序，并且排序实际上过于昂贵或内存不足：
v1.erase(std::remove_if(v1.begin(), v1.end(),
[&v2](int i) {
return std::find_if(v2.begin(), v2.end(),
[](const std::pair<int, float>& p) {
return p.first == i; })
!= v2.end() }), v1.end());
或者，在first上对v2进行排序，并改用二进制搜索。如果有足够的内存，则使用unordered_set对v2的first进行排序。
完整的C++03版本：
#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
struct find_func {
find_func(int i) : i(i) {}
int i;
bool operator()(const std::pair<int, float>& p) {
return p.first == i;
}
};
struct remove_func {
remove_func(std::vector< std::pair<int, float> >* v2)
: v2(v2) {}
std::vector< std::pair<int, float> >* v2;
bool operator()(int i) {
return std::find_if(v2->begin(), v2->end(), find_func(i)) != v2->end();
}
};
int main()
{
// c++11 here
std::vector<int> v1 = {5, 3, 2, 4, 7, 8};
std::vector< std::pair<int, float> > v2 = {{2,8}, {7,10}, {5,0}, {8,9}};
v1.erase(std::remove_if(v1.begin(), v1.end(), remove_func(&v2)), v1.end());
// and here
for(auto x : v1) {
std::cout << x << std::endl;
}
return 0;
}