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

Question

我想知道是否可以实现一个类似 stl 的向量，其中存储是在块中完成的，而不是分配一个更大的块并从原始块复制，您可以将不同的块保留在不同的位置，并重载运算符[]和迭代器的运算符++，以便向量的用户不知道块不连续。

当超出现有容量时，这可以保存副本。

Answer 1

您将寻找 std::deque

请参阅 GotW #54 使用向量和双端队列

在大多数情况下，更喜欢使用双端队列（有争议）

包含用于演示行为的基准测试

最新的 C++11 标准表示：

§ 23.2.3 序列容器

[2] 序列容器为程序员提供了不同的复杂性权衡，因此应相应地使用。
矢量或数组是默认应使用的序列容器类型。列表或转发列表
当序列中间频繁插入和删除时应使用。双端队列是
当大多数插入和删除发生在开头或结尾时选择的数据结构
序列。

常见问题解答 >前奏曲的角落>矢量还是双端队列？ （中级） 说：

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

• 就像插入一样，向量前面的擦除效率很低，但是双端队列也提供从前面进行恒定时间的擦除。

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

[...]

Answer 2

是的，这是可能的。

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

请看这里：STL 绳索 - 何时何地使用

以及永远记住：（

• 性能）优化的第一条规则是：不要这样做
• 第二条规则（仅适用于专家）：现在不要这样做。