无序向量中的 O(1) 删除

Question

在 C++ 程序中，我有一组普通旧数据，我需要能够高效地处理这些数据：

添加元素。
迭代整个集合。
删除其中一些元素（见下文更新）。迭代，见下文）。

我不必使用集或地图类型，因为没有外部要求：

索引到它
维护排序。
高效查找元素或测试它们是否在集合中。

如果我必须用 C 语言从头开始编写它，我会使用指数增长的动态数组，删除操作会将最后一个元素移到释放的槽中。这样删除是 O(1).

如果我想使用 C++ 标准容器，我似乎可以 (a) 使用 std::vector 但手动编写删除操作或 (b) 使用 std::list。我对链表有轻微但明确的厌恶。

这两种解决方案对我来说都是可以接受的，但我真的更愿意同时使用这两种方法：使用向量但仅使用标准操作。有没有办法做到这一点。

更新：

下面的评论表明我不是在寻找一般的删除操作。我的问题要求我经常遍历集合，并且在每次遍历时我都希望发现必须删除一些元素。

无论删除多少次，我都可以在 O(n) 时间内完成整个操作。但这显然是一个定制操作，我应该知道我需要编写自己的循环。令人惊讶的是 remove_if almost 解决了我的问题。如果我在迭代过程中唯一需要做的是识别过时的元素，那么 remove_if 就可以完成这项工作，但我还需要进行其他处理。

Answer 1

您可以在向量中为 delete 函数编写包装器，其中将最后一个元素复制到要删除的位置，然后在最后一个元素处调用标准 erase 函数.擦除最后一个元素将是 O(1).

它会是这样的：

void delete(vector<int> data, int position)
{
  data[position] = data[data.size() - 1];
  data.erase(data.begin() + data.size() - 1);
  return;
}

我假设要删除一个数字，您需要给出要删除的位置。如果是别的，请说明。

Answer 2

这是一个从容器末尾移动元素的擦除函数：

template <typename Vector>
void unordered_erase(Vector& v, typename Vector::iterator it) {
    *it = std::move(v.back());    
    v.pop_back();
}

Demo

Answer 3

其实标准库里已经有这些了：

将您的数据存储在 std::vector
使用std::remove_if followed by std::vector::erase which can then act on the very end of the vector (see Erase-remove idiom). Alternatively, you can have a look at boost::remove_erase_if删除数据，虽然我不知道这是否会不必要地保留顺序。但至少最后是O(n)。
使用 std::vector::push_back (or std::vector::insert(end) 添加数据以有效地插入整个范围）

std::remove_if 还允许您在单次迭代中删除一大堆元素。

而且，可能最重要的是，由于您的数据是连续存储的，因此迭代速度将最快 -> 没有缓存未命中。

Answer 4

这取决于集合的大小、每个元素的大小等。根据 bog 标准向量的大小和性能，您可以创建一个新向量，对旧向量进行一次传递并仅推送项目那不匹配。那是 O(N)。

标准库有 std::copy_if。例如，以下内容从第一个向量中删除所有值 2。剩下的在第二个。

#include <vector>
#include <algorithm>
#include <iterator>

int main(void)
{
    std::vector<int> v1 = { 1, 2, 2, 3, 4, 5, 6, 6, 7, 8, 9, 2, 3, 2, 2};
    std::vector<int> v2;

    std::copy_if(v1.begin(), v1.end(), std::back_inserter(v2), [](int value) { 
        return value != 2;
    });

}

在我的性能测试中（使用 50,000,000 个随机数），这比 remove_if 方法稍慢，但是：

第 32 版：copy_if (1412)，remove_if (1120)

第 64 版：copy_if (1420)，remove_if (1141)

Answer 5

您的整个问题的可能解决方案：

std::vector<MyClass> v;
// ...fill v...
v.erase(std::partition(v.begin(), v.end(), [](MyClass& element) -> bool {
    // ...process element and return false if element should be deleted.
}), v.end());

我知道已经晚了，但仍然有人会觉得它有用。

Answer 6

这是 remove_if 的替代方法，它可以在不维持秩序的情况下进行换回。

/// faster remove_if, but it doesn't keep order.
/// Swaps matched items to back; returns iterator to start of matched items
template <typename C, typename F>
inline typename C::iterator swapBackIf(C & v, F comp) {
  auto iter = v.begin();
  auto rear = v.end();
  for (iter; iter < rear; ++iter) {
    auto const& ele = *iter;
    if (comp(ele)) {
      std::iter_swap(iter, --rear);
    }
  }
  return rear;
}

无序向量中的 O(1) 删除

O(1) deletion in an unordered vector

c++

stl

vector