STL常用序列容器

微信扫一扫,分享到朋友圈

STL常用序列容器

这里简要的记述一下STL常用容器的实现原理,要点等内容。

vector

vector
是比较常用的stl容器,用法与数组是非类似,其内部实现是连续空间分配,与数组的不同之处在于可弹性增加空间,而 array
是静态空间,分配后不能动态扩展。 vecotr
的实现较为简单,主要的关键点在于当空间不足时,会新分配当前空间2倍的空间,将旧空间数据拷贝到新空间,然后删除旧空间。

struct _Vector_impl: public _Tp_alloc_type {
pointer _M_start;   // 元素头
pointer _M_finish;  // 元素尾
pointer _M_end_of_storage;  // 可用空间尾,
// 省略部分代码...
};

这个是向尾部添加元素的代码实现,可以看到如果当前还有剩余空间的话,直接在尾部添加,如果没有剩余空间,则会动态扩展。

void push_back(const value_type& __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, __x);
++this->_M_impl._M_finish;
} else
_M_realloc_insert(end(), __x);
}
template<typename _Tp, typename _Alloc>
void vector<_Tp, _Alloc>::_M_realloc_insert(iterator __position, const _Tp& __x) {
const size_type __len = _M_check_len(size_type(1), "vector::_M_realloc_insert");      // 2倍当前大小
const size_type __elems_before = __position - begin();
pointer __new_start(this->_M_allocate(__len));
pointer __new_finish(__new_start);
__try {
// The order of the three operations is dictated by the C++11
// case, where the moves could alter a new element belonging
// to the existing vector.  This is an issue only for callers
// taking the element by lvalue ref (see last bullet of C++11
// [res.on.arguments]).
_Alloc_traits::construct(this->_M_impl, __new_start + __elems_before, __x);
__new_finish = pointer();
__new_finish = std::__uninitialized_move_if_noexcept_a(this->_M_impl._M_start, __position.base(), __new_start, _M_get_Tp_allocator();
++__new_finish;
__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;
}
std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish, _M_get_Tp_allocator());
_M_deallocate(this->_M_impl._M_start, this->_M_impl._M_end_of_storage - this->_M_impl._M_start);
this->_M_impl._M_start = __new_start;
this->_M_impl._M_finish = __new_finish;
this->_M_impl._M_end_of_storage = __new_start + __len;
}
// Called by _M_fill_insert, _M_insert_aux etc.
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);       // 二倍长
return (__len < size() || __len > max_size()) ? max_size() : __len;
}
pointer _M_allocate(size_t __n) {
typedef __gnu_cxx::__alloc_traits<_Tp_alloc_type> _Tr;
return __n != 0 ? _Tr::allocate(_M_impl, __n) : pointer();
}

使用时可使用 []
,因为其已实现重载 []

reference
operator[](size_type __n) _GLIBCXX_NOEXCEPT {
__glibcxx_requires_subscript(__n);
return *(this->_M_impl._M_start + __n);
}

使用时要注意迭代器失效问题,这个在很多STL容器中都有这个问题。

list

链表 list
,与 vector
不同,元素在内存中不连续分配,不支持随机存取,好处就是插入与删除时间复杂度为 O(1)
。在STL中,其实现的是双向链表,其节点的定义可以看到有前驱和后继指针,实现也较为简单。

/// An actual node in the %list.
template<typename _Tp>
struct _List_node : public __detail::_List_node_base {
_Tp _M_data;
_Tp* _M_valptr() { return std::__addressof(_M_data); }
_Tp const* _M_valptr() const { return std::__addressof(_M_data); }
};
struct _List_node_base {
_List_node_base* _M_next;
_List_node_base* _M_prev;
static void swap(_List_node_base& __x, _List_node_base& __y) _GLIBCXX_USE_NOEXCEPT;
void _M_transfer(_List_node_base* const __first, _List_node_base* const __last) _GLIBCXX_USE_NOEXCEPT;
void _M_reverse() _GLIBCXX_USE_NOEXCEPT;
void _M_hook(_List_node_base* const __position) _GLIBCXX_USE_NOEXCEPT;
void _M_unhook() _GLIBCXX_USE_NOEXCEPT;
};

deque

双端队列,具体实现不同于 vector
list
,它是一小段一小段连续空间,每段连续空间之间通过指针数组(这个数组中存放的是每个连续空间数组的头指针)串联起来,这样就能访问到所有元素。之所以采用这种存储布局,是有原因的,是有其应用场景的,等分析完源码后,我们就明白其为何要这么做了。

