0

作为一个有很多汇编语言经验和旧习惯的人，我最近做了一个 C++ 项目，使用了 c++03 和 c++11 必须提供的许多特性（主要是容器类，包括一些来自促进）。这出乎意料地简单——我尽我所能来支持简单而不是过早的优化。当我们进入代码审查和性能测试时，我确信一些老手会因为看不到每个字节是如何被操纵的而产生动脉瘤，所以我想要一些先进的弹药。

我定义了一个类，它的实例成员包含几个向量和映射。不是“指向”向量和地图的“指针”。而且我意识到我根本不知道我的对象占用了多少连续空间，或者频繁清除和重新填充这些容器可能对性能产生什么影响。

这样的对象在实例化后会是什么样子？

4

5 回答 5

4

形式上，除了标准中指定的那些，在接口和复杂性方面对实现没有任何限制。实际上，大多数（如果不是全部）实现都源自相同的代码库，并且非常相似。

vector 的基本实现是三个指针。向量中对象的实际内存是动态分配的。根据向量是如何“增长”的，动态区域可能包含额外的内存；这三个指针指向内存的开头，当前使用的最后一个字节之后的字节，以及分配的最后一个字节之后的字节。也许实现的最重要的方面是它将分配和初始化分开：在许多情况下，向量将分配比需要更多的内存，而不在其中构造对象，并且只会在需要时构造对象。另外，当你删除对象，或者清除向量时，它不会释放内存；它只会破坏对象，并将更改指向已用内存末尾的指针以反映这一点。之后，

当您添加的对象超出分配的空间量时，vector 将分配一个新的、更大的区域；将对象复制到其中，然后破坏旧空间中的对象，然后将其删除。由于复杂性的限制，向量必须以指数方式增长面积，通过将大小乘以某个固定常数（1.5 和 2 是最常见的因素），而不是通过某个固定数量增加它。结果是，如果您使用 将向量从空扩展push_back，则不会有太多的重新分配和复制；另一个结果是，如果你从空的向量中增长，它最终可能会使用几乎两倍于必要的内存。如果您预先分配使用std::vector<>::reserve().

至于地图，复杂性约束和它必须有序的事实意味着必须使用某种平衡树。在我所知道的所有实现中，这是一个经典的红黑树：每个条目都是单独分配的，在一个包含两个或三个指针的节点中，除了数据之外，还可能加上一个布尔值。

我可能会补充一点，上述内容适用于容器的优化版本。通常的实现，当没有优化时，会添加额外的指针来链接所有迭代器到容器，这样当容器做了一些会使它们无效的事情时，它们可以被标记，并且它们可以进行边界检查。

最后：这些类是模板，因此在实践中，您可以访问源代码并查看它们。（异常安全之类的问题有时会使实现不如我们希望的那么简单，但是使用 g++ 或 VC++ 的实现并不难理解。）

于 2013-08-24T23:18:26.793 回答
3

Amap是一棵二叉树（有些品种，我相信它习惯上是一棵红黑树），所以它map本身可能只包含一个指针和一些管理数据（例如元素的数量）。

与任何其他二叉树一样，每个节点将包含两个或三个指针（两个用于“左和右”节点，可能还有一个指向上面的前一个节点，以避免必须遍历整个树来找到前一个节点的位置（s ） 是）。

一般来说，vector不应该明显比常规数组慢，当然也不会比你自己使用指针实现的可变大小数组差。

于 2013-08-24T23:01:15.843 回答
1

向量是数组的包装器。矢量类包含一个指向连续内存块的指针，并且以某种方式知道它的大小。当您清除一个向量时，它通常会保留其旧缓冲区（依赖于实现），以便下次重用它时，分配较少。如果您将向量的大小调整为高于其当前缓冲区大小，它将必须分配一个新的。重用和清除相同的向量来存储对象是有效的。（std::string类似）。如果您想确切地找出向量在其缓冲区中分配了多少，请调用该capacity函数并将其乘以元素类型的大小。您可以调用该reserve函数来手动增加缓冲区大小，以期望向量很快会占用更多元素。

地图比较复杂所以我不知道。但是如果你需要一个关联容器，你也必须在 C 中使用一些复杂的东西，对吧？

于 2013-08-24T22:53:56.903 回答
1

只是想在其他人的答案中添加一些我认为重要的事情。

首先，默认值（在我见过的实现中）sizeof(std::vector<T>)是常量，由三个指针组成。以下是 GCC 4.7.2 STL 标头的摘录，相关部分：

template<typename _Tp, typename _Alloc>
struct _Vector_base
{
 ...
 struct _Vector_impl : public _Tp_alloc_type
 {
  pointer _M_start;
  pointer _M_finish;
  pointer _M_end_of_storage;
  ...
 };
 ...
 _Vector_impl _M_impl;
 ...
};

template<typename _Tp, typename _Alloc = std::allocator<_Tp> >
class vector : protected _Vector_base<_Tp, _Alloc>
{
 ...
};

这就是三个指针的来源。他们的名字是不言自明的，我想。但也有一个基类——分配器。这将我带到我的第二点。

其次，std::vector< T, Allocator = std::allocator<T>>采用第二个模板参数，这是一个处理内存操作的类。它是通过这个类vector的函数来做内存管理的。有一个默认的 STL 分配器std::allocator<T>>。它没有数据成员，只有诸如等之类的功能allocate。destroy它的内存处理基于new/delete. 但是您可以编写自己的分配器并将其提供给std::vector作为第二个模板参数。它必须符合某些规则，例如它提供的功能等，但是内存管理是如何在内部完成的——这取决于你，只要它不违反std::vector依赖的逻辑。它可能会引入一些数据成员，这些数据成员将sizeof(std::vector)通过上面的继承添加到。它还为您提供“对每一位的控制”。

于 2013-08-24T23:46:09.357 回答
0

基本上，avector只是一个指向数组的指针，以及它的容量（总分配的内存）和大小（实际使用的元素）：

struct vector {
    Item* elements;
    size_t capacity;
    size_t size;
};

当然，由于封装，所有这些都被很好地隐藏了，用户永远无法直接处理血淋淋的细节（重新分配，在需要时调用构造函数/析构函数等）。

至于您关于清除的性能问题，这取决于您如何清除向量：

  • 用一个临时的空向量（通常的习惯用法）交换它会删除旧数组：std::vector<int>().swap(myVector);
  • 使用clear()orresize(0)将擦除所有项目并保持分配的内存和容量不变。

如果您关心效率，恕我直言，要考虑的要点是reserve()提前调用（如果可以的话），以便预先分配数组并避免无用的重新分配和复制（或使用 C++11 移动）。当向向量添加大量项目时，这可能会产生很大的不同（众所周知，动态分配的成本非常高，因此减少它可以大大提高性能）。

关于这一点还有很多话要说，但我相信我已经涵盖了基本细节。不要犹豫，询问您是否需要有关特定点的更多信息。

关于地图，它们通常使用红黑树来实现。但是该标准并没有强制要求，它只给出了功能和复杂性要求，因此任何其他符合要求的数据结构都可以使用。我不得不承认，我不知道 RB 树是如何实现的，但我猜想，映射至少包含一个指针和一个大小。

当然，每种容器类型都是不同的（例如，无序映射通常是哈希表）。

于 2013-08-24T22:55:56.960 回答