这里简要的记述一下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);
}
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);
}
到这里，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源码分析不在这里继续分析。