std::vector在增加容量时是否必须移动对象？或者，分配器是否可以“重新分配”？

Question

一个不同的问题启发了以下想法：

当 std::vector<T> 增加其容量时，是否必须移动所有元素？

据我所知，标准行为是底层分配器请求一个新大小的整个块，然后将所有旧元素移动过去，然后销毁旧元素，最后释放旧内存。

在标准分配器界面给出的情况下，这种行为似乎是唯一可能的正确解决方案。但是我想知道，修改分配器以提供一个reallocate(std::size_t)函数是否有意义，可以返回一个pair<pointer, bool>并映射到底层realloc()？这样做的优点是，如果操作系统实际上只能“扩展”已分配的内存，则根本不需要移动。布尔值将指示内存是否移动。

（std::realloc()也许不是最好的选择，因为如果我们无法扩展，则无需复制数据。因此，事实上，我们更想要像extend_or_malloc_new()这样的东西。 编辑：也许基于is_pod的特化可以允许我们使用实际的realloc，包括其位拷贝。只是不是普遍适用的。）

这似乎是一个被忽视的机会。最坏的情况下，您总是可以将 reallocate(size_t n) 实现为 return make_pair(allocate(n), true);，因此不会有任何惩罚。

在C ++中，是否存在任何问题使此功能不合适或不可取？

也许唯一可以利用此功能的容器是std::vector，但是那又是一个非常有用的容器。

---

更新：一个小例子以澄清。当前的 resize():

pointer p = alloc.allocate(new_size);

for (size_t i = 0; i != old_size; ++i)
{
  alloc.construct(p + i, T(std::move(buf[i])))
  alloc.destroy(buf[i]);
}
for (size_t i = old_size; i < new_size; ++i)
{
  alloc.construct(p + i, T());
}

alloc.deallocate(buf);
buf = p;

新实现：

pair<pointer, bool> pp = alloc.reallocate(buf, new_size);

if (pp.second) { /* as before */ }
else           { /* only construct new elements */ }

- Kerrek SB

---

我认为它不需要成对出现，你可以直接与传入的指针进行比较。只要重新分配理解适当的移动语义，我想不到任何问题。 - Mooing Duck

@MooingDuck：针对您的第一条评论：唯一的可能性是，如果分配器的增长函数在无法增长时失败，并将内存保持为之前的状态（没有位拷贝）。当您比较realloc指针的时候，损坏已经发生了。 - David Rodríguez - dribeas

@Praetorian：位拷贝存在不同的问题......例如，可能存在内部指针。例如，我使用了一个实现了“NullObject”模式的对象，其中对象包含一个“null-object”和一个指向当前对象的指针，该指针可以引用动态分配的“real-object”，也可以引用“null-object”成员。在对象为* null *的情况下，指针将引用同一对象的另一个成员。在这种情况下，进行位拷贝将导致悬空指针。 - David Rodríguez - dribeas

std::deque是最不幸的容器之一。它在自己擅长的方面表现得非常出色，但你几乎从不需要它所擅长的功能。相较于 std::deque, 一个几何级数增长的循环缓冲区将是一个更好的 std:: 容器候选。循环缓冲区具有更好的性能和更少的复杂性。但是它不能像 std::deque 和 std::list 那样保证引用的稳定性。根据我的经验，循环缓冲区比 std::deque 更好地解决了大多数推入/弹出队列问题。当循环缓冲区无法解决问题时，std::list 是正确的选择。 - Howard Hinnant

@KerrekSB - 这不是Peter的意思：他并不是说应该在全局范围内替换operator new。相反，他建议vector实现可以专门化其分配器以使用realloc来移动平凡可复制对象（可能在原地扩展分配而不移动），或者使用calloc来初始化零初始化对象（尽管似乎没有一种特性可以检测到类是否具有等效于零初始化构造函数）。 - BeeOnRope

Answer 1

当std::vector<T>的容量不足时，它必须分配一个新块。您正确地解释了原因。

在我看来，增加分配器接口是有意义的。我们两个人尝试过为C++11增加接口，但我们无法得到支持：[1][2] 我确信为使其工作需要额外的C级API。我也未能获得对此的支持：[3]

- Howard Hinnant

---

自定义的C++分配器将受益于一个C realloc-but-don't-move函数。这是向C委员会提出此建议的主要动机。 - Howard Hinnant