deque源码分析

我们摘取部分源码看一下其实现细节。双端队列的迭代器实现代码如下(相较于 vector
list
,对元素的访问因为其存储布局不同,在每一段连续分配空间的边缘要做特殊处理):

#define _GLIBCXX_DEQUE_BUF_SIZE 512       // 默认连续空间大小
_GLIBCXX_CONSTEXPR inline size_t __deque_buf_size(size_t __size) {
return (__size < _GLIBCXX_DEQUE_BUF_SIZE ? size_t(_GLIBCXX_DEQUE_BUF_SIZE / __size) :size_t(1));
}
template<typename _Tp, typename _Ref, typename _Ptr>
struct _Deque_iterator {
typedef _Deque_iterator<_Tp, _Tp&, _Tp*>	     iterator;
typedef _Deque_iterator<_Tp, const _Tp&, const _Tp*> const_iterator;
typedef _Tp*					 _Elt_pointer;
typedef _Tp**					_Map_pointer;
static size_t _S_buffer_size() _GLIBCXX_NOEXCEPT {
return __deque_buf_size(sizeof(_Tp));
}
typedef std::random_access_iterator_tag	iterator_category;
typedef _Tp				value_type;
typedef _Ptr				pointer;
typedef _Ref				reference;
typedef size_t				size_type;
typedef ptrdiff_t				difference_type;
typedef _Deque_iterator			_Self;
_Elt_pointer _M_cur;          // 当前位置
_Elt_pointer _M_first;        // 每一小段空间的开始
_Elt_pointer _M_last;         // 每一小段空间的结束
_Map_pointer _M_node;         // 指针数组,可通过这里访问到所有连续存储空间片段
// 构造函数
_Deque_iterator(_Elt_pointer __x, _Map_pointer __y) _GLIBCXX_NOEXCEPT : _M_cur(__x), _M_first(*__y),
_M_last(*__y + _S_buffer_size()), _M_node(__y) { }
_Deque_iterator() _GLIBCXX_NOEXCEPT: _M_cur(), _M_first(), _M_last(), _M_node() { }
_Deque_iterator(const iterator& __x) _GLIBCXX_NOEXCEPT: _M_cur(__x._M_cur), _M_first(__x._M_first),
_M_last(__x._M_last), _M_node(__x._M_node) { }
iterator _M_const_cast() const _GLIBCXX_NOEXCEPT {
return iterator(_M_cur, _M_node);     // 返回当前元素迭代器
}
reference operator*() const _GLIBCXX_NOEXCEPT {
return *_M_cur;
}
pointer operator->() const _GLIBCXX_NOEXCEPT {
return _M_cur;
}
// 重载++运算符,可以看到,当_M_cur指向本段连续空间尾部时,访问下一个元素的话是下一段连续空间的首地址
_Self& operator++() _GLIBCXX_NOEXCEPT {
++_M_cur;
if (_M_cur == _M_last) {
_M_set_node(_M_node + 1);   // 移向下一段连续存储空间
_M_cur = _M_first;          // 下一段连续空间的首元素
}
return *this;
}
_Self operator++(int) _GLIBCXX_NOEXCEPT {
_Self __tmp = *this;
++*this;
return __tmp;
}
_Self& operator--() _GLIBCXX_NOEXCEPT {
if (_M_cur == _M_first) {             // 与++类似,如果当前是第一个元素,--时,就应该调到上一个连续存储空间
_M_set_node(_M_node - 1);
_M_cur = _M_last;           // 移到上一段空间的最后,
}
--_M_cur;                       // 因为是[start, last)区间,这里要--_M_cur;
return *this;
}
_Self operator--(int) _GLIBCXX_NOEXCEPT {
_Self __tmp = *this;
--*this;
return __tmp;
}
_Self& operator+=(difference_type __n) _GLIBCXX_NOEXCEPT {
const difference_type __offset = __n + (_M_cur - _M_first);
if (__offset >= 0 && __offset < difference_type(_S_buffer_size()))  // 如果当前连续空间满足
_M_cur += __n;
else {  // 如果当前段连续空间不够用了,需要计算跳到连续空间
const difference_type __node_offset = __offset > 0 ? __offset / difference_type(_S_buffer_size()) : -difference_type((-__offset - 1) / _S_buffer_size()) - 1;
_M_set_node(_M_node + __node_offset);
_M_cur = _M_first + (__offset - __node_offset * difference_type(_S_buffer_size()));
}
return *this;
}
_Self operator+(difference_type __n) const _GLIBCXX_NOEXCEPT {
_Self __tmp = *this;
return __tmp += __n;
}
_Self& operator-=(difference_type __n) _GLIBCXX_NOEXCEPT {
return *this += -__n; }
_Self operator-(difference_type __n) const _GLIBCXX_NOEXCEPT {
_Self __tmp = *this;
return __tmp -= __n;
}
reference operator[](difference_type __n) const _GLIBCXX_NOEXCEPT { return *(*this + __n); }
// Prepares to traverse new_node.  Sets everything except _M_cur, which should therefore be set by the caller immediately afterwards, based on _M_first and _M_last.
void _M_set_node(_Map_pointer __new_node) _GLIBCXX_NOEXCEPT {     // 跳到新的一段连续存储空间
_M_node = __new_node;
_M_first = *__new_node;
_M_last = _M_first + difference_type(_S_buffer_size());
}
};

