高效地从向量中删除元素的方法

Question

高效地从向量中删除元素的方法

6

目前，我计划从向量中删除所有在集合中找不到的项目。

例如：

#include <vector>
#include <set>
#include <string>
#include <iostream>

using namespace std;

int main() {
    std::set<string> erase_if_not_found;
    erase_if_not_found.insert("a");
    erase_if_not_found.insert("b");
    erase_if_not_found.insert("c");

    std::vector<string> orders;
    orders.push_back("a");
    orders.push_back("A");
    orders.push_back("A");
    orders.push_back("b");
    orders.push_back("c");
    orders.push_back("D");

    // Expect all "A" and "D" to be removed.
    for (std::vector<std::string>::iterator itr = orders.begin(); itr != orders.end();) {
        if (erase_if_not_found.find(*itr) == erase_if_not_found.end()) {
            orders.erase(itr);
            // Begin from start point again? Do we have a better way?
            itr = orders.begin();
        } else {
            ++itr;
        }
    }

    for (std::vector<std::string>::iterator itr = orders.begin(); itr != orders.end(); ++itr) {
        std::cout << *itr << std::endl;
    }

    getchar();
}

尽管上述代码可以工作，但并不高效，因为我每次删除一个项目时都是从向量的起始点开始的。

有更好的方法吗？

- Cheok Yan Cheng

除了“remove_if”代码之外，您始终可以使用整数索引向后迭代向量。您可以自由地删除一个元素，然后移动到前一个元素而不会出现问题。我经常这样做。 - edA-qa mort-ora-y

6个回答

3

是的，有更好的方法 - 您可以将要删除的项移动到向量末尾。然后在循环结束后只需剪切向量末尾即可。

- Karel Petranek

如果您修改了向量，即使在结尾处，迭代器循环仍然有效吗？ - Benoit Thiery

如果你只是交换两个项目来修改向量，迭代器将不会失效。添加操作可能会使其失效。 - Karel Petranek

1

我建议将您想要保留的元素拷贝到另一个向量中，而不是在每次删除后再从开始解析向量。此外，如果在循环中不再修改集合，则应该在循环外部存储end()方法返回的迭代器，因为对于某些STL实现来说，调用end()是昂贵的。一些编译器正在优化这个问题，但并非总是如此。

- Benoit Thiery

在这里缓存end()不是一个好主意，因为当调用erase()时它将被无效化。 - Karel Petranek

我建议不再调用erase()，因此在这种情况下可以缓存end()。 - Benoit Thiery

0

首先对向量进行排序可能有所帮助，因为集合本身是有序的。一种变体方法是按照在集合中的存在来对向量进行排序，然后同时截取所有项。

- xPheRe

0

我不确定你所要求的是两个向量的交集，但如果是的话，你可以看一下std::set_intersection。

不过需要注意的是，这需要向量已经排序。

- ereOn

0

算法remove_if()可以做到这一点，但您需要一个谓词来确定该项不在您的集合中。

您还可以使用remove_copy_if()将项目复制到新向量中。

如果您的向量已排序，则可以使用set_intersection。这也只允许找到的每个元素有一个副本。

- CashCow

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

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

- James McNellis · Accepted Answer

可以使用自定义谓词和删除/擦除惯用语来实现。

template <typename SetT>
struct not_contained_in_set_impl
{
    not_contained_in_set_impl(const SetT& s) : set_(s) { }

    template <typename T>
    bool operator()(const T& v)
    {
        return set_.find(v) == set_.end();
    }

    const SetT& set_;
};

template <typename SetT>
not_contained_in_set_impl<SetT> not_contained_in_set(const SetT& s)
{
    return not_contained_in_set_impl<SetT>(s);
}

用作：

orders.erase(
    std::remove_if(orders.begin(),
                   orders.end(),
                   not_contained_in_set(erase_if_not_found)), 
    orders.end());

[在我的脑海中编译]

如果你愿意先对范围进行排序，你就有其他选项，可能会更快(std::set_intersection，例如)。