使用索引向量来删除另一个向量中的元素。

Question

我有两个向量，其中一个是另一个向量的索引向量，我想要删除它。目前我正在执行以下操作：

#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()需要引用同一个向量的迭代器。

- Xu Wang

---

你的删除标准是什么？你想随机删除元素吗？ - K-ballo

如果你想通过索引从向量中删除多个元素，也许更容易的方法是构建一个新的向量，只包含你想要保留的元素。 - didierc

@didierc：你应该把它做成一个答案。当前的答案，在我看来，要么不完整，要么不能保证在所有实现中都能正常工作。 - Benjamin Lindley

@BenjaminLindley 完成了！如果您认为需要进行一些调整，请告诉我（或进行编辑）。 - didierc

Answer 1

在IT技术中，有一种常见的删除标准序列元素的技巧，称为“擦除/删除惯用语”。首先使用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()
);

- K-ballo

---

谢谢K-ballo。这是一个有用的解决方案。 - Xu Wang

Answer 2

    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());

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

        return std::find(remove_these.begin(), remove_these.end(), counter++) != remove_these.end();

- Jonathan Wakely

---

"remove_these" 是一个 "vector<int>"，所以这样做是行不通的。 - K-ballo

哦，从后往前工作可能会有性能优势，因为您只移动已经访问并知道要保留的元素，而不浪费时间移动以后可能被删除的元素。我得调查一下... - Jonathan Wakely

这就是我提问时所想的。我不确定标准对于实现添加那种重载的规定是什么。 - K-ballo

Lambda函数是否有返回值？ - David G

@David: 简单的 lambda 表达式如果只包含一个 return 语句，则不需要显式指定返回值。 - K-ballo

Answer 3

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

• 你正在使用具有连续索引的容器，因此每次删除元素后，其后的所有元素都会被重新索引（这就是为什么你必须按相反的顺序进行删除的原因），
• 该容器还恰好以连续方式存储其元素，因此任何删除操作都可能触发重新分配，并且至少会导致复制元素以满足连续性约束。

鉴于这两个问题，在某些情况下，将要保留的元素复制到新容器中可能比进行删除更有意义。在你的情况下，似乎复制元素不应该成为一个大问题，因为许多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检查所给定的键是否在remove_these中来使用它，但时间复杂度会比上面的解决方案略高。

- didierc

---

谢谢didierc。我改变了我的策略，现在使用“保留”方法而不是“删除”方法。特别感谢您的伟大讨论和解释！ - Xu Wang