从上面 deque
迭代器的实现来看,主要需要注意的地方就是每段连续空间的边缘。看完迭代器后,我们看一下 deque
类的实现代码,这里删减掉大部分代码,保留部分代码。其中重点看一下 deque
中最常用的 push_front
pop_front
push_back
pop_back
的实现。 push_back
时间复杂度 O(1)
比较好理解,过程类似于 vector
,但 push_front
为什么也是 O(1)
呢?如果在头部插入一个元素,第一个连续空间距离起始 start
还有剩余空间的的话,直接插入就好了,如果没有剩余空间的话,就创建一段新的连续空间,将首地址放到 map
中,如果 map
没有空间放置这个首地址,就调整 map
,再插入首地址,详细过程请看源码的具体实现:

template<typename _Tp, typename _Alloc = std::allocator<_Tp> >
class deque : protected _Deque_base<_Tp, _Alloc> {
typedef _Deque_base<_Tp, _Alloc>			_Base;
typedef typename _Base::_Tp_alloc_type		_Tp_alloc_type;
typedef typename _Base::_Alloc_traits		_Alloc_traits;
typedef typename _Base::_Map_pointer		_Map_pointer;
public:
typedef _Tp					value_type;
typedef typename _Alloc_traits::pointer		pointer;
typedef typename _Alloc_traits::const_pointer	const_pointer;
typedef typename _Alloc_traits::reference		reference;
typedef typename _Alloc_traits::const_reference	const_reference;
typedef typename _Base::iterator			iterator;
typedef typename _Base::const_iterator		const_iterator;
typedef std::reverse_iterator<const_iterator>	const_reverse_iterator;
typedef std::reverse_iterator<iterator>		reverse_iterator;
typedef size_t					size_type;
typedef ptrdiff_t					difference_type;
typedef _Alloc					allocator_type;
protected:
static size_t _S_buffer_size() _GLIBCXX_NOEXCEPT { return __deque_buf_size(sizeof(_Tp)); }
// Functions controlling memory layout, and nothing else.
using _Base::_M_initialize_map;
using _Base::_M_create_nodes;
using _Base::_M_destroy_nodes;
using _Base::_M_allocate_node;
using _Base::_M_deallocate_node;
using _Base::_M_allocate_map;
using _Base::_M_deallocate_map;
using _Base::_M_get_Tp_allocator;
/**
*  A total of four data members accumulated down the hierarchy.
*  May be accessed via _M_impl.*
*/
using _Base::_M_impl;
public:
// 省略构造函数与析构函数......
/*
*  @brief  Assigns a given value to a %deque.
*  @param  __n  Number of elements to be assigned.
*  @param  __val  Value to be assigned.
*
*  This function fills a %deque with @a n copies of the given
*  value.  Note that the assignment completely changes the
*  %deque and that the resulting %deque's size is the same as
*  the number of elements assigned.
*/
void assign(size_type __n, const value_type& __val) { _M_fill_assign(__n, __val); }
// 省略其他assign重载函数......
/// Get a copy of the memory allocation object.
allocator_type get_allocator() const _GLIBCXX_NOEXCEPT{ return _Base::get_allocator(); }
// iterators
/**
*  Returns a read/write iterator that points to the first element in the
*  %deque.  Iteration is done in ordinary element order.
*/
iterator begin() _GLIBCXX_NOEXCEPT { return this->_M_impl._M_start; }
const_iterator begin() const _GLIBCXX_NOEXCEPT { return this->_M_impl._M_start; }
/**
*  Returns a read/write iterator that points one past the last
*  element in the %deque.  Iteration is done in ordinary
*  element order.
*/
iterator end() _GLIBCXX_NOEXCEPT{ return this->_M_impl._M_finish; }
const_iterator end() const _GLIBCXX_NOEXCEPT { return this->_M_impl._M_finish; }
// 省略其他迭代器相关代码......
// [23.2.1.2] capacity
/**  Returns the number of elements in the %deque.  */
size_type size() const _GLIBCXX_NOEXCEPT { return this->_M_impl._M_finish - this->_M_impl._M_start; }
/**  Returns the size() of the largest possible %deque.  */
size_type max_size() const _GLIBCXX_NOEXCEPT { return _Alloc_traits::max_size(_M_get_Tp_allocator()); }
/**
*  @brief  Resizes the %deque to the specified number of elements.
*  @param  __new_size  Number of elements the %deque should contain.
*
*  This function will %resize the %deque to the specified
*  number of elements.  If the number is smaller than the
*  %deque's current size the %deque is truncated, otherwise
*  default constructed elements are appended.
*/
void resize(size_type __new_size) {
const size_type __len = size();
if (__new_size > __len)
_M_default_append(__new_size - __len);
else if (__new_size < __len)
_M_erase_at_end(this->_M_impl._M_start + difference_type(__new_size));
}
#if __cplusplus >= 201103L
/**  A non-binding request to reduce memory use.  */
void shrink_to_fit() noexcept { _M_shrink_to_fit(); }
#endif
/**
*  Returns true if the %deque is empty.  (Thus begin() would
*  equal end().)
*/
bool empty() const _GLIBCXX_NOEXCEPT { return this->_M_impl._M_finish == this->_M_impl._M_start; }
// element access
/**
*  @brief Subscript access to the data contained in the %deque.
*  @param __n The index of the element for which data should be
*  accessed.
*  @return  Read/write reference to data.
*
*  This operator allows for easy, array-style, data access.
*  Note that data access with this operator is unchecked and
*  out_of_range lookups are not defined. (For checked lookups
*  see at().)
*/
reference operator[](size_type __n) _GLIBCXX_NOEXCEPT {
__glibcxx_requires_subscript(__n);
return this->_M_impl._M_start[difference_type(__n)];
}
protected:
/// Safety check used only from at().
void _M_range_check(size_type __n) const {
if (__n >= this->size())
__throw_out_of_range_fmt(__N("deque::_M_range_check: __n "
"(which is %zu)>= this->size() "
"(which is %zu)"), __n, this->size());
}
public:
/**
*  @brief  Provides access to the data contained in the %deque.
*  @param __n The index of the element for which data should be
*  accessed.
*  @return  Read/write reference to data.
*  @throw  std::out_of_range  If @a __n is an invalid index.
*
*  This function provides for safer data access.  The parameter
*  is first checked that it is in the range of the deque.  The
*  function throws out_of_range if the check fails.
*/
reference at(size_type __n) {
_M_range_check(__n);
return (*this)[__n];
}
/**
*  @brief  Provides access to the data contained in the %deque.
*  @param __n The index of the element for which data should be
*  accessed.
*  @return  Read-only (constant) reference to data.
*  @throw  std::out_of_range  If @a __n is an invalid index.
*
*  This function provides for safer data access.  The parameter is first
*  checked that it is in the range of the deque.  The function throws
*  out_of_range if the check fails.
*/
const_reference at(size_type __n) const {
_M_range_check(__n);
return (*this)[__n];
}
/**
*  Returns a read/write reference to the data at the first
*  element of the %deque.
*/
reference front() _GLIBCXX_NOEXCEPT {
__glibcxx_requires_nonempty();
return *begin();
}
/**
*  Returns a read/write reference to the data at the last element of the
*  %deque.
*/
reference back() _GLIBCXX_NOEXCEPT {
__glibcxx_requires_nonempty();
iterator __tmp = end();
--__tmp;
return *__tmp;
}
/**
*  @brief  Add data to the front of the %deque.
*  @param  __x  Data to be added.
*
*  This is a typical stack operation.  The function creates an
*  element at the front of the %deque and assigns the given
*  data to it.  Due to the nature of a %deque this operation
*  can be done in constant time.
*/
void push_front(const value_type& __x) {		// 如果第一段连续空间头部还有剩余空间的话,直接插入元素
if (this->_M_impl._M_start._M_cur != this->_M_impl._M_start._M_first) {
_Alloc_traits::construct(this->_M_impl, this->_M_impl._M_start._M_cur - 1, __x);
--this->_M_impl._M_start._M_cur;
} else		// 如果没有,在前部重新分配空间
_M_push_front_aux(__x);
}
/**
*  @brief  Add data to the end of the %deque.
*  @param  __x  Data to be added.
*
*  This is a typical stack operation.  The function creates an
*  element at the end of the %deque and assigns the given data
*  to it.  Due to the nature of a %deque this operation can be
*  done in constant time.
*/
void push_back(const value_type& __x) {
if (this->_M_impl._M_finish._M_cur != this->_M_impl._M_finish._M_last - 1) {
_Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish._M_cur, __x);
++this->_M_impl._M_finish._M_cur;
} else
_M_push_back_aux(__x);
}
/**
*  @brief  Removes first element.
*
*  This is a typical stack operation.  It shrinks the %deque by one.
*
*  Note that no data is returned, and if the first element's data is
*  needed, it should be retrieved before pop_front() is called.
*/
void pop_front() _GLIBCXX_NOEXCEPT {
__glibcxx_requires_nonempty();
if (this->_M_impl._M_start._M_cur != this->_M_impl._M_start._M_last - 1) {
_Alloc_traits::destroy(this->_M_impl,	this->_M_impl._M_start._M_cur);
++this->_M_impl._M_start._M_cur;
} else
_M_pop_front_aux();
}
/**
*  @brief  Removes last element.
*
*  This is a typical stack operation.  It shrinks the %deque by one.
*
*  Note that no data is returned, and if the last element's data is
*  needed, it should be retrieved before pop_back() is called.
*/
void pop_back() _GLIBCXX_NOEXCEPT {
__glibcxx_requires_nonempty();
if (this->_M_impl._M_finish._M_cur != this->_M_impl._M_finish._M_first) {
--this->_M_impl._M_finish._M_cur;
_Alloc_traits::destroy(this->_M_impl, this->_M_impl._M_finish._M_cur);
} else
_M_pop_back_aux();
}
/**
*  @brief  Inserts given value into %deque before specified iterator.
*  @param  __position  An iterator into the %deque.
*  @param  __x  Data to be inserted.
*  @return  An iterator that points to the inserted data.
*
*  This function will insert a copy of the given value before the
*  specified location.
*/
iterator insert(iterator __position, const value_type& __x);
/**
*  Erases all the elements.  Note that this function only erases the
*  elements, and that if the elements themselves are pointers, the
*  pointed-to memory is not touched in any way.  Managing the pointer is
*  the user's responsibility.
*/
void clear() _GLIBCXX_NOEXCEPT { _M_erase_at_end(begin()); }
protected:
// Internal constructor functions follow.
// 省略部分代码......
void _M_push_back_aux(const value_type&);
void _M_push_front_aux(const value_type&);
void _M_pop_back_aux();
void _M_pop_front_aux();
// 省略部分代码......
};

