给定一个 STL 容器,比如 std::map:
std::map<int, CustomClass> some_container;
std::vector<int> real_objects;
如何使用不在 real_objects vector 中的键正确有效地从 some_container 映射中删除每个元素? map 是此类任务的最佳容器吗?
最佳答案
我的第一直觉是批量删除大块的非真实对象:
// Assuming real_objets is sorted (otherwise sort it)
auto first = some_container.begin();
for(int i : real_objects) {
// end of the chunk to erase is the place where i could be
// inserted without breaking the order
auto last = some_container.lower_bound(i);
some_container.erase(first, last);
// if i is a key in the container, skip that element
if(last != some_container.end() && last->first == i) {
++last;
}
first = last;
}
// and in the end, kill stuff that comes after real_objects.back()
some_container.erase(first, some_container.end());
这具有运行时复杂度 O(n * log(m)),其中 n 是 real_objects.size()
,m 是 some_container.size()
,意思是它如果 some_container
比 real_objects
大得多,则性能最佳。否则,由于可以在线性时间内遍历 std::map
,因此您可以锁步遍历并按顺序移除差异:
// again, sort real_objects.
if(!some_container.empty()) { // else there's nothing to do
auto ir = real_objects.begin();
auto ire = std::lower_bound(real_objects.begin(),
real_objects.end (),
some_container.rbegin()->first);
auto is = some_container.begin();
for(;;) {
// find the next place where the real_objects and the keys of some_container don't match
auto p = std::mismatch(ir, ire, is, [](int i, std::pair<int, int> const &p) { return i == p.first; });
if(p.first == real_objects .end() ||
p.second == some_container.end())
{
// upon reaching the end, remove all that comes after the
// end of real_objects (if anything)
some_container.erase(p.second, some_container.end());
break;
} else if(*p.first < p.second->first) {
// if there's something in real_objects that's not in
// some_container, skip it
++p.first;
} else {
// otherwise there's something in some_container that's
// not in real_objects, so delete it.
p.second = some_container.erase(p.second);
}
ir = p.first;
is = p.second;
}
}
这具有运行时复杂度 O(max(n, m)),因此如果 some_container
和 real_objects
几乎匹配,它应该表现良好。
关于c++ - 使用不包含在另一个 vector 中的键从 map 中删除元素,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/27212621/