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

如果我设置如下:

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

最佳答案

您不能，也可能不需要。

C++的算法采用迭代器对。因此，不要将dummyset.begin()和dummyset.end()传递给您经过调整的迭代器。

但是，如果您使用的是set成员函数(如成员.find())，则无法解决它-您实际上需要擦除。没有办法告诉这些函数暂时作用于子范围而不是整个容器(我相信这是您要的)。

奇怪的是，这还没有你想的那么糟。该实现知道它在做什么，并且在给定一系列要删除的元素的情况下，仅应根据实际需要重新平衡其内部树。