अंतिम अद्यतन：2026-10-12
STL vector सोर्स कोड विश्लेषण¶
0.प्रस्तावना¶
vector की डेटा-व्यवस्था तथा ऑपरेशन का तरीका array जैसा ही है। दोनों में एकमात्र अंतर स्पेस उपयोग की लचीलापन में है — array स्टैटिक है, एक बार आवंटन के बाद बदला नहीं जा सकता, जबकि vector डायनामिक स्पेस है; एलिमेंट्स जुड़ने के साथ उसकी आंतरिक कार्यप्रणाली स्वयं स्पेस का विस्तार कर लेती है ताकि नए एलिमेंट समा सकें। आइए एक साथ देखें कि vector की "आंतरिक कार्यप्रणाली" स्पेस आवंटन रणनीति कैसे कार्यान्वित करती है।
1.vector¶
_Vector_base के आरंभ में दो पंक्तियाँ समझने में कठिन हैं; नीचे एक-एक करके विश्लेषण करते हैं:
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:
तुल्य है:
नीचे की दो पंक्तियों के अनुसार:
पुनः यह इसके तुल्य है:
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 में दो प्रकार के इटरेटर उपयोग होते हैं — फॉरवर्ड __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- जैसे स्थानांतरण ऑपरेशन सीधे गंतव्य पर पहुँच सकते हैं, जबकि गैर-रैंडम-एक्सेस पॉइंटर एक-एक कदम ही चल सकता है।
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 — द्वारा प्रबंधित होती है; पते, क्षमता आदि से जुड़े सभी ऑपरेशन्स में इन्हीं तीनों पॉइंटर्स की आवश्यकता होती है:
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 दो std::copy से कार्यान्वित होता है:
पहला swap __first के पॉइंटर तथा __last के पॉइंटर के बीच के डेटा को __result पॉइंटर की ओर इशारा किए आरंभिक स्थान पर कॉपी करता है।
दूसरा 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++那些事