你知道vector底層是如何實現的嗎？

vector底層使用動態數組來存儲元素對象，同時使用size和capacity記錄當前元素的數量和當前動態數組的容量。如果持續的push_back(emplace_back)元素，當size大于capacity時，需要開辟一塊更大的動態數組，并把舊動態數組上的元素搬移到當前動態數組，然后銷毀舊的動態數組。

你知道新開辟的動態數組的容量是就數組的多少倍比較合適？

這個值在不同的編譯器上不是固定的。MSVC 是1.5，而GCC是2。

有沒有什么好的辦法提升vector連續插入效率？

如果知道數據的大概量，我們可以使用reserve方法直接為vector擴容這個量級。這樣在后續的數據插入時就不會因為頻繁的capacity被用盡而導致的多次的數據搬移，從而提升vector插入效率。

push_back和emplace_back有什么區別？

兩者都可以在容器尾部插入元素。在GCC中，如果插入的元素是右值，兩者都會move元素到容器。如果是左值，兩者都會copy元素到容器。唯一不同的一點是，當C++版本高于C++17時，emplace_back返回當前插入的值的引用，而push_back返回void。

erase和remove有什么區別？

erase屬于成員函數，erase刪除了元素，remove屬于算法庫函數，而remove只會把元素移動到尾部。

哪些情況下迭代器會失效？

迭代器失效主要有兩種情況引起：

1.插入數據。由于插入數據可能導致數據搬移（size > capacity）,所以迭代器失效。

2.刪除數據。當使用erase刪除數據時，被刪除數據后面的數據依次向前移一位。這會導致被刪除數據之后的迭代器失效。

如何快速的清空vector容器并釋放vector容器所占用的內存？

有兩種方法：

• 第一種，使用clear方法清空所有元素。然后使用shrink_to_fit方法把capacity和size（0）對齊，達到釋放內存的作用；
• 第二種，使用swap方法；

你知道vector<bool>是如何實現的嗎？

vector<bool>的實現和其他實現容器的實現不一致。**每個元素被當作一個位而不是一個字節存儲。**這導致我們不能直接訪問該元素，也無法對每個元素取地址（8個元素可能在同一個字節中存儲）。所以不建議使用vector<bool>，必要時可以使用std::bitset替代。

介紹三個和大小、容量與內存相關的函數：

• 一個是_M_shrink_to_fit函數，可以使用這個函數將_M_finish和_M_end_of_storage之間的內存釋放掉，正好使分配的內存大小滿足vector中元素量。
• 一個是reserve函數，可以使用這個函數控制整個vector容量的作用，避免重新分配內存，例如我們如果知道元素最多有80個，我們就可以使用v.reserve(80)來一次分配80個內存。但是值得注意的是這個函數不能用來縮減容量
• 一個是resize函數，這個函數實際就是改變_M_start和_M_finish之間的相對位置，改變的是元素的個數，如果resize(n)的n小于當前個數就刪除元素，如果大于就追加默認函數生成的對象。

vector是怎么變長的

typename vector<_Tp, _Alloc>::iterator
vector<_Tp, _Alloc>::insert(iterator __position, const value_type& __x)
{const size_type __n = __position – begin();//如果還有空位，插入到最后一個位置，相當于push_backif (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage&& __position == end()){_Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish, __x);++this->_M_impl._M_finish;}else{_M_insert_aux(__position, __x);}return iterator(this->_M_impl._M_start + __n);
}

當容量不足的時候，就是_M_insert_aux函數發揮的時候，進行容量的擴展，實現如下：

template<typename _Tp, typename _Alloc>
void vector<_Tp, _Alloc>::_M_insert_aux(iterator __position, const _Tp& __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,_GLIBCXX_MOVE(*(this->_M_impl._M_finish- 1)));++this->_M_impl._M_finish;//__position后的元素依次向后移動一個位置_GLIBCXX_MOVE_BACKWARD3(__position.base(),this->_M_impl._M_finish - 2,this->_M_impl._M_finish – 1);//目標地址賦值*__position = _Tp(std::forward<_Args>(__args)...);}else{//內存加倍const size_type __len =_M_check_len(size_type(1), "vector::_M_insert_aux");const size_type __elems_before = __position - begin();pointer __new_start(this->_M_allocate(__len));pointer __new_finish(__new_start);__try{//給position位置賦值_Alloc_traits::construct(this->_M_impl,__new_start + __elems_before,std::forward<_Args>(__args)...);__x);__new_finish = 0;//拷貝position位置前元素__new_finish = std::__uninitialized_move_if_noexcept_a(this->_M_impl._M_start, __position.base(),__new_start, _M_get_Tp_allocator());++__new_finish;//拷貝position位置后元素__new_finish= std::__uninitialized_move_if_noexcept_a(__position.base(), this->_M_impl._M_finish,__new_finish, _M_get_Tp_allocator());}__catch(...){if (!__new_finish)_Alloc_traits::destroy(this->_M_impl,__new_start + __elems_before);elsestd::_Destroy(__new_start, __new_finish, _M_get_Tp_allocator());_M_deallocate(__new_start, __len);__throw_exception_again;}//析構原vector所有元素std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,_M_get_Tp_allocator());//釋放原vector內存空間_M_deallocate(this->_M_impl._M_start,this->_M_impl._M_end_of_storage，this->_M_impl._M_start);//vector內存地址指向新空間this->_M_impl._M_start = __new_start;this->_M_impl._M_finish = __new_finish;this->_M_impl._M_end_of_storage = __new_start + __len;}
}

其中_M_check_len函數的實現如下：

size_type
_M_check_len(size_type __n, const char* __s) const
{if (max_size() - size() < __n)__throw_length_error(__N(__s));//如果n小于當前size，內存加倍，否則內存增長n。const size_type __len = size() + std::max(size(), __n);return (__len < size() || __len > max_size()) ? max_size() : __len;
}

可以發現vector內存分配策略并不是簡單的加倍，如果n小于當前size，內存加倍，否則內存增長n。

接著我們講一下vector怎么刪除元素。vector刪除元素的函數有以下幾個：

// 刪除某個位置上的元素，返回下一個元素的位置
erase(const_iterator __position)
// 刪除一個區間內的所有元素
erase(const_iterator __first, const_iterator __last)
// 清空所有元素
clear()
// 借助remove刪除與val相等的所有元素
erase(remove(begin(), end(), val), end());
// 借助remove_if刪除滿足某個條件的所有元素
erase(remove_if(begin(), end(), <lambda>), end());

vector使用陷阱

• vector的函數除了at函數之外，都不拋出異常，如果要取元素的話，均需要判斷是否越界，不然會引發未知的錯誤；

• vector的內存占用空間只增不減，在使用vector時要及時清除元素和回收內存，尤其是在static對象中使用vector保存元素時。vector提供的刪除元素的成員函數，只是調用元素的析構函數析構掉元素，已經分配的內存并不會收回；

• 所有內存空間是在vector析構時候才能被系統回收。empty()用來檢測容器是否為空的，clear()可以清空所有元素。但是即使clear()，vector所占用的內存空間依然如故，無法保證內存的回收。

• 如果需要空間動態縮小，可以考慮使用deque。如果非vector不可，可以用swap()來幫助你釋放內存。具體方法如下：

• 如果vector中存放的是指針，那么當vector銷毀的時候，這些指針指向的對象不會被銷毀，所占用的內存也不會被釋放。