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

Question

我正在查看 libc++ 中 std::vector 的实现，我注意到它在内部保留了三个指针（一个指向分配内存的开头，一个指向结尾，一个指向分配内存的结尾）我会本能地做的事情，即一个指向开始的指针和两个 size 和 capacity 成员。

这里是libc++的<vector>的代码（忽略压缩对，我知道是什么意思）

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

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

那么 "three pointers" 解决方案优于 "pointer + sizes" 解决方案是否有特定原因？

Answer 1

我想这主要是速度问题。在集合上迭代时，生成的边界检查指令将只是一个带有结束指针的比较语句（可能是一个加载），而不是一个加载、一个添加和一个比较（也可能是另一个加载）。

当为 end() 和 begin() 生成迭代器时，代码也只是 return pointer;，而不是 return pointer + offset; 为 end()。

这些是非常小的优化，但标准模板库旨在用于每个周期都很重要的生产代码。

PS：关于以相同方式实现它的不同编译器：有一个参考实现，大多数（所有？）编译器供应商都基于其 STL 实现。这个特定的设计决策很可能是参考实现的一部分，这就是为什么您查看的所有实现都以这种方式处理向量的原因。

Answer 2

这是因为性能应该针对迭代器而不是索引进行优化。
（换句话说，性能应该针对 begin()/end() 而不是 size()/operator[] 进行优化。）
为什么？因为迭代器是 广义指针 ，因此 C++ 鼓励使用它们，并且在 return 中确保当两者等效时它们的性能与原始指针的性能相匹配。

要了解为什么这是一个性能问题，请注意典型的 for 循环如下：

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

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

（我在尝试为 std::vector 编写自己的替代品时已验证这是一个性能问题。）

编辑： 正如 Yakk 在评论中指出的那样，使用索引而不是指针也会导致生成乘法指令当元素大小不是 2 的幂时，这在紧密循环中非常昂贵且引人注目。我在写这个答案时没有想到这一点，但这是一个以前困扰我的现象（例如参见 [=19=]）...底线是，在一个紧密的循环中，一切都很重要。

Answer 3

实现者更方便。

存储大小恰好使一个操作更容易实现：size()

size_t size() { return size_; }

另一方面，它使 other 更难编写并使代码重用更难：

iterator end() { return iterator(end_); } // range version
iterator end() { return iterator(begin_ + size_); } // pointer + size version

void push_back(const T& v) // range version
{
    // assume only the case where there is enough capacity
    ::new(static_cast<void*>(end_)) T(v);
    ++end_;
}

void push_back(const T& v) // pointer + size version
{
    // assume only the case where there is enough capacity
    ::new(static_cast<void*>(begin_ + size_)) T(v);
    // it could use some internal `get_end` function, but the point stil stands:
    // we need to get to the end
    ++size_;
}

如果我们无论如何都要找到结尾，我们可以直接存储它——反正它比大小更有用。

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

Why the libc++ std::vector internally keeps three pointers instead of one pointer and two sizes?

c++

vector

stl

libc++