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

Question

如果我设置如下:

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

auto itr = dummyset.find(5);

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

但这需要线性时间.

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

例:

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()),则无法绕过它 - 您需要实际擦除.没有办法告诉这些函数暂时作用于子范围而不是整个容器(我认为这是你要求的).

可能性并不像你想象的那么糟糕.实现知道它正在做什么,并且应该只根据实际需要重新平衡其内部树,给定一系列要删除的元素.