deque
的实现比 vector
list
要复杂的多,主要是因为其空间布局不太一样。下面的代码主要是对双端队列队首与队尾的操作( push_front
push_back
pop_front
pop_back
)中涉及到空间变动的部分代码实现:

// Called only if _M_impl._M_finish._M_cur == _M_impl._M_finish._M_last - 1.
template<typename _Tp, typename _Alloc>
void deque<_Tp, _Alloc>::_M_push_back_aux(const value_type& __t) {
_M_reserve_map_at_back();
*(this->_M_impl._M_finish._M_node + 1) = this->_M_allocate_node();      // map新指针指向新分配的连续空间
__try {
this->_M_impl.construct(this->_M_impl._M_finish._M_cur, __t);
this->_M_impl._M_finish._M_set_node(this->_M_impl._M_finish._M_node + 1);
this->_M_impl._M_finish._M_cur = this->_M_impl._M_finish._M_first;
} __catch(...) {
_M_deallocate_node(*(this->_M_impl._M_finish._M_node + 1));
__throw_exception_again;
}
}
// Called only if _M_impl._M_start._M_cur == _M_impl._M_start._M_first.
template<typename _Tp, typename _Alloc>
void deque<_Tp, _Alloc>::_M_push_front_aux(const value_type& __t) {
_M_reserve_map_at_front();
*(this->_M_impl._M_start._M_node - 1) = this->_M_allocate_node();       // map指定位置指向新分配的连续空间
__try {
this->_M_impl._M_start._M_set_node(this->_M_impl._M_start._M_node - 1);
this->_M_impl._M_start._M_cur = this->_M_impl._M_start._M_last - 1;
this->_M_impl.construct(this->_M_impl._M_start._M_cur, __t);
} __catch(...) {
++this->_M_impl._M_start;
_M_deallocate_node(*(this->_M_impl._M_start._M_node - 1));
__throw_exception_again;
}
}
// Called only if _M_impl._M_finish._M_cur == _M_impl._M_finish._M_first.
template <typename _Tp, typename _Alloc>
void deque<_Tp, _Alloc>::_M_pop_back_aux() {
_M_deallocate_node(this->_M_impl._M_finish._M_first);
this->_M_impl._M_finish._M_set_node(this->_M_impl._M_finish._M_node - 1);
this->_M_impl._M_finish._M_cur = this->_M_impl._M_finish._M_last - 1;
_Alloc_traits::destroy(_M_get_Tp_allocator(), this->_M_impl._M_finish._M_cur);
}
// Called only if _M_impl._M_start._M_cur == _M_impl._M_start._M_last - 1.
// Note that if the deque has at least one element (a precondition for this
// member function), and if
//   _M_impl._M_start._M_cur == _M_impl._M_start._M_last,
// then the deque must have at least two nodes.
template <typename _Tp, typename _Alloc>
void deque<_Tp, _Alloc>::_M_pop_front_aux() {
_Alloc_traits::destroy(_M_get_Tp_allocator(), this->_M_impl._M_start._M_cur);
_M_deallocate_node(this->_M_impl._M_start._M_first);
this->_M_impl._M_start._M_set_node(this->_M_impl._M_start._M_node + 1);
this->_M_impl._M_start._M_cur = this->_M_impl._M_start._M_first;
}

