其中之一与其他不同：为什么 std::vector::size 在所有主要标准库实现中都根据指针来实现？

Question

在 godbolt 上随机播放（就像一个人那样）我发现 std::vector::size() 被实现为指针的差异，而我期望它只是 return 一个 class 数据成员。 std::vector::capacity() 类似。奇怪的是，所有其他标准容器（std::deque 除外）都将大小存储为数据成员。即使在 libstdc++ 和 Microsoft 的 STL 上 std::string 也将其大小存储为数据成员（在 libc++ 上，大小信息存储似乎使用 SSO 信息进行了优化，但大小仍然是显式存储的，而不是作为指针的差异计算的）。

Here is the godbolt link 包含所有容器在 libc++、libstdc++ 和微软的 STL 上的大小。部分摘录如下：

f_vec4:  //std::vector<std::int32_t>
        mov     rax, qword ptr [rdi + 8]
        sub     rax, qword ptr [rdi]
        sar     rax, 2
        ret
f_vec8:  // std::vector<int64_t>
        mov     rax, qword ptr [rdi + 8]
        sub     rax, qword ptr [rdi]
        sar     rax, 3
        ret

f_list:
        mov     rax, QWORD PTR [rdi+16]
        ret

f_map:
        mov     rax, QWORD PTR [rdi+40]
        ret

为什么 std::vector::size 唯一的容器大小实现为指针差异，而所有其他容器都存储它们的大小？标准中有什么吗？是优化吗？

Answer 1

在这里回答：

所有其他容器都需要存储大小，因为它们不会将其元素保存在连续的内存区域中（list、(unordered)_(multi)map、(unordered)_(multi)set）。 std::string 确实将元素存储在数组中，但由于 SSO（小字符串优化），该数组可以动态分配或包含在结构中，因此最好的策略是存储其大小。

std::vector 是唯一可以选择存储指向开始和结束（以及容量结束）的指针的容器。为什么所有标准库都使用开始结束而不是开始大小实现 std::vector 我不知道。

Answer 2

why is std::vector::size implemented in terms of pointers on all major standard library implementations?

因为可以用指针减法来实现。而且因为标准库实现者选择这样做。

Is is something in the standard?

没有。我确信将尺寸存储为成员是符合标准的。

What is weird is that all other standard containers (except std::deque) store the size as a data member.

这不足为奇。除了数组之外，没有其他数据结构可以使用指针作为迭代器。

std::string 被实现为一个数组，所以它也可以使用指针减法。如果没有这样做，那是因为实施者选择不这样做。这可能是也可能不是由于与小字符串优化相关的便利性。

Answer 3

除了复杂性之外，size() 实施没有严格的要求 - 它必须是恒定的。因此，人们可能会推测 std::vector 只是利用了这样一个事实，即它的元素存储是连续的，因为实现者选择了 and/or 潜在的基准（尽管很难想象这种微小变化的影响）。直接从标准： https://timsong-cpp.github.io/cppwp/container.requirements.general#4

|----------------------------------------------------------------------|
| Expression | Return type | Operational | Assertion/note | Complexity |
|----------------------------------------------------------------------|
| a.size()   | size_type   | distance(   |                |            |
|            |             |   a.begin(),|                |  constant  |
|            |             |   a.end())  |                |            |
|----------------------------------------------------------------------|

如果我没记错的话，它并不总是那样，有一段时间 gcc 的 std::list::size() 具有线性复杂度（在 C++ 之前是 11 倍）。

Answer 4

通常你会这样做：

std::vector<int> vec;
std::some_algorithm(vec.begin(), vec.end(), ...);

现在假设 vector 正在存储向量的大小。那么我们假设它是这样实现的：

// in #include <vector>
namespace std {
template<typename T>
class vector {
    T *_Begin; // pointer to beginning of allocated space
    size_t _Size; // size of allocated space
    T* begin() { return _Begin; }
    T* end() { return _Begin + _Size; }
 };
...
}

然后 std::some_algorithm 可以内联为：

std::some_algorithm(vec._Begin, vec._Begin + vec._Size, ...);

如果我们优先考虑对象大小，我们会选择存储结束指针或向量中的对象计数。当我们存储对象的计数时，我们必须通过加法计算end()指针，我们可以立即return size()。当我们存储结束指针时，end() 将只是一个简单的 return，而 size() 必须根据指针差异和除以对象大小来计算。

很可能库实现者选择优化 end() 而不是 size() 的计算。因为 C++ 算法基于采用两个指针 - 开始和结束迭代器，所以（对我而言）假设结束指针将比大小更频繁地使用是合理的。

其中之一与其他不同：为什么 std::vector::size 在所有主要标准库实现中都根据指针来实现？

One of them is not like the others: why is std::vector::size implemented in terms of pointers on all major standard library implementations?

c++

c++-standard-library

libstdc++

libc++