0

我目前正在实现我自己的矢量容器，我遇到了一个非常有趣的问题（至少对我来说）。这可能是一个愚蠢的问题，但 idk。

我的向量使用一个堆指针数组来堆分配未知类型（T**）的对象。我这样做是因为我希望单个元素的指针和引用保持不变，即使在调整大小之后也是如此。

这会在构造和复制时以性能为代价，因为我需要在堆上创建数组以及在堆上创建数组的每个对象。（堆分配比堆栈慢，对吧？）

T** arr = new *T[size]{nullptr};

然后对于每个元素

arr[i] = new T{data};

现在我想知道它是否安全、有益（更快）和可能，如果不是单独分配每个对象，我可以在堆上创建第二个数组并将每个对象的指针保存在第一个数组中。然后使用（并删除) 这些对象稍后就好像它们是单独分配的。

=> 在堆上分配数组是否比单独分配每个对象更快？

=> 在数组中分配对象并稍后忘记数组是否安全？（我觉得听起来很愚蠢）

链接到我的 github 仓库：https ://github.com/LinuxGameGeek/personal/tree/main/c%2B%2B/vector

谢谢你的帮助 ：）

4

5 回答 5

5

首先要说一句，您不应该从效率方面考虑比较堆/堆栈，而是考虑对象生命周期：

  • 自动数组（你在 stack 上调用的）在定义它们的块的末尾结束它们的生命
  • 动态数组（你在 heap 上调用什么）存在，直到它们被显式删除

现在，在一个数组中分配一堆对象总是比单独分配它们更有效。您保存了许多内部调用和各种数据结构来维护堆。简单地说，您只能释放数组而不是单个对象。

最后，除了一般可复制的对象之外，只有编译器而不是程序员知道确切的分配细节。例如（对于常见的实现）一个自动字符串（在堆栈上）包含一个指向动态字符数组（在堆上）的指针......

换句话说，除非您打算仅将容器用于 POD 或可复制的对象，否则不要期望自己处理所有分配和释放：非平凡对象具有内部分配。

于 2020-12-16T11:37:22.780 回答
2

堆分配比在堆栈上慢，对吧？

是的。动态分配是有代价的。

在堆上分配数组是否比单独分配每个对象更快？

是的。多次分配使成本成倍增加。

我想知道这是否可能......如果不是单独分配每个对象，我可以在堆上创建第二个数组并将每个对象的指针保存在第一个数组中

这将是可能的，但并非微不足道。认真思考如何实现元素擦除。然后考虑如何使用包含已删除元素的索引的数组正确实现其他功能，例如随机访问容器。

... 安全的

它可以安全地实施。

... 有益（更快）

当然，将分配从 N 减少到 1 本身就是有益的。但它是以某些方案为代价来实施擦除的。这个成本是否大于减少分配的好处取决于很多事情，比如容器的使用方式。

在数组中分配对象并稍后忘记数组是否安全？

“忘记”分配似乎是说“内存泄漏”的一种方式。

您可以使用自定义“池”分配器获得类似的优势。实现对容器的自定义分配器的支持可能更普遍有用。

PS Boost 已经有一个支持自定义分配器的“ptr_vector”容器。无需重新发明轮子。

于 2020-12-16T11:38:25.893 回答
1

我这样做是因为我希望单个元素的指针和引用保持不变，即使在调整大小之后也是如此。

您应该只使用std::vector::reserve来防止矢量数据在调整大小时重新分配。

Vector 非常原始，但经过高度优化。你很难用你的代码打败它。只需检查其 API 并尝试其所有功能。要创建一些更好的模板编程高级知识（显然您还没有）。

于 2020-12-16T11:44:33.543 回答
1

您试图提出的是对类似双端队列的容器使用放置新分配。这是一个可行的优化，但通常这样做是为了减少分配调用和内存碎片，例如在某些 RT 或嵌入式系统上。在这种情况下，该数组甚至可能是一个静态数组。但是，如果您还要求 T 的实例占据相邻空间，这是一个矛盾的要求，诉诸它们会扼杀任何性能提升。

... 有益（更快）

取决于 TEg，没有必要对字符串或共享指针之类的东西这样做。或者任何实际上在其他地方分配资源的东西，除非 T 也允许改变这种行为。

我想知道这是否可能......如果不是单独分配每个对象，我可以在堆上创建第二个数组并将每个对象的指针保存在第一个数组中

是的，即使使用标准 ISO 容器，这也是可能的，这要归功于分配器。如果此“数组”似乎是多个写入者和读取者线程之间的共享资源，则存在线程安全或意识问题。您可能希望实现线程本地存储，而不是使用共享存储，并为交叉情况实现信号量。

通常的应用不是在堆上分配，而是在预先确定的静态分配的数组中分配。或者在程序开始时分配一次的数组中。

请注意，如果您使用placement new，则不应在创建的对象上使用delete，您必须直接调用析构函数。就删除而言，放置新重载并不是真正的新重载。您可能会也可能不会导致错误，但如果您使用静态数组肯定会导致崩溃，并且在删除与动态分配的数组开头具有相同地址的元素时会导致堆损坏

于 2020-12-16T11:49:57.837 回答
0

这会在构造和复制时以性能为代价，因为我需要在堆上创建数组以及在堆上创建数组的每个对象。

复制POD非常便宜。如果您研究完美转发，您可以实现构造函数和emplace_back()函数的零成本抽象。复制时，使用std::copy()它非常快。

在堆上分配数组是否比单独分配每个对象更快？

每次分配都要求您向操作系统请求内存。除非您要求特别大量的内存，否则您可以假设每个请求将是一个恒定的时间量。与其要求 10 次停车位，不如要求 10 个停车位。

在数组中分配对象并稍后忘记数组是否安全？（我觉得听起来很愚蠢）

看你说的安全是什么意思。如果你不能自己回答这个问题，那么你必须清理内存并且在任何情况下都不能泄漏。

您可能会忽略清理内存的一个例子是，当您知道程序将要结束并且清理内存只是为了退出时有点毫无意义。不过，你应该清理它。阅读Serge Ballesta的答案，了解有关生命周期的更多信息。

于 2020-12-16T11:27:23.260 回答