下面的原代码是调整 map
的,如果 map
没有适当空间插入新的连续空间首地址,就重新分配 map
(这种情况比如, map
的后面全部插满了,但前面还大量空着,就需要将目前的 map
中的元素进行移动,使 map
的元素分布在中间位置,首尾两端是空闲的,以便于后面插入新元素; 如果是 map
的空间不足了,则需要新分配 map
空间,新空间大小要大于新指针元素数量+2)。

void _M_reserve_map_at_back(size_type __nodes_to_add = 1) {
if (__nodes_to_add + 1 > this->_M_impl._M_map_size - (this->_M_impl._M_finish._M_node - this->_M_impl._M_map))
_M_reallocate_map(__nodes_to_add, false);
}
void _M_reserve_map_at_front(size_type __nodes_to_add = 1) {
if (__nodes_to_add > size_type(this->_M_impl._M_start._M_node - this->_M_impl._M_map))
_M_reallocate_map(__nodes_to_add, true);
}
template <typename _Tp, typename _Alloc>
void deque<_Tp, _Alloc>::_M_reallocate_map(size_type __nodes_to_add, bool __add_at_front) {
const size_type __old_num_nodes = this->_M_impl._M_finish._M_node - this->_M_impl._M_start._M_node + 1;
const size_type __new_num_nodes = __old_num_nodes + __nodes_to_add;
_Map_pointer __new_nstart;
if (this->_M_impl._M_map_size > 2 * __new_num_nodes) {
__new_nstart = this->_M_impl._M_map + (this->_M_impl._M_map_size - __new_num_nodes) / 2 + (__add_at_front ? __nodes_to_add : 0);	// 这里新map的开始往后移动了一段位置,是为了将来在前部插入的时候有剩余空间,后部空余一段位置也是。
if (__new_nstart < this->_M_impl._M_start._M_node)
std::copy(this->_M_impl._M_start._M_node, this->_M_impl._M_finish._M_node + 1, __new_nstart);
else
std::copy_backward(this->_M_impl._M_start._M_node, this->_M_impl._M_finish._M_node + 1, __new_nstart + __old_num_nodes);
} else {
size_type __new_map_size = this->_M_impl._M_map_size + std::max(this->_M_impl._M_map_size, __nodes_to_add) + 2;		// 要至少空余2个空闲位置
_Map_pointer __new_map = this->_M_allocate_map(__new_map_size);
__new_nstart = __new_map + (__new_map_size - __new_num_nodes) / 2 + (__add_at_front ? __nodes_to_add : 0);
std::copy(this->_M_impl._M_start._M_node, this->_M_impl._M_finish._M_node + 1, __new_nstart);
_M_deallocate_map(this->_M_impl._M_map, this->_M_impl._M_map_size);
this->_M_impl._M_map = __new_map;
this->_M_impl._M_map_size = __new_map_size;
}
this->_M_impl._M_start._M_set_node(__new_nstart);
this->_M_impl._M_finish._M_set_node(__new_nstart + __old_num_nodes - 1);
}

