/重学C++：标准库类模板Vector

常见的坑与用法

1. vector的默认初始化是否合法取决于vector内对象所属的类是否要求显式初始化。

2. 使用()和{}对vector执行初始化含义不同。

   using std::vector;
   
   vector<int> v1{10};    // 存储1个int对象，值为10
   vector<int> v2(10);    // 存储10个int对象，值为0
   
   vector<int> v3(10, 1); // 存储10个int对象，值都是1
   vector<int> v4{10, 1}; // 存储2个int对象，值分别是10和1
   

3. 使用{}执行列表初始化时按照顺序遵守 2 个守则：

   1. 如果{}内容可以用于初始化，则采用{}默认的初始化含义。

   2. 如果{}中的内容无法用{}默认的初始化含义做出解释，则会按照()的初始化含义去解释{}。

      using std::vector;
      using std::string;
      
      vector<string> v1{"hi"};      // 存储1个值为hi的string对象
      vector<string> v2{10};        // 存储10个值为空的string对象
      vector<string> v3{10, "hi"};  // 存储10个值为hi的string对象
      

4. 与string相同，vector也有size_type作为其size()的返回值类型。

   但是使用时必须首先指定vector由哪个类型定义。

   std::vector<int>::size_type a; // 正确
   std::vector::size_type a;      // 错误
   

5. 只有vector内元素的类型可以被比较时才能做比较运算，对于自定义类型需要手动定义运算符重载。

6. 增加vector中的元素只能使用push_back() or emplace_back()，而不能使用对下标赋值的方式。

   push_back() 和 emplace_back() 的区别来自于两者的函数签名不同：

   • emplace_back() 支持通过传入参数在 vector 内部原地构造对象，因而只会调用构造函数 1 次；
   • push_back() 不支持，所以至少会调用 2 次构造函数和 1 次析构函数（临时对象的构造函数和析构函数、vector 内对象的拷贝或移动构造函数）；
   • 两者都支持传入右值引用作为参数，因而可以使用 push_back(std::move(obj)) or emplace_back(std::move(obj)) 来避免对象拷贝操作，从而改善性能。

7. 可以使用 vector 来模拟 stack 的行为：

   • stack.pop() <=> vector.pop_back()
   • stack.top() <=> vector.back()
   • stack.push() <=> vector.push_back() or vector.emplace_back()

8. vector 在达到容量上限时会触发扩容操作，GCC 的扩容倍数是 2 ，MSVC 的是 1.5.

   • 为什么使用倍数扩容而不是等长扩容？

     因为倍数扩容的单次操作平均时间复杂度是 O(1) （等比数列求和后平均，与扩容倍数相关）。

     等长扩容的是O(n) （等差数列求和后平均，与扩容次数相关）。

   • 为什么使用 1.5 倍或 2 倍而不使用 3 倍、4 倍？

     因为扩容的本质其实就是申请新内存空间、拷贝元素、释放旧内存空间。

     一个直观的想法是新申请内存空间时可以重复利用旧内存空间。

     • 对于 2 倍扩容的情况：1 2 4 8 16 32 ...，1+2<4, 1+2+4<8, 1+2+4+8<16，这种情况下之前释放的内存空间无法满足扩容的需求。

     • 对于 1.5 倍扩容的情况：1 2 3 4 6 9 13 ...，1+2>=3, 2+3>=4, 4+6>=9, 6+9>=13，这种情况下旧的内存空间可以满足扩容需求，因而存在内存重复利用的可能性。

       所以 1.5 倍扩容可以更好的实现对内存的重复利用。

       理论最优扩容满足的条件是 f(n-1)+f(n-2)=f(n) 即斐波那契数列，最优扩容因子通过极限可以求出为黄金分割率：1.618.

   • Linux 为什么使用 2 倍扩容？

     Linux 下主要使用 glibc 的 ptmalloc 来进行用户空间申请的，如果 malloc 的空间小于 128KB，其内部通过 brk()来扩张，如果大于 128KB，通过 mmap 将内存映射到进程地址空间。

     Linux 引入了伙伴系统为内核提供了一种用于分配连续的页而建立的一种高效的分配策略，对固定分区和动态分区方式的折中。固定分区存在内部碎片，动态分区存在外部碎片，而且动态分区回收时的合并以及分配时的切片是比较耗时的。伙伴系统是将整个内存区域构建成基本大小 basicSize 的 1 倍、2 倍、4 倍、8 倍、16 倍等，即要求内存空间分区链均对应 2 的整次幂倍大小的空间，整齐划一，有规律的而不是乱糟糟的。

     在分配和释放空间时，可以通过 log2(request/basicSize)向上取整的哈希算法快速找到对应内存块。通过伙伴系统管理空闲分区的了解，可以看到在伙伴系统中的每条空闲分区链中挂的都是 2^i 的页面大小，通过哈希思想进行空间分配与合并，非常高效。估计可能是这个原因 SGI-STL 选择以 2 倍方式进行扩容。

必须理解的点

1. vector是类模板而非类型。
2. vector中只能容纳对象，不能容纳引用。
3. vector对象能高效增长，增加vector中的元素需要使用 push_back() 或 emplace_back() 成员函数。
4. vector的成员函数（empty(), size()）和各种运算符（赋值、关系、下标）的操作使用方法和规则基本同string。

NOTE

1. 不需要在创建vector时确定其中的元素及其大小，但是如果在创建时就已经知道容器中需要容纳的元素个数就可以直接指定vector的大小。
2. 在循环体内部包含向vector对象添加元素的操作时，不应该使用foreach循环。