hoge diary - March 7, 2006

hoge diary - February 6, 2006 - std::vector の実装 の続きです．

さて，私は前回memcpy() 等を使ってメモリイメージを丸ごとコピーしているわけではないことがわかりましたが... コピーコンストラクタが 3 回ではなく 4 回呼ばれています．vector の最初の要素は 2 回のコンストラクタ呼び出しによって初期化されているのでしょうか．と書いていましたが，この謎は std::vector の定義を見れば済むことでした(某さんの的確なツッコミに感謝します)．

というわけで，定義を見てみましょう．今回使用するのは，GNU g++-3.4.5 に含まれている STL のヘッダです．

ヘッダファイル vector を見ると... bits/stl_vector.h をインクルードしています．stl_vector.h を見ると，std::vector の定義が見つかりました．

template<typename _Tp, typename _Alloc = allocator<_Tp> >
  class vector : protected _Vector_base<_Tp, _Alloc>
  {
    ...(途中省略)...

    void
    resize(size_type __new_size, const value_type& __x)
    {
      if (__new_size < size())
        erase(begin() + __new_size, end());
      else
        insert(end(), __new_size - size(), __x);
    }

    void
    insert(iterator __position, size_type __n, const value_type& __x)
    { _M_fill_insert(__position, __n, __x); }

    ...(途中省略)...

    void
    _M_fill_insert(iterator __pos, size_type __n, const value_type& __x);

    ...(途中省略)...
 };

resize() が insert() を呼び，insert() が _M_fill_insert() なるものを呼んでおりますが，その定義は，bits/vector.tcc に以下の通り書かれています．強調箇所が今回の要点(コンストラクタの呼び出しにかかわる箇所)です．なお，左端に行番号を付けて示しています．

 1  template<typename _Tp, typename _Alloc>
 2    void
 3    vector<_Tp,_Alloc>::
 4    _M_fill_insert(iterator __position, size_type __n, const value_type& __x)
 5    {
 6      if (__n != 0)      // 挿入する要素が無ければ何もする必要はない
 7      {
 8        // 既に n 個の領域を追加するのに十分なメモリを確保してあるかを調べる
 9        if (size_type(this->_M_impl._M_end_of_storage - this->_M_impl._M_finish) >= __n)
10        {
11          // 十分なメモリが確保されているので，要素を追加するだけ．
12  
13          value_type __x_copy = __x;      // ここでコピーコンストラクタがまず最初に 1 回呼ばれる．
14          const size_type __elems_after = end() - __position;
15          iterator __old_finish(this->_M_impl._M_finish);
16          // 挿入地点以後の要素を後方にコピーするが，その前にコピー元とコピー先のメモリ領域が
17          // 重なるかどうかをチェックする．
18          if (__elems_after > __n)
19          {
20            // 重なっているので，末尾の要素から順番にコピーする．
21  
22            std::uninitialized_copy(this->_M_impl._M_finish - __n,
23                                    this->_M_impl._M_finish,
24                                    this->_M_impl._M_finish);
25            this->_M_impl._M_finish += __n;
26            std::copy_backward(__position, __old_finish - __n, __old_finish);
27            std::fill(__position, __position + __n, __x_copy);
28          }
29          else
30          {
31            // 要素は重ならないので，前から順にコピーしてよい．
32  
33            std::uninitialized_fill_n(this->_M_impl._M_finish,
34                                      __n - __elems_after,
35                                      __x_copy);
36            this->_M_impl._M_finish += __n - __elems_after;
37            std::uninitialized_copy(__position, __old_finish, this->_M_impl._M_finish);
38            this->_M_impl._M_finish += __elems_after;
39            std::fill(__position, __old_finish, __x_copy);
40          }
41        }
42        else
43        {
44          // 十分なメモリが確保されていないので，確保する
45  
46          const size_type __old_size = size();
47          const size_type __len = __old_size + std::max(__old_size, __n);
48          iterator __new_start(this->_M_allocate(__len));
49          iterator __new_finish(__new_start);
50          try
51          {
52            // 言語仕様より，std::vector はメモリの連続性を保証する必要がある．
53            // したがって，
54            //   1. 挿入位置より前の要素をコピー
55            //   2. 今回追加する n 個の領域を初期化
56            //   3. 挿入位置より後ろの要素をコピー
57            // の流れをたどる．
58  
59            __new_finish = std::uninitialized_copy(begin(), __position,
60                                                   __new_start);
61            __new_finish = std::uninitialized_fill_n(__new_finish, __n, __x);
62            __new_finish = std::uninitialized_copy(__position, end(),
63                                                   __new_finish);
64          }
65          catch(...)
66          {
67            std::_Destroy(__new_start,__new_finish);
68            _M_deallocate(__new_start.base(),__len);
69            __throw_exception_again;
70          }
71          std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish);
72          _M_deallocate(this->_M_impl._M_start,
73                        this->_M_impl._M_end_of_storage - this->_M_impl._M_start);
74          this->_M_impl._M_start = __new_start.base();
75          this->_M_impl._M_finish = __new_finish.base();
76          this->_M_impl._M_end_of_storage = __new_start.base() + __len;
77        }
78      }
79    }

関数 std::uninitialized_copy()，std::uninitialized_fill_n() は，placement new を用いてコンストラクタを呼び出し，確保済みのメモリ領域を初期化します．詳しくはロベールのC++教室 - 第49章 破壊と創造や，s34 - 初期化されていないメモリへの記憶を参照してください．

ここまで来れば，前回の疑問である，コンストラクタが最初に 1 回余分に呼ばれている謎はもう解けました．_M_fill_insert() の 13 行目です．ここでコピーが 1 回発生しています．

insert() メンバ関数による要素の挿入時に，挿入位置より後の要素を後方にずらす処理を行っていますが，コピー元とコピー先の範囲が重なるかどうかで処理を分けてるところがあります(18 行目の if 文)．どんな場合でも後ろからコピーするわけではなく，可能ならば前から順にコピーするようになっていたことを，今回ソースを眺めることで初めて知ることができました．これを実装した GNU の人はこのようなところにも気を配っているわけです．