更详细的还是自己看STL的源码吧,顺便吐槽一下STL的源码,代码太臃肿了,看起来太累了,如果按照其实现原理,自己实现一个mini版STL,应该会简洁许多许多。

到这里, deque
中比较核心的源码已经基本分析完了,也基本展现了 deque
中几个关键成员函数是如何实现的,其迭代器的实现,其 map
的实现与调整。

deque与vector、list的对比

vector
能够实现随机访问,动态扩展,但在头部插入 O(n)
,开销较大,且动态扩展时需要复制所有的元素,同样效率较低。 list
插入、删除头尾部元素效率很高 O(n)
,但是不能随机访问,查找效率 O(n)
,每个节点需要存储前后节点指针,有较大的额外存储开销。而 deque
等于是在两种容器的优缺点进行了一定的平衡,在收尾插入、删除元素,效率很高 O(1)
,在中间插入 O(n)
都差不多,但其能实现随机访问,且动态扩展时不需要复制全体元素,只需要新分配足够的连续存储空间,最多重新复制一下 map
到新 map
,而 map
是各个连续存储空间首地址指针数组,容量相比全体元素小非常多,动态扩展时代价很小。所以, deque
相比 vector
在更一般的情况下有更高的性能,相比 list
有更小的额外存储空间(但 deque
拥有较大的最小内存开销,原因是它需要 map
和一段连续存储空间开销,即元素数目非常小时开销比 list
大,但当元素数目较多时,空间开销比 list
少)。

