C++：向量和列表的混合:类似于std::rope的东西？

Question

当我存储一堆物品并且我不需要随机访问容器时，我使用的是一个std::list，它基本上是很好的。然而，有时(尤指)当我只是向后推回条目，而不是删除中间的某个地方)，我希望我有一些结构，更好的添加条目的性能。

std::vector是坏的，因为：

• 如果它不再合适就必须重新分配。
• 实际上不能处理大量的数据(因为你不能总是得到大量的连续空闲内存)。

std::list是坏的，因为：

，

• ，它在每个push_back上进行分配。这是缓慢的，导致大量的内存fragmentation.

所以，介于两者之间的东西是我想要的。

基本上，我想要一些类似std::list< boost::array<T, 100> >之类的东西。或者让它成为100，而不是4096/sizeof(T)。也许std::list< std::vector<T> >和第一个向量也可以是小的，然后进一步的向量可以生长。实际上，我想让它不被使用，所以我只需要做一个mycontainer.push_back(x)。

std::rope有点类似，但在标准中是不可用的。

有类似的东西在助推吗？

Answer 1

你考虑过使用std::deque吗？它的元素不是连续存储的，但它确实允许对元素的随机访问；如果您只是在序列的开头或结尾插入元素，那么它可能提供比std::vector更好的性能。

Answer 2

是的，它叫做std：：载体。O(1) time push_back几乎总是比std::list快。(是的，而且它也是内存高效的)

std::list最重要的特点是从中间删除/插入固定时间。如果您不需要它，请选择std::vector。