最終更新：2026-10-12
STL vector ソースコード解析¶
0.はじめに¶
vectorのデータの配置と操作方法は、arrayと非常によく似ています。両者の唯一の違いは空間の運用の柔軟性にあります。arrayは静的で、一度配置すると変更できませんが、vectorは動的な空間であり、要素が追加されると、その内部機構が自ら空間を拡張して新しい要素を収容します。以下で、vectorの「内部機構」がどのように空間配置戦略を実現しているかを一緒に見てみましょう。
1.vector¶
_Vector_baseの先頭には理解が比較的難しい2行があります。以下で1つずつ分析します：
1.1 _Tp_alloc_type¶
先頭で定義されています：
__gnu_cxx::__alloc_traitsの中で：対応するファイルは：ext/alloc_traits.hです
template<typename _Tp>
struct rebind
{ typedef typename _Base_type::template rebind_alloc<_Tp> other; };
そして_Base_typeは：
したがって上述は次と等価です：
続けてallocator_traitsの中を探します
見つかりました：
そこで：
次と等価です：
まとめ
次と等価です：
1.2 pointer¶
そしてpointerは：
次と等価です：
次の2行に基づいて：
さらに次と等価です：
allocator_traitsの中で次のものが見つかります：
/**
* @brief The allocator's pointer type.
*
* @c Alloc::pointer if that type exists, otherwise @c value_type*
*/
typedef __pointer pointer;
コメントでは、存在すればAlloc::pointer、そうでなければvalue_type *であると述べられています。
まとめ
typedef typename __gnu_cxx::__alloc_traits<_Tp_alloc_type>::pointer
pointer;
// 或者
typedef typename __gnu_cxx::__alloc_traits<allocator<_Tp>>::pointer
pointer;
次と等価です
/**
* @brief The allocator's pointer type.
*
* @c Alloc::pointer if that type exists, otherwise @c value_type*
*/
typedef __pointer pointer;
_Tp_alloc_type::pointer、すなわちallocator<_Tp>が存在すればallocator<_Tp>::pointerです。
これはallocator.hのソースコードを見てください：
そうでなければvalue_type*です。そしてvalue_typeは：
したがってvalue_type*は次のように導かれます：
1.3 vectorのメモリ管理¶
_Vector_baseの中には**メモリ管理器**_Vector_implクラスがあります。この構造体はallocatorを継承しています（上述の1.1の等価条件から導かれます）。
template<typename _Tp, typename _Alloc>
struct _Vector_base {
//__alloc_traits -> allocator_traits
// typedef allocator<_Tp> _Tp_alloc_type
typedef typename __gnu_cxx::__alloc_traits<_Alloc>::template
rebind<_Tp>::other _Tp_alloc_type;
// _Tp::value_type* or _Tp*
typedef typename __gnu_cxx::__alloc_traits<_Tp_alloc_type>::pointer
pointer;
struct _Vector_impl
: public _Tp_alloc_type {
pointer _M_start; // 使用空间起始位置
pointer _M_finish; // 使用空间结束位置
pointer _M_end_of_storage; // 可使用空间结束位置
_Vector_impl()
: _Tp_alloc_type(), _M_start(0), _M_finish(0), _M_end_of_storage(0) {}
_Vector_impl(_Tp_alloc_type const &__a)
// vector数据交换，只交换内存地址，不交换数据
void _M_swap_data(_Vector_impl &__x)
_GLIBCXX_NOEXCEPT
{
std::swap(_M_start, __x._M_start);
std::swap(_M_finish, __x._M_finish);
std::swap(_M_end_of_storage, __x._M_end_of_storage);
}
};
public:
typedef _Alloc allocator_type;
// 前面我们知道_Vector_impl继承自allocator分配器，而这个又是_Tp_alloc_type，所以这里返回的就是_M_impl的基类。
_Tp_alloc_type &
_M_get_Tp_allocator()
_GLIBCXX_NOEXCEPT
{ return *static_cast<_Tp_alloc_type *>(&this->_M_impl); }
const _Tp_alloc_type &
_M_get_Tp_allocator() const
_GLIBCXX_NOEXCEPT
{ return *static_cast<const _Tp_alloc_type *>(&this->_M_impl); }
allocator_type // 获取传递进来的分配器
get_allocator() const
_GLIBCXX_NOEXCEPT
{ return allocator_type(_M_get_Tp_allocator()); }
_Vector_base()
: _M_impl() {}
_Vector_base(const allocator_type &__a)
_GLIBCXX_NOEXCEPT
: _M_impl(__a) {}
_Vector_base(size_t __n)
: _M_impl() { _M_create_storage(__n); }
_Vector_base(size_t __n, const allocator_type &__a)
: _M_impl(__a) { _M_create_storage(__n); }
#if __cplusplus >= 201103L
_Vector_base(_Tp_alloc_type&& __a) noexcept
: _M_impl(std::move(__a)) { }
// 移动构造函数，只交换3个指针，不copy数据
_Vector_base(_Vector_base&& __x) noexcept
: _M_impl(std::move(__x._M_get_Tp_allocator()))
{ this->_M_impl._M_swap_data(__x._M_impl); }
_Vector_base(_Vector_base&& __x, const allocator_type& __a)
: _M_impl(__a)
{
if (__x.get_allocator() == __a)
this->_M_impl._M_swap_data(__x._M_impl);
else
{
size_t __n = __x._M_impl._M_finish - __x._M_impl._M_start;
_M_create_storage(__n);
}
}
#endif
~_Vector_base()
_GLIBCXX_NOEXCEPT
{
_M_deallocate(this->_M_impl._M_start, this->_M_impl._M_end_of_storage
- this->_M_impl._M_start);
}
public:
_Vector_impl _M_impl;
pointer _M_allocate(size_t __n) {
typedef __gnu_cxx::__alloc_traits <_Tp_alloc_type> _Tr;
return __n != 0 ? _Tr::allocate(_M_impl, __n) : 0; // 同_M_deallocate，一直往后调用的就是malloc函数
}
void _M_deallocate(pointer __p, size_t __n) {
typedef __gnu_cxx::__alloc_traits <_Tp_alloc_type> _Tr;
if (__p)
_Tr::deallocate(_M_impl, __p, __n); // 最后调用allocator_traits的deallocate,而该函数又是根据传递进来的_M_impl进行deallocate,一直往后，最后调用的就是free函数
}
private:
void _M_create_storage(size_t __n) {
this->_M_impl._M_start = this->_M_allocate(__n);
this->_M_impl._M_finish = this->_M_impl._M_start;
this->_M_impl._M_end_of_storage = this->_M_impl._M_start + __n;
}
};
まとめ：_Vector_baseは専らvectorのメモリ管理を担当し、内部クラス_M_implは_Tp_alloc_type（すなわちallocator）を継承することでメモリの割り当てと解放の機能を得ています。_M_allocateと_M_deallocateはそれぞれvectorが使うメモリの割り当てと解放を行い、vector自身は要素の構築と破棄だけを担当すればよいのです。
vectorでは、デフォルトのメモリアロケータはstd::allocator<_Tp>です
template<typename _Tp, typename _Alloc = std::allocator<_Tp>>
class vector : protected _Vector_base<_Tp, _Alloc> {
}
template<typename _Tp, typename _Alloc = std::allocator<_Tp>>
class vector : protected _Vector_base<_Tp, _Alloc> {
typedef _Vector_base<_Tp, _Alloc> _Base;
typedef typename _Base::_Tp_alloc_type _Tp_alloc_type;
public:
typedef typename _Base::pointer pointer;
protected:
using _Base::_M_allocate;
using _Base::_M_deallocate;
using _Base::_M_impl;
using _Base::_M_get_Tp_allocator;
}
2.vectorのイテレータ¶
vectorでは2種類のイテレータが使われています。それぞれ順方向の__normal_iteratorと逆方向のイテレータreverse_iteratorです：
順方向：
typedef __gnu_cxx::__normal_iterator <pointer, vector> iterator;
typedef __gnu_cxx::__normal_iterator <const_pointer, vector> const_iterator;
typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
typedef std::reverse_iterator<iterator> reverse_iterator;
__normal_iteratorとreverse_iteratorはどちらもstl_iterator.hで定義されており、vector要素のポインタをカプセル化しています。
2.1 順方向¶
template<typename _Iterator, typename _Container>
class __normal_iterator
{
protected:
_Iterator _M_current;
typedef iterator_traits<_Iterator> __traits_type;
public:
typedef _Iterator iterator_type;
// iterator必须包含的五种typedef
typedef typename __traits_type::iterator_category iterator_category;
typedef typename __traits_type::value_type value_type;
typedef typename __traits_type::difference_type difference_type;
typedef typename __traits_type::reference reference;
typedef typename __traits_type::pointer pointer;
_GLIBCXX_CONSTEXPR __normal_iterator() _GLIBCXX_NOEXCEPT
: _M_current(_Iterator()) { }
explicit
__normal_iterator(const _Iterator& __i) _GLIBCXX_NOEXCEPT
: _M_current(__i) { }
// Allow iterator to const_iterator conversion
template<typename _Iter>
__normal_iterator(const __normal_iterator<_Iter,
typename __enable_if<
(std::__are_same<_Iter, typename _Container::pointer>::__value),
_Container>::__type>& __i) _GLIBCXX_NOEXCEPT
: _M_current(__i.base()) { }
// Forward iterator requirements
reference
operator*() const _GLIBCXX_NOEXCEPT
{ return *_M_current; }
pointer
operator->() const _GLIBCXX_NOEXCEPT
{ return _M_current; }
// 前置++
__normal_iterator&
operator++() _GLIBCXX_NOEXCEPT
{
++_M_current;
return *this;
}
// 后置++
__normal_iterator
operator++(int) _GLIBCXX_NOEXCEPT
{ return __normal_iterator(_M_current++); }
// 前置--
// Bidirectional iterator requirements
__normal_iterator&
operator--() _GLIBCXX_NOEXCEPT
{
--_M_current;
return *this;
}
// 后置--
__normal_iterator
operator--(int) _GLIBCXX_NOEXCEPT
{ return __normal_iterator(_M_current--); }
// 随机访问迭代器都要重载[]操作符
// Random access iterator requirements
reference
operator[](difference_type __n) const _GLIBCXX_NOEXCEPT
{ return _M_current[__n]; }
// +=操作符 跳跃n个difference_type
__normal_iterator&
operator+=(difference_type __n) _GLIBCXX_NOEXCEPT
{ _M_current += __n; return *this; }
// +操作符 跳跃n个difference_type
__normal_iterator
operator+(difference_type __n) const _GLIBCXX_NOEXCEPT
{ return __normal_iterator(_M_current + __n); }
// -=操作符 后退n个difference_type
__normal_iterator&
operator-=(difference_type __n) _GLIBCXX_NOEXCEPT
{ _M_current -= __n; return *this; }
// -操作符 后退n个difference_type
__normal_iterator
operator-(difference_type __n) const _GLIBCXX_NOEXCEPT
{ return __normal_iterator(_M_current - __n); }
const _Iterator&
base() const _GLIBCXX_NOEXCEPT
{ return _M_current; }
};
_M_currentはイテレータの位置を指すポインタです。これはランダムアクセス型のポインタで、operator+やoperator-などの移動操作で直接目的地へ移動できます。非ランダムアクセス型のポインタは1歩ずつ移動するしかありません。
2.2 逆方向¶
vectorはreverse_iterator、すなわち逆順イテレータも使います。名前が示す通り、その移動方向は普通のイテレータと逆です
template<typename _Iterator>
class reverse_iterator
: public iterator<typename iterator_traits<_Iterator>::iterator_category,
typename iterator_traits<_Iterator>::value_type,
typename iterator_traits<_Iterator>::difference_type,
typename iterator_traits<_Iterator>::pointer,
typename iterator_traits<_Iterator>::reference>
{
protected:
_Iterator current;
typedef iterator_traits<_Iterator> __traits_type;
public:
typedef _Iterator iterator_type;
typedef typename __traits_type::difference_type difference_type;
typedef typename __traits_type::pointer pointer;
typedef typename __traits_type::reference reference;
// 省略不重要的代码
// 该迭代器是从后面end()开始，需要往前一步，才可以获取到有效的迭代器位置
reference
operator*() const
{
_Iterator __tmp = current;
return *--__tmp;
}
// 通过调用上述*操作符直接实现
pointer
operator->() const
{ return &(operator*()); }
// 前置++操作符完成后退任务
reverse_iterator&
operator++()
{
--current;
return *this;
}
// 后置++
reverse_iterator
operator++(int)
{
reverse_iterator __tmp = *this;
--current;
return __tmp;
}
// 前置--操作符完成前进任务
reverse_iterator&
operator--()
{
++current;
return *this;
}
// 后置--
reverse_iterator
operator--(int)
{
reverse_iterator __tmp = *this;
++current;
return __tmp;
}
// +操作符
reverse_iterator
operator+(difference_type __n) const
{ return reverse_iterator(current - __n); }
// +=操作符
reverse_iterator&
operator+=(difference_type __n)
{
current -= __n;
return *this;
}
// -操作符
reverse_iterator
operator-(difference_type __n) const
{ return reverse_iterator(current + __n); }
// -=操作符
reverse_iterator&
operator-=(difference_type __n)
{
current += __n;
return *this;
}
// []操作符
reference
operator[](difference_type __n) const
{ return *(*this + __n); }
};
3.vectorのデータ構造¶
vectorのメモリは_M_implの中のM_start、_M_finish、_M_end_of_storageの3つのポインタで管理されており、アドレスや容量のサイズなどに関するすべての操作にはこの3つのポインタが必要です：
iterator begin() _GLIBCXX_NOEXCEPT
{ return iterator(this->_M_impl._M_start); }
iterator end() _GLIBCXX_NOEXCEPT
{ return iterator(this->_M_impl._M_finish); }
reverse_iterator rbegin() noexcept
{ return reverse_iterator(end()); }
reverse_iterator rend() noexcept
{ return reverse_iterator(begin()); }
size_type size() const _GLIBCXX_NOEXCEPT
{ return size_type(this->_M_impl._M_finish - this->_M_impl._M_start); }
size_type capacity() const _GLIBCXX_NOEXCEPT
{ return size_type(this->_M_impl._M_end_of_storage - this->_M_impl._M_start); }
bool empty() const _GLIBCXX_NOEXCEPT
{ return begin() == end(); }
_M_finishと_M_end_of_storageの間の空間にはデータがなく、ときにはこれは無駄になります。c++11はとても役立つ関数shrink_to_fit()を提供しており、この未使用の空間を解放します。主に次のコードを呼び出しています。
template<typename _Alloc>
bool vector<bool, _Alloc>::
_M_shrink_to_fit()
{
if (capacity() - size() < int(_S_word_bit)) // 64位系统为64bytes
return false;
__try
{
_M_reallocate(size());
return true;
}
__catch(...)
{
return false;
}
}
template<typename _Alloc>
void vector<bool, _Alloc>::
_M_reallocate(size_type __n)
{
_Bit_type* __q = this->_M_allocate(__n);
this->_M_impl._M_finish = _M_copy_aligned(begin(), end(),
iterator(__q, 0));
this->_M_deallocate();
this->_M_impl._M_start = iterator(__q, 0);
this->_M_impl._M_end_of_storage = __q + _S_nword(__n);
}
_M_copy_alignedは2つのstd::copyで実現されています：
最初のswapで__firstのポインタと__lastのポインタの間のデータを__resultポインタが指す開始位置にコピーします。
2回目のswapで__lastのポインタに対応するイテレータを取得します。
iterator
_M_copy_aligned(const_iterator __first, const_iterator __last,
iterator __result)
{
// _Bit_type * _M_p; _Bit_type为unsigned long类型
_Bit_type* __q = std::copy(__first._M_p, __last._M_p, __result._M_p);
return std::copy(const_iterator(__last._M_p, 0), __last,
iterator(__q, 0));
}
begin()とend()の間のデータを格納するのに使います。元のvectorの空間を解放し、新しいvectorはsize()個のデータだけを含み、_M_startと_M_end_of_storageの指す先を修正します。
4.vectorの構築と破棄¶
//使用默认内存分配器
vector() : _Base() { }
//指定内存分配器
explicit vector(const allocator_type& __a) : _Base(__a) { }
//初始化为n个__value值，如果没指定就使用该类型默认值
explicit vector(size_type __n, const value_type& __value = value_type(),
const allocator_type& __a = allocator_type()): _Base(__n, __a)
{ _M_fill_initialize(__n, __value); }
//拷贝构造函数
vector(const vector& __x)
: _Base(__x.size(),
_Alloc_traits::_S_select_on_copy(__x._M_get_Tp_allocator()))
{ this->_M_impl._M_finish =
std::__uninitialized_copy_a(__x.begin(), __x.end(),
this->_M_impl._M_start,
_M_get_Tp_allocator());
}
//c++11的移动构造函数，获取__x的M_start，_M_finish，_M_end_of_storage，并不需要数据拷贝
vector(vector&& ) noexcept
: _Base(std::move(__x)) { }
//从list中拷贝数据，也是c++11才有的
vector(initializer_list<value_type> __l,
const allocator_type& __a = allocator_type())
: _Base(__a)
{
_M_range_initialize(__l.begin(), __l.end(), random_access_iterator_tag());
}
//支持vector使用两个迭代器范围内的值初始化，除了stl的迭代器，也可以是数组地址
template<typename _InputIterator,
typename = std::_RequireInputIter<_InputIterator>>
vector(_InputIterator __first, _InputIterator __last,
const allocator_type& __a = allocator_type())
: _Base(__a)
{ _M_initialize_dispatch(__first, __last, __false_type()); }
//只析构所有元素，释放内存由vector_base完成
~vector() _GLIBCXX_NOEXCEPT
{ std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,_M_get_Tp_allocator()); }
5.vector¶
挿入はメモリの割り当てと動的調整に関わります。冒頭で触れたvectorとarrayの違いは、まさにここで現れています：
typename vector<_Tp, _Alloc>::iterator
vector<_Tp, _Alloc>::insert(iterator __position, const value_type& __x)
{
const size_type __n = __position – begin();
//插入到最后一个位置，相当于push_back
if (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);
else
std::_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));
const size_type __len = size() + std::max(size(), __n); //如果n小于当前size，内存加倍，否则内存增长n。
return (__len < size() || __len > max_size()) ? max_size() : __len;
}
学習資料：
侯捷《STL源码剖析》
関連トピック¶
- STL array ソースコード解析 | C++那些事
- STL string 深入解析 | C++那些事
- STL string 面接問題解説 | C++那些事
- STL deque ソースコード解析 | C++那些事
- STL 空基底クラス最適化 EBO | C++那些事
- STL 手書きハッシュテーブル実装 | C++那些事
- STL hashtable ハッシュテーブル | C++那些事
- STL イテレータソースコード解析 | C++那些事
- STL list ソースコード解析 | C++那些事
- STL map と multimap | C++那些事