C++:vector和list之间的混合:类似于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> >并且第一个矢量可以很小,然后可以进一步增长.实际上我想隐藏在使用中,所以我可以做一个mycontainer.push_back(x).

std::rope 有点类似,但标准中没有.

在Boost中有这样的东西吗？

Answer 1

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