STL矢量的实现

Question

我想知道STL是如何std::vector实现的.

确切地说,STL向量是否包含一个对象表或一个指向对象的表？

在实际实现中:最好std::vector<char>是大小是什么10^8,或者有一个数组char？

第一个选项有明显的优点:迭代在每个其他容器中,已知大小,自动内存管理,很难做一些真正错误的事情.

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

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

Type 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

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

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

(它还需要存储一个分配器;但通常,这是无状态的,一个不错的实现将使用"空基类优化"来确保它在这种情况下不占用空间).

如果您管理自己的动态阵列,则至少需要其中两个; 因此使用向量的额外成本是单个指针.

如果您不需要动态分配,那么自动数组(或者std::array,如果您想要更多STLy)将更有效:它不会涉及任何堆分配或任何额外存储.但是,只有在编译时知道大小时才有可能,并且存在大型数组可能溢出堆栈的危险.