为什么libc ++ std :: vector在内部保留三个指针而不是一个指针和两个大小？

Question

我正在研究std::vectorlibc ++ 中的实现,我注意到它内部保留了三个指针(一个指向开头,一个结束,一个指向已分配内存的末尾),而不是我本能地做的,即,一个指针开始和两个size和capacity成员.

这是来自libc ++的代码<vector>(忽略压缩对,我知道它意味着什么).

pointer                                    __begin_;
pointer                                    __end_;
__compressed_pair<pointer, allocator_type> __end_cap_;

我注意到其他标准库也做同样的事情(例如Visual C++).我没有看到为什么这个解决方案应该比另一个解决方案更快的任何特殊原因,但我可能是错的.

那么"三指针"解决方案是否优于"指针+尺寸"解决方案？

Answer 1

这是因为基本原理是性能应该针对迭代器而不是索引进行优化.
(换句话说,性能应该优化begin()/ end(),而不是size()/ operator[].)
为什么？因为迭代器是通用指针,因此C++鼓励它们的使用,并且反过来确保它们的性能与原始指针的性能相匹配.

要了解性能问题的原因,请注意典型的for循环如下:

for (It i = items.begin(); i != items.end(); ++i)
    ...

除了在最微不足道的情况下,如果我们跟踪大小而不是指针,那么将会发生的比较i != items.end()将会变成i != items.begin() + items.size()比预期更多的指令.(在许多情况下,优化器通常很难分解代码.)这会在紧密循环中显着减慢速度,因此避免了这种设计.

(我在尝试编写自己的替代品时已经验证了这是一个性能问题std::vector.)

编辑:正如Yakk在评论中指出的那样,当元素大小不是2的幂时,使用索引而不是指针也会导致乘法指令的生成,这非常昂贵并且在紧密循环中很明显.在写这个答案时我没有想到这一点,但这是一个让我感到困扰的现象(例如见到这里)......底线是,在一个紧密的循环中,一切都很重要.