tin*_*lyx 5 c++ stl vector deque c++11
我正在阅读有关deques vs vectors的文章,并且遇到了它的维基百科条目,其中说deque使用动态数组的三种可能实现之一是:
从底层数组的中心分配deque内容,并在到达任一端时调整底层数组的大小.这种方法可能需要更频繁的调整并浪费更多空间,特别是当元件仅插入一端时.
我想知道是否有任何实际使用此中心分配策略的STL(或STL风格)实现？
我问,因为这个策略看起来很吸引人,因为它只涉及一个底层数组,因此消除了内存不连续性问题,这可能是与之deque相比时唯一的主要问题vector.如果我理解正确,这很可能是std::vector允许O(1)pop_front(摊销)或替代deque内存连续性保证的替代品.我认为这是以a的缓冲空间加倍为代价的std::vector,这不是我用例的主要问题.
此外,在这样的容器中间插入/删除是否需要std::vector平均一半的时间？
更新:
正如@Lightness Races in Orbit指出的那样,这样的实施将不会在现行标准下使用,因为没有人可以从STL的每份合同的优势中受益,并且每个人都会受到不利影响.关于缺点的另一个问题是:
是否可以实现一个新的 vector或deque类似的容器(比如说bivector),除了功能/运营商之外std::vector,
1)提供(摊销)恒定时间push_front()和pop_front()操作
2)增加大小后保证内存连续但不保证迭代器有效性？
我想在幕后有一个阵列,很多间接/性能问题deque就会消失.
没有标准库（不是“STL”）实现会为此烦恼，因为它有您提到的缺点，而优点不是std::deque.
这些要求都是精心构建的，从各种操作的算法复杂性到迭代器失效规则。以没有人可以依赖该实现的优点的方式实现容器没有任何好处。
C++ 委员会是否可以在未来的标准中引入一个具有不同名称和不同约束的新容器，哪些供应商可以按照您的描述来实现？是的，他们可以。