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源碼分析不在這裏繼續分析。
本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理
【其他文章推薦】
※台北網頁設計公司這麼多該如何選擇?
※智慧手機時代的來臨，RWD網頁設計為架站首選
※評比南投搬家公司費用收費行情懶人包大公開
※回頭車貨運收費標準
※網頁設計最專業,超強功能平台可客製化
※別再煩惱如何寫文案,掌握八大原則!
