使用许多块实现的向量，没有调整大小的副本

Question

我想知道是否有可能实现一个类似stl的向量，其中存储是以块为单位完成的，而不是分配更大的块并从原始块复制，您可以将不同的块保存在不同的位置，并重载operator[]和迭代器的operator++，这样向量的用户就不会意识到块是不连续的。

这可以在超出现有容量时保存一份副本。

Answer 1

您将查找std::deque

请参阅 Using Vector and Deque

在大多数情况下，更喜欢使用deque (有争议)

包含用于演示行为的基准

最新的C++11标准规定：

§23.2.3序列容器

2序列容器为程序员提供了不同的复杂性权衡，应该相应地使用。向量或数组是默认使用的序列容器类型。当序列中间频繁插入和删除时，应使用list或forward_list。当大多数插入和删除发生在序列的开头或结尾时，deque是所选择的数据结构。

FAQ > Prelude's Corner > Vector or Deque? (intermediate)说：

• 向量只能有效地将项目添加到末尾，任何试图在向量中间或开头插入项目的尝试都可能而且通常是非常低效的。双端队列可以在固定时间，O(1)中插入项目的开头和结尾，这是非常好的。在中间插入仍然是低效的，，但是如果需要这样的功能，应该使用列表。双端队列用于在前面插入的方法是push_front()，也可以使用insert()方法，但push_front更清晰。

• 就像well.

一样，在向量前面的擦除是低效的，但是双端队列提供了从前面持续的时间擦除，就像一样

• 双端队列更有效地使用内存。考虑内存碎片，一个向量需要N个连续的内存块来保存它的项目，其中N是项目的数量，一个块是单个项目的大小。如果向量需要5或10兆字节的内存，这可能是一个问题，但可用内存被分割到没有5兆或10兆字节的连续内存的程度。A deque没有这个问题，如果连续内存不足，deque会使用一系列较小的内存

..。

Answer 2

是的这是可能的。

你知道绳索吗？这就是你所描述的，对于字符串(big string == rope，明白这个笑话了吗？)。Rope不是该标准的一部分，但出于实际目的:它可以在现代编译器上使用。您可以使用它来表示文本编辑器的完整内容。

看看这里：STL Rope - when and where to use

并且永远记住：

• (性能)优化的第一条规则是: do
• 第二条规则(仅限专家)：不要现在就做。