c++ - STL vector 的实现

Question

我想知道 STL 怎么样 std::vector实现。

确切地说，STL vector 中保存的是对象表还是对象指针表？

在实际实现中:std::vector<char> 是否更好？大小约为 10^8 , 或者有一个 char 的数组？

第一个选项有明显的优点:像在所有其他容器中一样进行迭代、已知大小、自动内存管理、很难做真正错误的事情。

第二个选项可能使用的空间少九倍(指针是 64 位，其中 char 是 8 位)，但代价是上面列出的所有这些舒适的方法。

我看过 /usr/include/c++/4.8.2/bits/STL_vector.h 看到了push_back()实现如下，但即使检查 alloc_traits.h 也让我不知道它是如何真正完成的。

输入 char仅用于表明指针的大小与保存的值大小相比很重要。

我正在使用 C++11。

void
push_back(const value_type& __x)
{
     if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage)
     {
         _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish,
                                  __x);
         ++this->_M_impl._M_finish;
     }
     else
#if __cplusplus >= 201103L
     _M_emplace_back_aux(__x);
#else
     _M_insert_aux(end(), __x);
#endif
}

Answer 1

vector 管理单个连续的对象数组，因此它不需要指向每个元素的指针。它只需要:

• 指向数组开头的指针
• 一个指针(或索引)，标记所用元素的结尾(即大小)
• 标记已分配存储(即容量)结束的指针(或索引)

(它还需要存储一个分配器；但通常，这是无状态的，并且体面的实现将使用“空基类优化”来确保它在这种情况下不占用空间)。

如果您管理自己的动态数组，则至少需要其中两个；所以使用 vector 的额外成本是单个指针。

如果您不需要动态分配，那么自动数组(或 std::array，如果您想要更多 STLy)会更高效:它不会涉及任何堆分配，或任何额外的存储空间。但是，这只有在编译时已知大小的情况下才有可能，并且存在大数组可能溢出堆栈的危险。