C++: vector 和列表之间的混合:类似于 std::rope？

Question

当存储一堆元素并且我不需要随机访问容器时，我使用了 std::list这大部分都很好。然而，有时(尤其是当我只是将条目推回后面并且从不删除中间的某个地方时)，我希望我有一些具有更好性能的结构来添加条目。

std::vector不好是因为:

• 如果它不再适合，它必须重新分配。
• 它不适用于大量数据(因为您不能总是获得非常大的连续空闲内存块)。

std::list不好是因为:

• 它对每个 push_back 进行分配。这很慢并且会导致大量内存碎片。

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

基本上，我想要类似 std::list< boost::array<T, 100> > 的东西或者。或者也许可以代替 100 , 让它成为 4096/sizeof(T) .也许还有std::list< std::vector<T> >并且第一个 vector 可以很小，然后可以增长更多的 vector 。实际上我想在使用中隐藏它，所以我可以做一个 mycontainer.push_back(x) .

std::rope 有点类似，但是没有在标准中。

Boost 里有这样的东西吗？

Answer 1

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