C++: std::vector 两端保留空间

Question

一些想法:

我想从大小为 n > x 的 std::vector 的开头删除 x 个元素。由于 vector 在内部使用数组，这就像将 vector.begin() 的指针设置为保留的第一个元素的索引一样简单。但相反，删除会将数组中的所有元素移动到第一个元素实际从索引 0 开始的位置，从而使删除操作花费的时间比它可能花费的时间要多得多。

此外，如果内部数组的有效“区域”真的只是由 vector 结构的一些开始和结束索引/指针控制，那么也可以选择在第一个元素前面保留空间。例如，初始化一个 vector ，在末尾保留 20 个空格，在开头保留 10 个空格。在内部，然后创建一个空间 30(或 32)的数组，其中起始索引/指针指向内部数组的第 11 个值，允许以恒定速度将新元素包含到“vector ”的前面。

好吧，我的意思是，我认为这样的数据结构会有些用处，至少对我来说是这样。我很确定有人已经想到了这一点并且已经实现了。所以我想问:我描述的数据结构是怎么称呼的？如果它存在，我很乐意使用它。我认为这不是双链表，因为在那里，每个元素都是一种包含元素值和指向邻居的附加指针的结构(据我所知)。

编辑:是的，这样的结构可能会使用比必要更多的内存，尤其是从一开始就删除一些元素时，因为那样的话，内部数组仍然具有初始大小。但是好吧，对于大多数问题来说，内存不再是一个大问题，并且可能会有一个(耗时的)“内存优化”操作来创建一个新的、更小的数组，复制所有旧值并删除旧的内部数组使用尽可能小的尺寸。

Answer 1

扩展@Kerrek SB 的评论，boost::circular_buffer<>我认为你需要什么，例如:

#include <iostream>
#include <boost/circular_buffer.hpp>

int main()
{
  boost::circular_buffer<int> cb(3);

  cb.push_back(1);
  cb.push_back(2);
  cb.push_back(3);

  for( auto i : cb) {
      std::cout << i << std::endl;
  }

  // Increase to hold two more items
  cb.set_capacity(5);
  cb.push_back(4);
  cb.push_back(5);

  for( auto i : cb) {
      std::cout << i << std::endl;
  }

  // Increase to hold two more items
  cb.rset_capacity(7);
  cb.push_front(0);
  cb.push_front(-1);

  for( auto i : cb) {
      std::cout << i << std::endl;
  }  
}

TBH - 我没有看过实现，所以无法评论它是否移动数据(我会非常惊讶。)但是如果你拉下源代码，如果性能是一个问题，请快速浏览一下以满足...

编辑:快速查看代码表明 push_xxx操作确实不会移动数据，但是 xxx_capacity操作确实会导致移动/复制 - 为避免这种情况，请确保环在开始时有足够的容量并且它将按您希望的方式工作...