c++ - 如何有效地从 C++ 中的集合中删除开始和结束元素？

Question

如果我设置如下:

set<int> dummyset = {2,3,4,5,6,7,8};

auto itr = dummyset.find(5);

如果我想从 2 到 4 中删除，我会输入 dummyset.erase(dummyset.begin(), itr);

但这需要线性时间。

假设我打算总是想从两端删除两个 block ，我可以只移动开始指针或结束指针(常数时间)而不是删除每个元素(线性时间)吗？

例子:

begin     end
|           |
V           V
1  2  3  4  5

// Delete {1,2} and {5} by moving pointers

1  2  3  4  5
      ^  ^
      |  |
  begin  end

Answer 1

你不能，你可能不需要。

C++ 的算法采用迭代器对。因此，不是 dummyset.begin() 和 dummyset.end()，而是将调整后的迭代器传递给它们。

但是，如果您正在使用 set 成员函数(如成员 .find())，则没有办法绕过它——您将需要实际删除。无法告诉这些函数暂时作用于子范围而不是整个容器(我相信这正是您所要求的)。

很可能这并不像您想象的那么糟糕。实现知道它在做什么，并且应该只在实际需要的情况下重新平衡其内部树，给定一个范围要删除的元素。