C++?STL標準庫std::vector擴容時進行深復制原因詳解

更新時間：2022年08月15日 14:42:57 作者：fl2011sx

我們知道，std::vector之所以可以動態(tài)擴容，同時還可以保持順序存儲，主要取決于其擴容復制的機制。當容量滿時，會重新劃分一片更大的內存區(qū)域，然后將所有的元素拷貝過去

引子

但是筆者卻發(fā)現(xiàn)了一個奇怪的現(xiàn)象，std::vector擴容時，對其中的元素竟然進行的是深復制。請看示例代碼：

#include <iostream>
#include <vector>
struct Test {
    Test() {std::cout << "Test" << std::endl;}
    ~Test() {std::cout << "~Test" << std::endl;}
    Test(const Test &) {std::cout << "Test copy" << std::endl;}
    Test(Test &&) {std::cout << "Test move" << std::endl;}
};
int main(int argc, const char *argv[]) {
    std::vector<Test> ve;
    ve.emplace_back();
    ve.emplace_back();
    ve.emplace_back();
    return 0;
}

打印結果如下：

Test
Test
Test copy
~Test
Test
Test copy
Test copy
~Test
~Test
~Test
~Test
~Test

由于我們沒有調用reverse函數(shù)，所以默認只分配了一個元素的大小。第一次emplace_back時，僅進行了一次普通構造。第二次emplace_back時，就需要進行擴容，然后把第一個元素拷貝過去，再釋放原來的對象。所以這里除了有一次新的構造以外，還有一次復制和釋放。后面的行為類似，不再贅述，

但關鍵問題就在于，Test類明明實現(xiàn)了移動構造（淺復制），可這里竟然調用了拷貝構造（深復制）。

如果vector擴容無腦調用拷貝構造，那么這個對象如果含有很多外鏈的成員（比如說指向buffer的指針、指向其他對象的指針等），調用拷貝構造就意味著要把這些鏈接的對象全部都重新構造一遍。這對于vector自身擴容來說，顯然是沒有必要的，會極度浪費內存空間。

查找原因

基于上述理由，我認為STL的開發(fā)者不可能連這個問題都考慮不到，但想不通為什么我明明實現(xiàn)了移動構造，卻不能調用。

帶著這樣的疑問我去研讀了STL的源碼（GNU版本），在vector擴容時，會調用_M_realloc_insert函數(shù)，該函數(shù)在vector.tcc文件中實現(xiàn)。在這個函數(shù)里面對已有元素進行拷貝的時候，看到了類似這樣的代碼：

__new_finish
		= std::__uninitialized_move_if_noexcept_a
		(__old_start, __position.base(),
		 __new_start, _M_get_Tp_allocator());
	      ++__new_finish;

有趣的就是這個__uninitialized_move_if_noexcept_a，我們找到這個函數(shù)的實現(xiàn)：

template<typename _InputIterator, typename _ForwardIterator,
	   typename _Allocator>
    inline _ForwardIterator
    __uninitialized_move_if_noexcept_a(_InputIterator __first,
				       _InputIterator __last,
				       _ForwardIterator __result,
				       _Allocator& __alloc)
    {
      return std::__uninitialized_copy_a
	(_GLIBCXX_MAKE_MOVE_IF_NOEXCEPT_ITERATOR(__first),
	 _GLIBCXX_MAKE_MOVE_IF_NOEXCEPT_ITERATOR(__last), __result, __alloc);
    }

再看一下_GLIBCXX_MAKE_MOVE_IF_NOEXCEPT_ITERATOR的實現(xiàn)

#if __cplusplus >= 201103L
#define _GLIBCXX_MAKE_MOVE_IF_NOEXCEPT_ITERATOR(_Iter) std::__make_move_if_noexcept_iterator(_Iter)
#else
#define _GLIBCXX_MAKE_MOVE_IF_NOEXCEPT_ITERATOR(_Iter) (_Iter)
#endif // C++11

也就是說，在C++11以前，這玩意就是對象本身（畢竟C++11以前還沒有移動構造），而在C++11以后被定義成了__make_move_if_noexcept_iterator，繼續(xù)查看其定義。

template<typename _Iterator, typename _ReturnType
    = typename conditional<__move_if_noexcept_cond
      <typename iterator_traits<_Iterator>::value_type>::value,
                _Iterator, move_iterator<_Iterator>>::type>
    inline _GLIBCXX17_CONSTEXPR _ReturnType
    __make_move_if_noexcept_iterator(_Iterator __i)
    { return _ReturnType(__i); }

這里用了一個conditional，來判斷這個迭代器的類型，如果__move_if_noexcept_cond為真，就取迭代器本身，否則就取移動迭代器。看起來問題就在這里了，之前我們的例程中的Test一定就是符合了這個__move_if_noexcept_cond，導致用了原始迭代器。

繼續(xù)深挖這個__move_if_noexcept_cond，看到這樣的代碼：

template<typename _Tp>
    struct __move_if_noexcept_cond
    : public __and_<__not_<is_nothrow_move_constructible<_Tp>>,
                    is_copy_constructible<_Tp>>::type { };

也就是說，如果一個類，不存在不會拋出異常的移動構造函數(shù)并且可拷貝，那么就為真。

Test類顯然符合，所以vector<Test>在復制時用了普通的迭代器進行了遍歷，自然就會調用拷貝構造函數(shù)進行復制了。

解決方法

所以，我們需要讓Test不符合__move_if_noexcept_cond的條件，也就是這里要將移動構造函數(shù)聲明為noexcept表示它不會拋出異常，這樣vector<Test>在復制時就會使用移動迭代器（就是會包裝一層std::move），從而觸發(fā)移動構造。

順道我們也看一眼移動迭代器的原理:

template<typename _Iterator>
class move_iterator {
    _Iterator _M_current;
    // ...
  public:
    using iterator_type = _Iterator;
	explicit _GLIBCXX17_CONSTEXPR
      	move_iterator(iterator_type __i)
      	: _M_current(std::move(__i)) { }
    // ...
}

確實調用了std::move，證明我們的思路沒錯。

所以，修改Test代碼，實現(xiàn)noexcept移動構造：

struct Test {
    long a, b, c, d;
    Test() {std::cout << "Test" << std::endl;}
    ~Test() {std::cout << "~Test" << std::endl;}
    Test(const Test &) {std::cout << "Test copy" << std::endl;}
    Test(Test &&) noexcept {std::cout << "Test move" << std::endl;}
};
int main(int argc, const char *argv[]) {
    std::vector<Test> ve;
    ve.emplace_back();
    ve.emplace_back();
    ve.emplace_back();
    return 0;
}

打印結果如下：