vector
目前用的最多的容器，没有之一。非常有必要更多地了解它。vector 是动态数组，数组的容量不是固定的。它的原理很简单，当数组的元素数量达到了容量时，插入新的元素会发生扩容。扩容会开一块新的内存出来，然后将元素复制过去，扩容的大小为 1.5 倍。
接口
vector 提供了哪些接口，看文档即可。
文档：https://www.cplusplus.com/reference/vector/vector/
注意事项：
- begin/end 是前闭后开区间，即 begin 指向首元素，end 指向尾元素的后一个位置。
- 注意区分 size capacity resize reverse
- resize 是否扩容取决于是否大于 capacity，大于则扩容
- insert 是插入到 “迭代器” 之前，用的是迭代器
- 效率上微小的区别：emplace vs. insert, push_back vs. emplace_back
问与答
问：扩容的算法是怎么样子的？
答：初始情况下大小为 0，传入的 _Newsize 为 1，于是第一次扩容大小变为 1。后续就按照这个公式计算下一次扩容时候的大小，每次扩容为 1.5 倍。
size_type _Calculate_growth(const size_type _Newsize) const {
// given _Oldcapacity and _Newsize, calculate geometric growth
const size_type _Oldcapacity = capacity();
const auto _Max = max_size();
if (_Oldcapacity > _Max - _Oldcapacity / 2) {
return _Max; // geometric growth would overflow
}
const size_type _Geometric = _Oldcapacity + _Oldcapacity / 2;
if (_Geometric < _Newsize) {
return _Newsize; // geometric growth would be insufficient
}
return _Geometric; // geometric growth is sufficient
}
问：扩容的时候，元素是如何动的？
首先在 C++11 之后，“移动语义” 肯定要安排上吧，毕竟原来的数组是要丢弃了的，所以直接移动就好了。接下来，vector 的内存管理归根结底还是由 allocator 来负责，所以最终调用的还是要走到 allocator.construct 这个方法去。此外有个细节：如果 vector 的模板参数有 move constructor，那么就会调用；如果没有，那么调用 copy constructor。如果 copy / move 都被 delete 了，那么编译时会报错。
问：push_back 和 emplace_back 之间的区别？
答：可能会多一次移动构造函数的调用，你想想看这两个函数的参数有什么区别？
empalce_back使用可变参数模型，可以接收参数，用这些参数直接在 vector 的尾部构造元素，从而减少了一次移动构造的开销。push_back先构造出一个临时对象，后会进行移动构造。push_back内部的实现其实只是调用了emplace_back，所以绝大多数情况是没有区别的。除了emplace_back可以直接在对应的位置创建构造器。这启发我们，如果要构造临时对象，那么用 emplace_back。其他则没有区别。
// push_back 其实就是调用 emplace_back
void push_back(const _Ty& _Val) { // insert element at end, provide strong guarantee
emplace_back(_Val);
}
void push_back(_Ty&& _Val) { // insert by moving into element at end, provide strong guarantee
emplace_back(_STD move(_Val));
}
// emplace_back 内部实现，可以直接在数组上构建元素
template <class... _Valty>
decltype(auto) _Emplace_back_with_unused_capacity(_Valty&&... _Val) {
// insert by perfectly forwarding into element at end, provide strong guarantee
auto& _My_data = _Mypair._Myval2;
pointer& _Mylast = _My_data._Mylast;
_STL_INTERNAL_CHECK(_Mylast != _My_data._Myend); // check that we have unused capacity
// 在元素尾部构造元素
_Alty_traits::construct(_Getal(), _Unfancy(_Mylast), _STD forward<_Valty>(_Val)...);
_Orphan_range(_Mylast, _Mylast);
_Ty& _Result = *_Mylast;
++_Mylast;
return _Result;
}
问：vector 为什么不给用引用类型？
答：因为不允许使用 “指向引用的指针”。说到底 vector 总是需要分配内存的，用到了 allocator。如果 vector 的泛型参数是引用类型，那么 allocator 内部的就有一个 “指向引用的指针”。下面报的错误大部分来自于 allocator，引用类型在模板实例化的时候出错了。更进一步地说，其实只要用了 allocator 的容器，就是不能用引用类型。注意区分，“指向指针的引用” 这个又是可以的。至于为什么不能有 “指向引用的指针”，我很赞同 [1] 的回答，因为引用本身是不能修改 “指向” 的指针，那么指向它的指针就没有意义，标准委员会说不能，那就不能吧。核心就是要理解到引用和指针的区别：引用的指向是不可变的了。
问：迭代器失效的情况？
答：扩容，erase。比较常犯的错误是，一边遍历，一边删除，删除之后迭代器是会失效的。什么是失效呢？在 MSVC 里面，iterator 变成了空指针，在 GCC 里面，iterator 里面存储的指针仍然指向原地址（比如 insert 了之后，iterator 仍然指向 insert 之前的位置）。所以失效的意思是，不满足用户想要的语义。假如用户知道 gcc 那样的实现，就是要那么用，那就算不上失效了hhh
以 MSVC 的代码为例子看看吧。我们可以找到 earse 的代码，其中有一段会调用下面的 _Orphan_range 来使到 first 和 last 之间全部置空。
// 使某个范围内的 iterator 失效
void _Orphan_range(pointer _First, pointer _Last) const { // orphan iterators within specified (inclusive) range
#if _ITERATOR_DEBUG_LEVEL == 2
_Lockit _Lock(_LOCK_DEBUG);
_Iterator_base12** _Pnext = &_Mypair._Myval2._Myproxy->_Myfirstiter;
while (*_Pnext) {
const auto _Pnextptr = static_cast<const_iterator&>(**_Pnext)._Ptr;
if (_Pnextptr < _First || _Last < _Pnextptr) { // skip the iterator
_Pnext = &(*_Pnext)->_Mynextiter;
} else { // orphan the iterator
// _Myproxy 是 iterator 内部存储的数据结构, erase 会将当前到最后置空
(*_Pnext)->_Myproxy = nullptr;
*_Pnext = (*_Pnext)->_Mynextiter;
}
}
#else // ^^^ _ITERATOR_DEBUG_LEVEL == 2 ^^^ // vvv _ITERATOR_DEBUG_LEVEL != 2 vvv
(void) _First;
(void) _Last;
#endif // _ITERATOR_DEBUG_LEVEL == 2
}
// iterator 重载了 * 操作符, 通过 _Myproxy -> _Mycont -> _Myfirst 来判断是否在范围，是否已经失效
_NODISCARD reference operator*() const noexcept {
#if _ITERATOR_DEBUG_LEVEL != 0
const auto _Mycont = static_cast<const _Myvec*>(this->_Getcont());
_STL_VERIFY(_Ptr, "can't dereference value-initialized vector iterator");
_STL_VERIFY(
_Mycont->_Myfirst <= _Ptr && _Ptr < _Mycont->_Mylast, "can't dereference out of range vector iterator");
#endif // _ITERATOR_DEBUG_LEVEL != 0
return *_Ptr;
}