stack

栈也是经常用的数据结构,其实现较为简单,内部实现依赖 deque
,当然也可以用 vector
list
实现。

// Stack implementation -*- C++ -*-
template<typename _Tp, typename _Sequence = deque<_Tp> >
class stack {
// concept requirements
typedef typename _Sequence::value_type _Sequence_value_type;
public:
typedef typename _Sequence::value_type		value_type;
typedef typename _Sequence::reference		reference;
typedef typename _Sequence::const_reference	const_reference;
typedef typename _Sequence::size_type		size_type;
typedef	       _Sequence			container_type;
protected:
_Sequence c;
public:
stack(): c() { }
// 省略构造函数与析构函数......
/**
*  Returns true if the %stack is empty.
*/
bool empty() const { return c.empty(); }
/**  Returns the number of elements in the %stack.  */
size_type size() const { return c.size(); }
/**
*  Returns a read/write reference to the data at the first
*  element of the %stack.
*/
reference top() {
__glibcxx_requires_nonempty();
return c.back();
}
/**
*  @brief  Add data to the top of the %stack.
*  @param  __x  Data to be added.
*
*  This is a typical %stack operation.  The function creates an
*  element at the top of the %stack and assigns the given data
*  to it.  The time complexity of the operation depends on the
*  underlying sequence.
*/
void push(const value_type& __x) { c.push_back(__x); }
/**
*  @brief  Removes first element.
*
*  This is a typical %stack operation.  It shrinks the %stack
*  by one.  The time complexity of the operation depends on the
*  underlying sequence.
*
*  Note that no data is returned, and if the first element's
*  data is needed, it should be retrieved before pop() is
*  called.
*/
void pop() {
__glibcxx_requires_nonempty();
c.pop_back();
}
// 省略其他非关键代码......
};

queue

队列有普通的先进先出的队列,还有优先队列,优先级队列不仅仅要按先后顺序,更强调优先级高的先出队列。

普通队列的实现

普通队列的实现与栈实现差不多,也是基于 deque
实现的。

template<typename _Tp, typename _Sequence = deque<_Tp> >
class queue {
// concept requirements
typedef typename _Sequence::value_type _Sequence_value_type;
public:
typedef typename	_Sequence::value_type		value_type;
typedef typename	_Sequence::reference		reference;
typedef typename	_Sequence::const_reference	const_reference;
typedef typename	_Sequence::size_type		size_type;
typedef		_Sequence			container_type;
protected:
/*  Maintainers wondering why this isn't uglified as per style
*  guidelines should note that this name is specified in the standard,
*  C++98 [23.2.3.1].
*  (Why? Presumably for the same reason that it's protected instead
*  of private: to allow derivation.  But none of the other
*  containers allow for derivation.  Odd.)
*/
///  @c c is the underlying container.
_Sequence c;
public:
queue(): c() { }
// 省略构造函数与析构函数......
bool empty() const { return c.empty(); }
size_type size() const { return c.size(); }
reference front() {
__glibcxx_requires_nonempty();
return c.front();
}
reference back() {
__glibcxx_requires_nonempty();
return c.back();
}
// Add data to the end of the %queue.
void push(const value_type& __x) { c.push_back(__x); }
// Removes first element.
void pop() {
__glibcxx_requires_nonempty();
c.pop_front();
}
};