嗯，总有可能其他用户定义的类使用具有“可能增长”接口的分配器。可惜它被拒绝了。不过，编写一个比规定的分配器接口更多的分配器是否可以呢？ - Kerrek SB

你不能直接使用mmap内存吗？我的意思是，向量分配一些内存，然后将其映射，并在映射上工作。一旦你用完了内存，就再分配一些内存，并在先前的mmap块之后进行映射。这可能只适用于Unix，并且会增加向量的大小（您必须为每个分配存储一个指针，以便能够正确地销毁向量），但它基本上意味着在Linux、BSD和MacOS上，向量永远不需要复制/重新分配其元素。也许这只是一个愚蠢的想法，但在Unix上，魔术环形缓冲区类似于这种方式而没有问题。 - gnzlbg

我明白了，谢谢Howard。我记得几年前玩过一个向量，它基本上会预先请求大量虚拟内存（几GB），但只有在需要时才分配该内存，从而消除重新分配并使强异常安全性更容易实现。不过它不支持分配器。如果你正在使用mmap，你可以在向量内部有两个指针，指向同一个对象的两个不同地址。这不会通过向量API泄漏，但可能是边缘未定义行为。我觉得很有趣。 - gnzlbg

@gnzlbg - 你实际上不需要为每个mmap维护一个指针来进行释放。我猜你的假设是你需要将从mmap获取的相同指针传回munmap（就像new和delete），但事实并非如此：你只需传递要删除的整个页面范围，即使它们来自不同的mmap调用，它们也会被释放。即使其中一些未映射，这甚至不是错误！因此，您只需要指向区域开头的指针（已经是向量的一部分）和容量（已经是向量的一部分）... - BeeOnRope

Answer 2

在大多数情况下，realloc通常不会扩展内存，而是分配一个单独的块并移动内容。这一点在最初定义C++时已经考虑过了，并且决定当前界面更简单，在普遍情况下效率不会降低。

在实际生活中，实际上很少有realloc能够进行增长。在任何malloc具有不同池大小的实现中，新大小（记住vector 大小必须成几何级数增长）可能会落入另一个池中。即使是未从任何内存池中分配的大块，仅当较大大小的虚拟地址可用时，它才能增长。

请注意，尽管realloc有时可以在不移动的情况下增加内存，但在realloc完成时，它可能已经（按位）移动了内存，对于所有非POD类型，这种二进制移动将导致未定义的行为。我不知道任何分配器实现（POSIX、*NIX、Windows），可以向系统询问它是否能够增长，但如果需要移动，则会失败。

- David Rodríguez - dribeas

---

我认为他指的是一个新的内存重新分配函数，与malloc.h中的'realloc'不兼容，当无法原地调整大小时，它不会移动内容，也不会释放旧的内存块。 - Ben Voigt

此外，VirtualAlloc和mmap允许您请求紧随您的块之后的地址，因此您要么扩展该块，要么失败。但是我也不知道有哪些基于堆的分配器支持“如果可能则增长”的操作。 - Ben Voigt

@BenVoigt：显然这样的功能肯定已经存在：我只需要撕裂realloc并消除执行位移操作的部分，不是吗？realloc++ :-) - Kerrek SB

Linux 提供了 mremap 函数，您可以使用它来扩展现有的匿名内存映射（或在尝试时失败）。 - Nemo

另一个阻碍问题是C++保证，如果std::vector增长，用户可替换的new将被调用，但在另一个编译单元中可能会被覆盖，而此模板无法看到它。C++标准库容器是否保证调用可替换的new函数？。这也是优化零初始化向量以使用calloc或与new/delete兼容的等效函数的问题，而C++再次忽略了提供。 - Peter Cordes

Answer 3

没错，标准分配器接口确实没有为可进行memcpy的类型提供优化。

使用boost类型特征库可以确定一个类型是否可以进行memcpy（不确定它们是否直接提供，或者需要基于boost构建复合类型鉴别器）。

无论如何，要利用realloc()，可能需要创建一种新的容器类型，可以明确地利用这种优化。使用当前的标准分配器接口似乎不可能。

- Maxim Egorushkin

---

不，不，我不关心可复制性。我已经准备好调用分配器的构造和析构序列。我只是想给分配器一个懒惰的机会！ - Kerrek SB