使用for循环删除向量中的元素

Question

我该如何使用for循环通过索引从向量中删除元素？我遇到了向量越界的错误。下面是示例代码：

 vector<int> to_erase = {0, 1, 2}; 
 vector<int> data     = {3, 3, 3, 3};

 for(int i = 0; i < to_erase.size(); i++) {

    data.erase(data.begin() + to_erase[i]);
 }

我认为问题出在我的向量大小在每次迭代中都会减小，因此它无法访问索引2。

- RuiQi

---

也许你可以对索引数组进行排序，然后从最后一个元素开始删除。 - Aleksej

Answer 1

通常情况下，你会使用删除-移除习语来高效地从向量中删除多个元素（逐个删除通常不太高效，并且，正如你所见，有时并不是那么容易）。在其最一般的形式中，这个习语看起来像这样：

data.erase(remove_algorithm(begin(data), end(data)), end(data));

在您的情况下，remove_algorithm 基于另一个向量中的索引，因此我们还需要提供这些索引：

data.erase(
    remove_indices(begin(data), end(data), begin(to_erase), end(to_erase)),
    end(data));

不幸的是，标准库中并没有包含这样的算法。然而，自己编写此算法非常简单¹：

template <typename It, typename It2>
auto remove_indices(It begin, It end, It2 idx_b, It2 idx_e) -> It {
    using idx_t = typename std::iterator_traits<It2>::value_type;
    std::sort(idx_b, idx_e, std::greater<idx_t>{});

    for (; idx_b != idx_e; ++idx_b) {
        auto pos = begin + *idx_b;
        std::move(std::next(pos), end--, pos);
    }
    return end;
}

在这里，我们首先将要删除的索引从大到小排序。接下来，我们循环遍历这些索引。然后，我们（最大化地高效）将当前位置（要删除的位置）和向量末尾之间的所有元素向前移动一个位置。随后，末尾减少了一个（因为一个元素被删除了）。

现场代码

---

¹ *咳嗽* 一旦您清除了代码中的所有愚蠢的错别字。

- Konrad Rudolph

Answer 2

在迭代时删除一组元素是不安全且可能很昂贵的。我建议符合您条件的每个元素都与末尾的一个元素交换。(在末尾，因为从末尾删除会更便宜)。您可以跟踪从向量末尾返回了多少(基于交换数量)，并尽早退出循环。现在根据您交换的元素数量，您可以执行类似以下操作：

data.resize(data.size() - reverse_counter);

或者

int pos = data.size() - reverse_counter;
data.erease(data.begin()+pos, data.end();

这只是伪代码，用于解释思路。

正如参考中提到的，不要在末尾执行删除操作，因为它会触发重新分配，这是很耗费资源的。值得记住的一点是： http://www.cplusplus.com/reference/vector/vector/erase/

- Marco Giordano

Answer 3

我认为这是因为我的向量大小在每次迭代中都会减小。

是的！

您可以通过保留一个额外的变量来计算已删除的元素数量来实现此目的，就像这样：

#include <iostream>
#include <vector>

using namespace std;

int main() {
        vector<int> to_erase = {0, 1, 2}; 
        vector<int> data     = {3, 3, 3, 3};

        int count_removed = 0;
        for(unsigned int i = 0; i < to_erase.size(); i++)
                data.erase(data.begin() + to_erase[i] - count_removed++);

        for(unsigned int i = 0; i < data.size(); ++i)
                        cout << data[i] << "\n";
        return 0;
}

输出：

3

当我第一次使用std::erase()时，我也遇到了同样的问题，好问题，+1。

- gsamaras

---

@Marievi 希望瑞琪也能发现它有用。 - gsamaras

Answer 4

我认为这是一种不好的设计，因为你将改变for循环不变量，并需要大量的解决方法来实现这一点。无论如何，如果你真的想使用for循环，你可以标记要删除的内容并运行stl remove_if，就像这样：

#include <iostream>
#include <vector>
#include <limits>
#include <algorithm>
using namespace std;

int main() {

    vector<int> to_erase = {0, 1, 2}; 
    vector<int> data     = {3, 3, 3, 3};

    cout << "Before:\n" ;
    for(int i=0; i<data.size(); i++)
        cout << i << "\t";
    cout << endl;   
    for(int i=0; i<data.size(); i++)
        cout << data[i] << "\t";
    cout << endl;

    for(int i = 0; i < to_erase.size(); i++) {
        //data.erase(data.begin() + to_erase[i]);
        data[i] = numeric_limits<int>::max();
    }

    data.erase(remove_if(data.begin(), 
                         data.end(), 
                         [](int i){return i==numeric_limits<int>::max();}), data.end());

    cout << "Next:\n" ;
    for(int i=0; i<data.size(); i++)
        cout << i << "\t";
    cout << endl;
    for(int i=0; i<data.size(); i++)
        cout << data[i] << "\t";

    return 0;
}

- wesley.mesquita