优先队列priority_queue实现

优先队列的实现原理是基于堆实现的,堆底层是数组,所以,这里 priority_queue
底层的序列容器是 vector
,选则 vector
而不是其他容器,是因为优先队列基于堆,而堆的各种操作中,插入、删除、都是从尾部插入、删除操作最后实际上物理删除的是尾部元素,而且其扩容是2倍扩容,符合二叉树下一层节点数目是上一次所有数目+1,二倍扩容恰好合适,当然也可以用其他容器(例如 deque
,但不是最优的)。至于堆实现优先队列的原理,这里不再叙述。源码实现如下:

template<typename _Tp, typename _Sequence = vector<_Tp>, typename _Compare  = less<typename _Sequence::value_type> >
class priority_queue {
#ifdef _GLIBCXX_CONCEPT_CHECKS
// concept requirements
typedef typename _Sequence::value_type _Sequence_value_type;
# if __cplusplus < 201103L
__glibcxx_class_requires(_Tp, _SGIAssignableConcept)
# endif
__glibcxx_class_requires(_Sequence, _SequenceConcept)
__glibcxx_class_requires(_Sequence, _RandomAccessContainerConcept)
__glibcxx_class_requires2(_Tp, _Sequence_value_type, _SameTypeConcept)
__glibcxx_class_requires4(_Compare, bool, _Tp, _Tp, _BinaryFunctionConcept)
#endif
#if __cplusplus >= 201103L
template<typename _Alloc>
using _Uses = typename
enable_if<uses_allocator<_Sequence, _Alloc>::value>::type;
#endif
public:
typedef typename	_Sequence::value_type		value_type;
typedef typename	_Sequence::reference		 reference;
typedef typename	_Sequence::const_reference	   const_reference;
typedef typename	_Sequence::size_type		 size_type;
typedef		_Sequence			    container_type;
typedef	       _Compare				    value_compare;
protected:
_Sequence  c;
_Compare   comp;	// 优先队列基于堆,而堆经常需要比较操作
public:
//    *  @brief  Default constructor creates no elements.
explicit priority_queue(const _Compare& __x = _Compare(), const _Sequence& __s = _Sequence()): c(__s), comp(__x) {
std::make_heap(c.begin(), c.end(), comp); 	// 构造堆
}
// 省略其他构造函数......
/**
*  Returns true if the %queue is empty.
*/
bool empty() const {
return c.empty();
}
/**  Returns the number of elements in the %queue.  */
size_type size() const { return c.size(); }
/**
*  Returns a read-only (constant) reference to the data at the first
*  element of the %queue.
*/
const_reference top() const {
__glibcxx_requires_nonempty();
return c.front();
}
/**
*  @brief  Add data to the %queue.
*  @param  __x  Data to be added.
*
*  This is a typical %queue operation.
*  The time complexity of the operation depends on the underlying
*  sequence.
*/
void push(const value_type& __x) {		// 优先队列中插入元素,先放到容器尾部,再进行“上移”操作使之满足堆性质。
c.push_back(__x);
std::push_heap(c.begin(), c.end(), comp);
}
/**
*  @brief  Removes first element.
*
*  This is a typical %queue operation.  It shrinks the %queue
*  by one.  The time complexity of the operation depends on the
*  underlying sequence.
*
*  Note that no data is returned, and if the first element's
*  data is needed, it should be retrieved before pop() is
*  called.
*/
void pop() {		//从优先队列中弹出首元素
__glibcxx_requires_nonempty();
std::pop_heap(c.begin(), c.end(), comp);
c.pop_back();
}
};

可以看到只要理解了堆的实现原理,优先队列的实现原理就非常容易理解,堆的相关STL源码分析不在这里继续分析。

央视Boys再“合体”亮相京东直播间,京东为北…

上一篇

顺丰旗下地图领域科技公司注册资本新增至约2.78亿人民币

下一篇

你也可能喜欢

STL常用序列容器

长按储存图像,分享给朋友