作为一个有很多汇编语言经验和旧习惯的人,我最近用 C++ 做了一个项目,使用了 c++03 和 c++11 必须提供的很多特性(主要是容器类,包括来自 Boost 的一些)。这出奇地简单——我尽我所能地倾向于简单而不是过早的优化。当我们进入代码审查和性能测试时,我敢肯定一些老手会因为看不到每个字节是如何被操纵的而有动脉瘤的,所以我想要一些先进的弹药。
我定义了一个类,其实例成员包含多个 vector 和映射。不是“指向” vector 和 map 的指针。我意识到我一点也不知道我的对象占用了多少连续空间,或者频繁清除和重新填充这些容器可能会对性能产生什么影响。
一旦实例化,这样的对象是什么样子的?
最佳答案
形式上,对实现没有任何限制 除标准中规定的以外,关于 接口(interface)和复杂性。实际上,大多数(如果不是全部) 实现源自相同的代码库,并且相当 相似的。
vector的基本实现是三个指针。这 vector 中对象的实际内存是动态的 分配。取决于载体是如何“生长”的,动态 区域可能包含额外的内存;三个指针指向 内存的开始,当前最后一个字节之后的字节 使用,以及分配的最后一个字节之后的字节。也许 实现中最重要的方面是它 分离分配和初始化: vector 将在 很多情况下,分配比需要更多的内存,而不 在其中构造对象,并且只会构造对象 需要的时候。此外,当您删除对象或清除 vector,它不会释放内存;它只会破坏 对象,并将指针更改为使用的末尾 内存来反射(reflect)这一点。稍后,当您插入对象时,没有 需要分配。
当您添加超出分配空间量的对象时,
vector 将分配一个新的、更大的区域;将对象复制到
它,然后销毁旧空间中的对象,并将其删除。
由于复杂性的限制, vector 必须增加面积
以指数方式,通过将大小乘以某个固定常数
(1.5 和 2 是最常见的因素),而不是
将它增加一些固定的数量。结果是,如果你
使用 push_back
从空增长 vector , 不会有的
太多的重新分配和拷贝;另一个结果是,如果你
从空开始增长 vector ,它最终可以使用几乎两倍
必要的内存。如果你能避免这些问题
使用 std::vector<>::reserve()
预分配.
至于 map ,复杂性限制以及它必须 有序意味着必须使用某种平衡树。 在我所知道的所有实现中,这是一个经典的 红黑树:每个条目单独分配,在一个节点中 它包含两个或三个指针,可能还有一个 bool 值,在 添加数据。
我可能会补充一点,以上内容适用于优化版本 容器。通常的实现,如果没有优化, 将添加额外的指针以将所有迭代器链接到 容器,以便在容器运行时标记它们 一些会使他们无效的东西,这样他们就可以做 边界检查。
最后:这些类是模板,所以在实践中,你有 访问资源,并可以查看它们。 (诸如此类的问题 异常安全有时会减少实现 比我们想要的更直接,但是实现 使用 g++ 或 VC++ 并不难理解。)
关于包含容器的对象的 C++ 布局,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/18423921/