vector深度探索

声明：本文中所有图件都来自B站侯捷老师授课视频

vecctor 底层实现原理

图1. GNU2.9 实现的容器vector

• vector 的内存是动态增长的，vector 最重要的三个成员变量为 三个迭代器： start, finish, end_of_storage 。start 指向vector第一个元素， finish 指向最后一个元素的下一个地址，end_of_storage指向 vector 内存空间最后一个地址的下一个地址。vector对象 的大小 就是 这三个指针（vector的迭代器就是指针）的总大小，在32位的计算机上，一个指针的大小为4个字节，所以是12个字节,sizeof(vector)=12。而 vector 的一些成员函数如图1，都是通过以上三个迭代器来实现的。
• []操作符重载，所有容器，只要是连续内存空间，就会提供中括号 [] 来做元素访问。

内存增长机制 与 push_back

• vector 的内存增长是成倍增长的，比如 vector 当前分配空间为 8， 当第 9 个元素 放进来时，vector 会 另外找一块大小为 16 的内存空间，将 已有的 8 个元素 从 原来的 内存地址上 拷贝过去，并插入第9个元素，并且将原来的内存空间释放掉，这就是 push_back 做的事情，可见，在向 vector 添加数据的过程中 需要执行大量的 拷贝函数和析构函数。
• 图 2 和图 3 是 push_back 的实现代码。
  
  图2. 容器 vector 的 push_back（上）
  
  图2. 容器 vector 的 push_back（下）

vector 的迭代器

• vector 的迭代器就是指针，实际上内存空间连续的容器的迭代器都是指针。
• 如图4， 从迭代器的设计原则一文中知道 萃取机（是个结构体），通过模版特化，可以识别指针，常量指针和class。当识别到容器的迭代器是指针时，意味着容器的内存空间连续，所以其 迭代器类型 iterator_category 为 随机访问迭代器。
  
  图4. vertor’s iterator