4

我有两个向量，一个是我想擦除的另一个向量的索引向量。目前我正在做以下事情：

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

int main() {
        std::vector<std::string> my_vec;
        my_vec.push_back("one");
        my_vec.push_back("two");
        my_vec.push_back("three");
        my_vec.push_back("four");
        my_vec.push_back("five");
        my_vec.push_back("six");

        std::vector<int> remove_these;
        remove_these.push_back(0);
        remove_these.push_back(3);

        // remove the 1st and 4th elements
        my_vec.erase(my_vec.begin() + remove_these[1]);
        my_vec.erase(my_vec.begin() + remove_these[0]);

        my_vec.erase(remove_these.begin(), remove_these.end());

        for (std::vector<std::string>::iterator it = my_vec.begin(); it != my_vec.end(); ++it)
                std::cout << *it << std::endl;

        return 0;
}

但我认为这是不优雅和低效的。此外，我认为我必须小心对remove_these向量进行排序并从末尾开始（这就是我在索引 0 之前擦除索引 3 的原因）。我想要一个擦除命令，比如

my_vec.erase(remove_these.begin(), remove_these.end());

但是这当然行不通，因为my_vec.erase()期望迭代器引用相同的向量。

4

3 回答 3

6

从标准序列中擦除元素的已知习语是擦除/删除习语。您首先调用remove算法，将您想要保留的所有元素移动到序列的前面，然后erase将删除的元素移到序列的后面。在C++11中，它看起来像这样：

std::vector< std::string > strings;
strings.erase(
    std::remove_if(
        strings.begin(), strings.end()
      , []( std::string const& s ) -> bool
        {
            return /*whether to remove this item or not*/;
        }
    )
  , strings.end()
);
于 2012-12-30T20:13:02.787 回答
4 
    std::sort(remove_these.begin(), remove_these.end());

    int counter = 0;
    auto end = std::remove_if(my_vec.begin(), my_vec.end(),
                             [&](const std::string&) mutable {
        return std::binary_search(remove_these.begin(), remove_these.end(), counter++);
    });
    my_vec.erase(end, my_vec.end());

这remove_if与 lambda 函数一起使用，如果counter在向量中找到当前元素的索引（由变量跟踪） ，则返回 true remove_these。该向量已排序，以便binary_search可以用作优化。如果要删除的元素列表很小，则不对其进行排序并仅在 lambda 中使用它可能会更快：

        return std::find(remove_these.begin(), remove_these.end(), counter++) != remove_these.end();
于 2012-12-30T20:14:19.837 回答
1

在您的情况下，我认为有两个问题值得考虑：

  • 您正在使用具有连续索引的容器，因此每次删除一个元素时，它之后的所有元素都会被重新索引（这就是您必须在示例代码中以相反顺序进行删除的原因），
  • 该容器也恰好连续存储其元素，因此任何删除都可能触发重新分配，并且至少会引发元素的副本以满足连续性约束。

鉴于这两个问题，在某些情况下将您希望保留的元素复制到新容器中可能会很有趣，而不是进行删除。在您的情况下，复制元素似乎不是一个大问题，因为许多实现std::string使用写时复制策略，但您可能希望自己验证这一点。

要考虑的另一件事是，要删除的索引集可以很好地存储在位向量中。它相当有效，并且大大简化了算法。不过，您需要跟踪删除的元素的有效数量。

我个人会选择一个简单的循环，但 C++ 提供了许多方法来实现类似的结果。这是循环版本：

    std::vector<bool> remove_these(my_vec.size(), false):
    remove_these[0] = remove_these[4] = true;

    std::vector<std::string> my_result;
    my_result.reserve(my_vec.size() - 2);

    for (int i = 0; i < remove_these.size(); ++i)
        if (!remove_these[i])
             my_result.push_back(my_vec[i]);

注意reserve在向量填充期间避免多次重新分配的使用。

现在，剩下要做的就是将上面的代码包装在一个函数中，该函数将预先将 int 向量转换为 bool 向量：

template <typename IT>
void erase(std::vector<std::string> &my_vec, IT begin, IT end){
    std::vector<std::string> res;
    std::vector<bool> r(my_vec.size(), false);
    res.reserve(my_vec.size() - (end - begin));
    for (IT it = begin; it != end; ++it)
        r[*it] = true;
    for (int i = 0; i < r.size(); ++i)
        if (!r[i])
            res.push_back(my_vec[i]);
    my_vec = res;
}

就是这样。该算法的时间复杂度约为O(N+M)，其中 N 和 M 是 和 的my_vec大小remove_these。或者，可以将第二个循环替换为remove_if.

事实上，如果 stl 提供了一个函数来迭代一个序列，remove_if并调用一个谓词函数，参数是该迭代器的键和值，我们可以通过给它提供my_vec反向迭代器和一个 lambda 来检查给定的关键是 in remove_these，但时间复杂度会比上面的解决方案高一点。

于 2012-12-30T22:31:32.960 回答