### 前言
? deque是一種雙向開口的分段連續線性空間，可以在頭尾端進行元素的插入和刪除。deque與vector最大的差異就是：第一是deque允許于常數時間內對頭端進行插入或刪除元素；第二是deque是分段連續線性空間，隨時可以增加一段新的空間；deque不像vector那樣，vector當內存不夠時，需重新分配/復制數據/釋放原始空間；不過deque的迭代器設置比vector復雜，因為迭代器不能使用普通指針，因此盡量使用vector；?當對deque的元素進行排序時，為了提高效率，首先把deque數據復制到vector，利用vector的排序算法(利用STL的sort算法)，排序之后再次復制回deque；本文所列的源碼出自SGI STL中的文件<stl_deque.h>，對于deque容器類的詳細信息也可以查看[《deque容器庫》](http://zh.cppreference.com/w/cpp/container/deque)和[《](http://msdn.microsoft.com/zh-cn/library/22a9t119.aspx)[MSDN](http://msdn.microsoft.com/zh-cn/library/22a9t119.aspx)[的](http://msdn.microsoft.com/zh-cn/library/22a9t119.aspx)[deque](http://msdn.microsoft.com/zh-cn/library/22a9t119.aspx)[類》](http://msdn.microsoft.com/zh-cn/library/22a9t119.aspx)
### deque容器
### deque中控器
? 由于deque是分段連續線性空間的，為了用戶方便操作，所以它對外的接口類似于連續空間。為了管理這些分段空間deque容器引入了一種中控器map，map是一塊連續的空間，其中每個元素是指向緩沖區的指針，緩沖區才是deque存儲數據的主體。下面給出map的結構；
~~~
_Tp**_M_map;
size_t _M_map_size;
~~~
### deque的迭代器
? ? ?deque是分段連續的線性空間，則普通指針不能作為deque的迭代器。迭代器設計時必須能夠進行operator++或operator--操作，為了能夠是用戶隨機訪問容器，則必須對操作符進行重載。
? ? **deque**迭代器的功能**：
1. 必須知道緩沖區的位置
1. 能夠判斷是否處于其所在緩沖區的邊界
1. 能夠知道其所在緩沖區當前所指位置的元素
?迭代器的數據結構如下：
~~~
struct _Deque_iterator {
...
//以下是迭代器設計的關鍵，訪問容器的節點
_Tp* _M_cur;//指向緩沖區當前的元素
_Tp* _M_first;//指向緩沖區的頭(起始地址)
_Tp* _M_last;//指向緩沖區的尾(結束地址)
_Map_pointer _M_node;//指向中控器的相應節點
...
};
~~~
?為了實現能夠隨機訪問，deque的中控器、緩沖區和迭代器之間的相互關系如下圖所示：
?以下是對迭代器源碼的剖析：
~~~
//* deque是分段連續線性空間，為了能夠像連續線性空間那樣訪問數據，
//* deque采用了一種中控方法map,map是塊連續的空間，其每個元素都是一個指針，
//* 指向一塊緩沖區，實質上map是T**；
//*********************************
// Note: this function is simply a kludge to work around several compilers'
// bugs in handling constant expressions.
//這個函數是方便不同編譯器處理常量表達式的bug
inline size_t __deque_buf_size(size_t __size) {
return __size < 512 ? size_t(512 / __size) : size_t(1);
}
//deque迭代器的設計
//*deque是分段連續的線性空間，迭代器設計時必須能夠進行operator++或operator--操作
//* 迭代器的功能：
//* 1、必須知道緩沖區的位置
//* 2、能夠判斷是否處于其所在緩沖區的邊界
//* 3、能夠知道其所在緩沖區當前所指位置的元素
//**********************
template <class _Tp, class _Ref, class _Ptr>
struct _Deque_iterator {
typedef _Deque_iterator<_Tp, _Tp&, _Tp*> iterator;
typedef _Deque_iterator<_Tp, const _Tp&, const _Tp*> const_iterator;
static size_t _S_buffer_size() { return __deque_buf_size(sizeof(_Tp)); }
typedef 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 _Tp**_Map_pointer;
typedef _Deque_iterator _Self;
//以下是迭代器設計的關鍵，訪問容器的節點
_Tp* _M_cur;//指向緩沖區當前的元素
_Tp* _M_first;//指向緩沖區的頭(起始地址)
_Tp* _M_last;//指向緩沖區的尾(結束地址)
_Map_pointer _M_node;//指向中控器的相應節點
_Deque_iterator(_Tp* __x, _Map_pointer __y)
: _M_cur(__x), _M_first(*__y),
_M_last(*__y + _S_buffer_size()), _M_node(__y) {}
_Deque_iterator() : _M_cur(0), _M_first(0), _M_last(0), _M_node(0) {}
_Deque_iterator(const iterator& __x)
: _M_cur(__x._M_cur), _M_first(__x._M_first),
_M_last(__x._M_last), _M_node(__x._M_node) {}
//**************************************
//***********以下是迭代器_Deque_iterator的操作************
//* 這些操作符的重載方便我們訪問容器的內容
//* 也是讓deque從接口看來是維護連續線性空間的關鍵
//**************************************
reference operator*() const { return *_M_cur; }//解除引用,返回當前元素
#ifndef __SGI_STL_NO_ARROW_OPERATOR
pointer operator->() const { return _M_cur; }
#endif /* __SGI_STL_NO_ARROW_OPERATOR */
//返回兩個迭代器之間的距離
difference_type operator-(const _Self& __x) const {
return difference_type(_S_buffer_size()) * (_M_node - __x._M_node - 1) +
(_M_cur - _M_first) + (__x._M_last - __x._M_cur);
}
//前綴自增++操作符重載
_Self& operator++() {
++_M_cur; //普通自增操作，移至下一個元素
if (_M_cur == _M_last) { //若已達到緩沖區的尾部
_M_set_node(_M_node + 1);//切換至下一緩沖區(節點)
_M_cur = _M_first; //的第一個元素
}
return *this;
}
//后綴自增++操作符重載
//返回當前迭代器的一個副本
_Self operator++(int) {
_Self __tmp = *this;//定義當前迭代器的一個副本
++*this;//這里前綴++不是普通的++操作，是上一步驟已經重載過的前綴++
return __tmp;
}
//前綴自減--操作符重載
//基本思想類似于前綴自增操作
_Self& operator--() {
if (_M_cur == _M_first) { //若是當前緩沖區的第一個元素
_M_set_node(_M_node - 1);//切換到上一個緩沖區
_M_cur = _M_last; //的尾部(即最后一個元素的下一個位置)
}
--_M_cur;//普通的自減操作，移至前一個元素
return *this;
}
//后綴自減--操作符重載
//返回當前迭代器的副本
_Self operator--(int) {
_Self __tmp = *this;//定義一個副本
--*this; //迭代器自減操作
return __tmp;
}
//以下實現隨機存取，迭代器可以直接跳躍n個距離
//將迭代器前移n個距離，當n負值時就為下面的operator-=操作
_Self& operator+=(difference_type __n)
{
difference_type __offset = __n + (_M_cur - _M_first);//定義一個中間變量
if (__offset >= 0 && __offset < difference_type(_S_buffer_size()))
//若前移n個距離后，目標依然在同一個緩沖區
//則直接前移n個距離
_M_cur += __n;
else {
//若前移n個距離后，目標超出該緩沖區范圍
//__offset / difference_type(_S_buffer_size())計算向后移動多少個緩沖區
//-difference_type((-__offset - 1) / _S_buffer_size()) - 1計算向前移動多少個緩沖區
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
{
_Self __tmp = *this;
//調用operator+=操作
return __tmp += __n;
}
//利用operator+=操作實現
_Self& operator-=(difference_type __n) { return *this += -__n; }
_Self operator-(difference_type __n) const {
_Self __tmp = *this;
return __tmp -= __n;
}
//返回指定位置的元素，即實現隨機存取
//該函數調用operator+，operator*
reference operator[](difference_type __n) const { return *(*this + __n); }
bool operator==(const _Self& __x) const { return _M_cur == __x._M_cur; }
bool operator!=(const _Self& __x) const { return !(*this == __x); }
bool operator<(const _Self& __x) const {
return (_M_node == __x._M_node) ?
(_M_cur < __x._M_cur) : (_M_node < __x._M_node);
}
bool operator>(const _Self& __x) const { return __x < *this; }
bool operator<=(const _Self& __x) const { return !(__x < *this); }
bool operator>=(const _Self& __x) const { return !(*this < __x); }
//調整到正確的緩沖區
//切換到正確的元素位置
void _M_set_node(_Map_pointer __new_node) {
_M_node = __new_node;//指向新的節點
_M_first = *__new_node;//指向新節點的頭部
_M_last = _M_first + difference_type(_S_buffer_size());//指向新節點的尾部
}
};
~~~
### deque容器的數據結構
? ? ?deque容器具有維護map和迭代器的功能，deque定義的兩個迭代器分別是start和finish，分別指向第一個緩沖區的第一個元素和最后一個緩沖區的最后一個元素的下一個位置；
~~~
template <class _Tp, class _Alloc>
class _Deque_base {
...
protected:
_Tp**_M_map;
size_t _M_map_size;
iterator _M_start;
iterator _M_finish;
...
};
//deque容器的定義
//配置器默認為第二級配置器
template <class _Tp, class _Alloc = __STL_DEFAULT_ALLOCATOR(_Tp) >
class deque : protected _Deque_base<_Tp, _Alloc> {
// requirements:
...
public: // Iterators
typedef typename _Base::iterator iterator;
typedef typename _Base::const_iterator const_iterator;
protected:
//下面是deque的數據結構
using _Base::_M_map;//指向中控器map
using _Base::_M_map_size;//map內指針的個數
using _Base::_M_start;//指向第一個節點
using _Base::_M_finish;//指向最后一個節點
...
};
~~~
? 容器的結構圖如下所示：
### deque容器的構造函數和析構函數
? ?了解deque容器的構造函數和析構函數，方便我們使用；其源碼如下：
~~~
public:
//******************************
//* 以下是構造函數和析構函數
//* 默認構造函數
//* explicit deque( const Allocator& alloc = Allocator() );
//* 容器大小為count個初始值為value的元素
//* explicit deque( size_type count,
//* const T& value = T(),
//* const Allocator& alloc = Allocator());
//* deque( size_type count,
//* const T& value,
//* const Allocator& alloc = Allocator());
//* 容器大小為count個默認值的元素
//* explicit deque( size_type count );
//* 拷貝構造函數
//* deque( const deque& other );
//* deque( const deque& other, const Allocator& alloc );
//* 初始值為[first,last)內容的容器
//* template< class InputIt >
//* deque( InputIt first, InputIt last,
//* const Allocator& alloc = Allocator() );
//* 析構函數
//* ~deque()
//*
//****************************
// Constructor, destructor.
explicit deque(const allocator_type& __a = allocator_type())
: _Base(__a, 0) {}
deque(const deque& __x) : _Base(__x.get_allocator(), __x.size())
{ uninitialized_copy(__x.begin(), __x.end(), _M_start); }
deque(size_type __n, const value_type& __value,
const allocator_type& __a = allocator_type()) : _Base(__a, __n)
{ _M_fill_initialize(__value); }
explicit deque(size_type __n) : _Base(allocator_type(), __n)
{ _M_fill_initialize(value_type()); }
#ifdef __STL_MEMBER_TEMPLATES
// Check whether it's an integral type. If so, it's not an iterator.
template <class _InputIterator>
deque(_InputIterator __first, _InputIterator __last,
const allocator_type& __a = allocator_type()) : _Base(__a) {
typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
_M_initialize_dispatch(__first, __last, _Integral());
}
template <class _Integer>
void _M_initialize_dispatch(_Integer __n, _Integer __x, __true_type) {
_M_initialize_map(__n);
_M_fill_initialize(__x);
}
template <class _InputIter>
void _M_initialize_dispatch(_InputIter __first, _InputIter __last,
__false_type) {
_M_range_initialize(__first, __last, __ITERATOR_CATEGORY(__first));
}
#else /* __STL_MEMBER_TEMPLATES */
deque(const value_type* __first, const value_type* __last,
const allocator_type& __a = allocator_type())
: _Base(__a, __last - __first)
{ uninitialized_copy(__first, __last, _M_start); }
deque(const_iterator __first, const_iterator __last,
const allocator_type& __a = allocator_type())
: _Base(__a, __last - __first)
{ uninitialized_copy(__first, __last, _M_start); }
#endif /* __STL_MEMBER_TEMPLATES */
~deque() { destroy(_M_start, _M_finish); }
//構造函數和析構函數定義結束
~~~
### deque容器的成員函數
? 關于成員函數的講解，這里只給出源碼的剖析：
~~~
//交換兩個容器的內容
//這里實際上并沒有交換具體的元素，而是交換迭代器
//和中控器信息
void swap(deque& __x) {
__STD::swap(_M_start, __x._M_start);
__STD::swap(_M_finish, __x._M_finish);
__STD::swap(_M_map, __x._M_map);
__STD::swap(_M_map_size, __x._M_map_size);
}
public:
// assign(), a generalized assignment member function. Two
// versions: one that takes a count, and one that takes a range.
// The range version is a member template, so we dispatch on whether
// or not the type is an integer.
void _M_fill_assign(size_type __n, const _Tp& __val) {
if (__n > size()) {//若新的大小比容器原來的大
fill(begin(), end(), __val);//把原來容器填充為val
insert(end(), __n - size(), __val);//容器追加填充值
}
else {//若新的大小比容器原來的小
erase(begin() + __n, end());//則擦除多余的內容
fill(begin(), end(), __val);//填充值為val覆蓋原來的內容
}
}
//對外接口的assign第一個版本
void assign(size_type __n, const _Tp& __val) {
_M_fill_assign(__n, __val);
}
#ifdef __STL_MEMBER_TEMPLATES
//對外接口的assign第二個版本
//采用迭代器的traist技術
template <class _InputIterator>
void assign(_InputIterator __first, _InputIterator __last) {
typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
_M_assign_dispatch(__first, __last, _Integral());
}
private: // helper functions for assign()
template <class _Integer>
void _M_assign_dispatch(_Integer __n, _Integer __val, __true_type)
{ _M_fill_assign((size_type) __n, (_Tp) __val); }
template <class _InputIterator>
void _M_assign_dispatch(_InputIterator __first, _InputIterator __last,
__false_type) {
_M_assign_aux(__first, __last, __ITERATOR_CATEGORY(__first));
}
template <class _InputIterator>
void _M_assign_aux(_InputIterator __first, _InputIterator __last,
input_iterator_tag);
template <class _ForwardIterator>
void _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last,
forward_iterator_tag) {
size_type __len = 0;
distance(__first, __last, __len);//計算兩個輸入迭代器的距離
if (__len > size()) {//若輸入迭代器距離比待賦值容器大小還大
_ForwardIterator __mid = __first;
advance(__mid, size());//將mid向前移動size()個距離
copy(__first, __mid, begin());//先復制[first,mid)數據
insert(end(), __mid, __last);//插入剩下的數據
}
else//否則擦除多余的數據
erase(copy(__first, __last, begin()), end());
}
#endif /* __STL_MEMBER_TEMPLATES */
public: // push_* and pop_*
//在容器尾部加數據
void push_back(const value_type& __t) {
//若當前緩沖區存在可用空間
if (_M_finish._M_cur != _M_finish._M_last - 1) {
construct(_M_finish._M_cur, __t);//直接構造對象
++_M_finish._M_cur;//調整指針所指位置
}
else//若當前緩沖區不存在可用空間
//需分配一段新的連續空間
_M_push_back_aux(__t);
}
void push_back() {
if (_M_finish._M_cur != _M_finish._M_last - 1) {
construct(_M_finish._M_cur);
++_M_finish._M_cur;
}
else
_M_push_back_aux();
}
void push_front(const value_type& __t) {
if (_M_start._M_cur != _M_start._M_first) {
construct(_M_start._M_cur - 1, __t);
--_M_start._M_cur;
}
else
_M_push_front_aux(__t);
}
void push_front() {
if (_M_start._M_cur != _M_start._M_first) {
construct(_M_start._M_cur - 1);
--_M_start._M_cur;
}
else
_M_push_front_aux();
}
void pop_back() {
if (_M_finish._M_cur != _M_finish._M_first) {
--_M_finish._M_cur;
destroy(_M_finish._M_cur);
}
else
_M_pop_back_aux();
}
void pop_front() {
if (_M_start._M_cur != _M_start._M_last - 1) {
destroy(_M_start._M_cur);
++_M_start._M_cur;
}
else
_M_pop_front_aux();
}
public:
//*******************************
/* 在指定位置之前插入數據
*******************************
* iterator insert (iterator position, const value_type& val);
*
* void insert (iterator position, size_type n, const value_type& val);
*
* template <class InputIterator>
* void insert (iterator position, InputIterator first, InputIterator last);
*/
//*******************************
// Insert
iterator insert(iterator position, const value_type& __x) {
if (position._M_cur == _M_start._M_cur) {//若當前位置為deque.begin()
push_front(__x);//則在容器頭部插入數據
return _M_start;
}
else if (position._M_cur == _M_finish._M_cur) {//若當前位置為deque.end()
push_back(__x);
iterator __tmp = _M_finish;
--__tmp;
return __tmp;
}
else {//否則在容器直接插入數據
return _M_insert_aux(position, __x);
}
}
iterator insert(iterator __position)
{ return insert(__position, value_type()); }
void insert(iterator __pos, size_type __n, const value_type& __x)
{ _M_fill_insert(__pos, __n, __x); }
void _M_fill_insert(iterator __pos, size_type __n, const value_type& __x);
#ifdef __STL_MEMBER_TEMPLATES
// Check whether it's an integral type. If so, it's not an iterator.
template <class _InputIterator>
void insert(iterator __pos, _InputIterator __first, _InputIterator __last) {
typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
_M_insert_dispatch(__pos, __first, __last, _Integral());
}
template <class _Integer>
void _M_insert_dispatch(iterator __pos, _Integer __n, _Integer __x,
__true_type) {
_M_fill_insert(__pos, (size_type) __n, (value_type) __x);
}
template <class _InputIterator>
void _M_insert_dispatch(iterator __pos,
_InputIterator __first, _InputIterator __last,
__false_type) {
insert(__pos, __first, __last, __ITERATOR_CATEGORY(__first));
}
#else /* __STL_MEMBER_TEMPLATES */
void insert(iterator __pos,
const value_type* __first, const value_type* __last);
void insert(iterator __pos,
const_iterator __first, const_iterator __last);
#endif /* __STL_MEMBER_TEMPLATES */
//改變容器大小
void resize(size_type __new_size, const value_type& __x) {
const size_type __len = size();
if (__new_size < __len)//新的大小較舊的小
erase(_M_start + __new_size, _M_finish);//擦除多余的元素
else//否則，填充新增的節點
insert(_M_finish, __new_size - __len, __x);
}
void resize(size_type new_size) { resize(new_size, value_type()); }
public:
//****************************
/* 擦除指定位置的元素
* iterator erase (iterator position);
* 擦除指定區間的元素
* iterator erase (iterator first, iterator last);
*/
//****************************
// Erase
iterator erase(iterator __pos) {
iterator __next = __pos;
++__next;
difference_type __index = __pos - _M_start;//擦除點之前元素個數
if (size_type(__index) < (this->size() >> 1)) {//若擦除點之前的元素個數較少
copy_backward(_M_start, __pos, __next);//向后移動擦除點之前的元素
pop_front();
}
else {
copy(__next, _M_finish, __pos);//否則，向前移動擦除點之后的元素
pop_back();
}
return _M_start + __index;
}
iterator erase(iterator __first, iterator __last);
void clear();
protected: // Internal construction/destruction
void _M_fill_initialize(const value_type& __value);
#ifdef __STL_MEMBER_TEMPLATES
template <class _InputIterator>
void _M_range_initialize(_InputIterator __first, _InputIterator __last,
input_iterator_tag);
template <class _ForwardIterator>
void _M_range_initialize(_ForwardIterator __first, _ForwardIterator __last,
forward_iterator_tag);
#endif /* __STL_MEMBER_TEMPLATES */
protected: // Internal push_* and pop_*
void _M_push_back_aux(const value_type&);
void _M_push_back_aux();
void _M_push_front_aux(const value_type&);
void _M_push_front_aux();
void _M_pop_back_aux();
void _M_pop_front_aux();
protected: // Internal insert functions
#ifdef __STL_MEMBER_TEMPLATES
template <class _InputIterator>
void insert(iterator __pos, _InputIterator __first, _InputIterator __last,
input_iterator_tag);
template <class _ForwardIterator>
void insert(iterator __pos,
_ForwardIterator __first, _ForwardIterator __last,
forward_iterator_tag);
#endif /* __STL_MEMBER_TEMPLATES */
iterator _M_insert_aux(iterator __pos, const value_type& __x);
iterator _M_insert_aux(iterator __pos);
void _M_insert_aux(iterator __pos, size_type __n, const value_type& __x);
#ifdef __STL_MEMBER_TEMPLATES
template <class _ForwardIterator>
void _M_insert_aux(iterator __pos,
_ForwardIterator __first, _ForwardIterator __last,
size_type __n);
#else /* __STL_MEMBER_TEMPLATES */
void _M_insert_aux(iterator __pos,
const value_type* __first, const value_type* __last,
size_type __n);
void _M_insert_aux(iterator __pos,
const_iterator __first, const_iterator __last,
size_type __n);
#endif /* __STL_MEMBER_TEMPLATES */
iterator _M_reserve_elements_at_front(size_type __n) {
size_type __vacancies = _M_start._M_cur - _M_start._M_first;
if (__n > __vacancies)
_M_new_elements_at_front(__n - __vacancies);
return _M_start - difference_type(__n);
}
iterator _M_reserve_elements_at_back(size_type __n) {
size_type __vacancies = (_M_finish._M_last - _M_finish._M_cur) - 1;
if (__n > __vacancies)
_M_new_elements_at_back(__n - __vacancies);
return _M_finish + difference_type(__n);
}
void _M_new_elements_at_front(size_type __new_elements);
void _M_new_elements_at_back(size_type __new_elements);
protected: // Allocation of _M_map and nodes
// Makes sure the _M_map has space for new nodes. Does not actually
// add the nodes. Can invalidate _M_map pointers. (And consequently,
// deque iterators.)
void _M_reserve_map_at_back (size_type __nodes_to_add = 1) {
//_M_map_size - (_M_finish._M_node - _M_map)表示map尾端節點的備用空間
if (__nodes_to_add + 1 > _M_map_size - (_M_finish._M_node - _M_map))
_M_reallocate_map(__nodes_to_add, false);
}
void _M_reserve_map_at_front (size_type __nodes_to_add = 1) {
//_M_start._M_node - _M_map表示map頭部節點的備用空間
if (__nodes_to_add > size_type(_M_start._M_node - _M_map))
_M_reallocate_map(__nodes_to_add, true);
}
void _M_reallocate_map(size_type __nodes_to_add, bool __add_at_front);
};
~~~
### deque容器的源碼完整剖析
~~~
/* deque是雙向隊列，可以在頭尾兩端插入或刪除元素；
* deque與vector最大的差異就是：
* 一、deque允許于常數時間內對頭端進行插入或刪除元素；
* 二、deque是分段連續線性空間，隨時可以增加一段新的空間；
* deque不像vector那樣，vector當內存不夠時，需重新分配/復制數據/釋放原始空間；
* 不過deque的迭代器設置比vector復雜，因為迭代器不能使用普通指針，因此盡量使用vector；
* 注：當對deque的元素進行排序時，為了提高效率，首先把deque數據復制到vector，
* 利用vector的排序算法(利用STL的sort算法)，排序之后再次復制回deque；
*/
#include <concept_checks.h>
#ifndef __SGI_STL_INTERNAL_DEQUE_H
#define __SGI_STL_INTERNAL_DEQUE_H
/* Class invariants:
* For any nonsingular iterator i:
* i.node is the address of an element in the map array. The
* contents of i.node is a pointer to the beginning of a node.
* i.first == *(i.node)
* i.last == i.first + node_size
* i.cur is a pointer in the range [i.first, i.last). NOTE:
* the implication of this is that i.cur is always a dereferenceable
* pointer, even if i is a past-the-end iterator.
* Start and Finish are always nonsingular iterators. NOTE: this means
* that an empty deque must have one node, and that a deque
* with N elements, where N is the buffer size, must have two nodes.
* For every node other than start.node and finish.node, every element
* in the node is an initialized object. If start.node == finish.node,
* then [start.cur, finish.cur) are initialized objects, and
* the elements outside that range are uninitialized storage. Otherwise,
* [start.cur, start.last) and [finish.first, finish.cur) are initialized
* objects, and [start.first, start.cur) and [finish.cur, finish.last)
* are uninitialized storage.
* [map, map + map_size) is a valid, non-empty range.
* [start.node, finish.node] is a valid range contained within
* [map, map + map_size).
* A pointer in the range [map, map + map_size) points to an allocated node
* if and only if the pointer is in the range [start.node, finish.node].
*/
/*
* In previous versions of deque, there was an extra template
* parameter so users could control the node size. This extension
* turns out to violate the C++ standard (it can be detected using
* template template parameters), and it has been removed.
*/
__STL_BEGIN_NAMESPACE
#if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
#pragma set woff 1174
#pragma set woff 1375
#endif
//* deque是分段連續線性空間，為了能夠像連續線性空間那樣訪問數據，
//* deque采用了一種中控方法map,map是塊連續的空間，其每個元素都是一個指針，
//* 指向一塊緩沖區，實質上map是T**；
//*********************************
// Note: this function is simply a kludge to work around several compilers'
// bugs in handling constant expressions.
//這個函數是方便不同編譯器處理常量表達式的bug
inline size_t __deque_buf_size(size_t __size) {
return __size < 512 ? size_t(512 / __size) : size_t(1);
}
//deque迭代器的設計
//*deque是分段連續的線性空間，迭代器設計時必須能夠進行operator++或operator--操作
//* 迭代器的功能：
//* 1、必須知道緩沖區的位置
//* 2、能夠判斷是否處于其所在緩沖區的邊界
//* 3、能夠知道其所在緩沖區當前所指位置的元素
//**********************
template <class _Tp, class _Ref, class _Ptr>
struct _Deque_iterator {
typedef _Deque_iterator<_Tp, _Tp&, _Tp*> iterator;
typedef _Deque_iterator<_Tp, const _Tp&, const _Tp*> const_iterator;
static size_t _S_buffer_size() { return __deque_buf_size(sizeof(_Tp)); }
typedef 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 _Tp**_Map_pointer;
typedef _Deque_iterator _Self;
//以下是迭代器設計的關鍵，訪問容器的節點
_Tp* _M_cur;//指向緩沖區當前的元素
_Tp* _M_first;//指向緩沖區的頭(起始地址)
_Tp* _M_last;//指向緩沖區的尾(結束地址)
_Map_pointer _M_node;//指向中控器的相應節點
_Deque_iterator(_Tp* __x, _Map_pointer __y)
: _M_cur(__x), _M_first(*__y),
_M_last(*__y + _S_buffer_size()), _M_node(__y) {}
_Deque_iterator() : _M_cur(0), _M_first(0), _M_last(0), _M_node(0) {}
_Deque_iterator(const iterator& __x)
: _M_cur(__x._M_cur), _M_first(__x._M_first),
_M_last(__x._M_last), _M_node(__x._M_node) {}
//**************************************
//***********以下是迭代器_Deque_iterator的操作************
//* 這些操作符的重載方便我們訪問容器的內容
//* 也是讓deque從接口看來是維護連續線性空間的關鍵
//**************************************
reference operator*() const { return *_M_cur; }//解除引用,返回當前元素
#ifndef __SGI_STL_NO_ARROW_OPERATOR
pointer operator->() const { return _M_cur; }
#endif /* __SGI_STL_NO_ARROW_OPERATOR */
//返回兩個迭代器之間的距離
difference_type operator-(const _Self& __x) const {
return difference_type(_S_buffer_size()) * (_M_node - __x._M_node - 1) +
(_M_cur - _M_first) + (__x._M_last - __x._M_cur);
}
//前綴自增++操作符重載
_Self& operator++() {
++_M_cur; //普通自增操作，移至下一個元素
if (_M_cur == _M_last) { //若已達到緩沖區的尾部
_M_set_node(_M_node + 1);//切換至下一緩沖區(節點)
_M_cur = _M_first; //的第一個元素
}
return *this;
}
//后綴自增++操作符重載
//返回當前迭代器的一個副本
_Self operator++(int) {
_Self __tmp = *this;//定義當前迭代器的一個副本
++*this;//這里前綴++不是普通的++操作，是上一步驟已經重載過的前綴++
return __tmp;
}
//前綴自減--操作符重載
//基本思想類似于前綴自增操作
_Self& operator--() {
if (_M_cur == _M_first) { //若是當前緩沖區的第一個元素
_M_set_node(_M_node - 1);//切換到上一個緩沖區
_M_cur = _M_last; //的尾部(即最后一個元素的下一個位置)
}
--_M_cur;//普通的自減操作，移至前一個元素
return *this;
}
//后綴自減--操作符重載
//返回當前迭代器的副本
_Self operator--(int) {
_Self __tmp = *this;//定義一個副本
--*this; //迭代器自減操作
return __tmp;
}
//以下實現隨機存取，迭代器可以直接跳躍n個距離
//將迭代器前移n個距離，當n負值時就為下面的operator-=操作
_Self& operator+=(difference_type __n)
{
difference_type __offset = __n + (_M_cur - _M_first);//定義一個中間變量
if (__offset >= 0 && __offset < difference_type(_S_buffer_size()))
//若前移n個距離后，目標依然在同一個緩沖區
//則直接前移n個距離
_M_cur += __n;
else {
//若前移n個距離后，目標超出該緩沖區范圍
//__offset / difference_type(_S_buffer_size())計算向后移動多少個緩沖區
//-difference_type((-__offset - 1) / _S_buffer_size()) - 1計算向前移動多少個緩沖區
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
{
_Self __tmp = *this;
//調用operator+=操作
return __tmp += __n;
}
//利用operator+=操作實現
_Self& operator-=(difference_type __n) { return *this += -__n; }
_Self operator-(difference_type __n) const {
_Self __tmp = *this;
return __tmp -= __n;
}
//返回指定位置的元素，即實現隨機存取
//該函數調用operator+，operator*
reference operator[](difference_type __n) const { return *(*this + __n); }
bool operator==(const _Self& __x) const { return _M_cur == __x._M_cur; }
bool operator!=(const _Self& __x) const { return !(*this == __x); }
bool operator<(const _Self& __x) const {
return (_M_node == __x._M_node) ?
(_M_cur < __x._M_cur) : (_M_node < __x._M_node);
}
bool operator>(const _Self& __x) const { return __x < *this; }
bool operator<=(const _Self& __x) const { return !(__x < *this); }
bool operator>=(const _Self& __x) const { return !(*this < __x); }
//調整到正確的緩沖區
//切換到正確的元素位置
void _M_set_node(_Map_pointer __new_node) {
_M_node = __new_node;//指向新的節點
_M_first = *__new_node;//指向新節點的頭部
_M_last = _M_first + difference_type(_S_buffer_size());//指向新節點的尾部
}
};
//operator+迭代器向前移動n個位置
template <class _Tp, class _Ref, class _Ptr>
inline _Deque_iterator<_Tp, _Ref, _Ptr>
operator+(ptrdiff_t __n, const _Deque_iterator<_Tp, _Ref, _Ptr>& __x)
{
return __x + __n;
}
#ifndef __STL_CLASS_PARTIAL_SPECIALIZATION
template <class _Tp, class _Ref, class _Ptr>
inline random_access_iterator_tag
iterator_category(const _Deque_iterator<_Tp,_Ref,_Ptr>&)
{
return random_access_iterator_tag();
}
template <class _Tp, class _Ref, class _Ptr>
inline _Tp* value_type(const _Deque_iterator<_Tp,_Ref,_Ptr>&) { return 0; }
template <class _Tp, class _Ref, class _Ptr>
inline ptrdiff_t* distance_type(const _Deque_iterator<_Tp,_Ref,_Ptr>&) {
return 0;
}
#endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */
// Deque base class. It has two purposes. First, its constructor
// and destructor allocate (but don't initialize) storage. This makes
// exception safety easier. Second, the base class encapsulates all of
// the differences between SGI-style allocators and standard-conforming
// allocators.
#ifdef __STL_USE_STD_ALLOCATORS
// Base class for ordinary allocators.
//這里只負責中控器節點內存管理
template <class _Tp, class _Alloc, bool __is_static>
class _Deque_alloc_base {
public:
typedef typename _Alloc_traits<_Tp,_Alloc>::allocator_type allocator_type;
allocator_type get_allocator() const { return _M_node_allocator; }
_Deque_alloc_base(const allocator_type& __a)
: _M_node_allocator(__a), _M_map_allocator(__a),
_M_map(0), _M_map_size(0)
{}
protected:
typedef typename _Alloc_traits<_Tp*, _Alloc>::allocator_type
_Map_allocator_type;
allocator_type _M_node_allocator;
_Map_allocator_type _M_map_allocator;
_Tp* _M_allocate_node() {
return _M_node_allocator.allocate(__deque_buf_size(sizeof(_Tp)));
}
void _M_deallocate_node(_Tp* __p) {
_M_node_allocator.deallocate(__p, __deque_buf_size(sizeof(_Tp)));
}
_Tp**_M_allocate_map(size_t __n)
{ return _M_map_allocator.allocate(__n); }
void _M_deallocate_map(_Tp**__p, size_t __n)
{ _M_map_allocator.deallocate(__p, __n); }
_Tp**_M_map; //指向中控器map
size_t _M_map_size;//中控器map可容納指針的個數
};
// Specialization for instanceless allocators.
template <class _Tp, class _Alloc>
class _Deque_alloc_base<_Tp, _Alloc, true>
{
public:
typedef typename _Alloc_traits<_Tp,_Alloc>::allocator_type allocator_type;
allocator_type get_allocator() const { return allocator_type(); }
_Deque_alloc_base(const allocator_type&) : _M_map(0), _M_map_size(0) {}
protected:
typedef typename _Alloc_traits<_Tp, _Alloc>::_Alloc_type _Node_alloc_type;
typedef typename _Alloc_traits<_Tp*, _Alloc>::_Alloc_type _Map_alloc_type;
_Tp* _M_allocate_node() {
return _Node_alloc_type::allocate(__deque_buf_size(sizeof(_Tp)));
}
void _M_deallocate_node(_Tp* __p) {
_Node_alloc_type::deallocate(__p, __deque_buf_size(sizeof(_Tp)));
}
_Tp**_M_allocate_map(size_t __n)
{ return _Map_alloc_type::allocate(__n); }
void _M_deallocate_map(_Tp**__p, size_t __n)
{ _Map_alloc_type::deallocate(__p, __n); }
_Tp**_M_map;
size_t _M_map_size;
};
template <class _Tp, class _Alloc>
class _Deque_base
: public _Deque_alloc_base<_Tp,_Alloc,
_Alloc_traits<_Tp, _Alloc>::_S_instanceless>
{
public:
typedef _Deque_alloc_base<_Tp,_Alloc,
_Alloc_traits<_Tp, _Alloc>::_S_instanceless>
_Base;
typedef typename _Base::allocator_type allocator_type;
typedef _Deque_iterator<_Tp,_Tp&,_Tp*> iterator;
typedef _Deque_iterator<_Tp,const _Tp&,const _Tp*> const_iterator;
//參數__num_elements表示緩沖區(節點)存儲元素的個數
_Deque_base(const allocator_type& __a, size_t __num_elements)
: _Base(__a), _M_start(), _M_finish()
{ _M_initialize_map(__num_elements); }
_Deque_base(const allocator_type& __a)
: _Base(__a), _M_start(), _M_finish() {}
~_Deque_base();
protected:
void _M_initialize_map(size_t);
void _M_create_nodes(_Tp**__nstart, _Tp**__nfinish);
void _M_destroy_nodes(_Tp**__nstart, _Tp**__nfinish);
enum { _S_initial_map_size = 8 };//中控器map默認大小
protected:
iterator _M_start;//指向第一個緩沖區的第一個元素
iterator _M_finish;//指向最后一個緩沖區的最后一個元素的下一個位置
};
#else /* __STL_USE_STD_ALLOCATORS */
template <class _Tp, class _Alloc>
class _Deque_base {
public:
typedef _Deque_iterator<_Tp,_Tp&,_Tp*> iterator;
typedef _Deque_iterator<_Tp,const _Tp&,const _Tp*> const_iterator;
typedef _Alloc allocator_type;
allocator_type get_allocator() const { return allocator_type(); }
_Deque_base(const allocator_type&, size_t __num_elements)
: _M_map(0), _M_map_size(0), _M_start(), _M_finish() {
_M_initialize_map(__num_elements);
}
_Deque_base(const allocator_type&)
: _M_map(0), _M_map_size(0), _M_start(), _M_finish() {}
~_Deque_base();
protected:
void _M_initialize_map(size_t);
void _M_create_nodes(_Tp**__nstart, _Tp**__nfinish);
void _M_destroy_nodes(_Tp**__nstart, _Tp**__nfinish);
enum { _S_initial_map_size = 8 };
protected:
_Tp**_M_map;
size_t _M_map_size;
iterator _M_start;
iterator _M_finish;
typedef simple_alloc<_Tp, _Alloc> _Node_alloc_type;
typedef simple_alloc<_Tp*, _Alloc> _Map_alloc_type;
_Tp* _M_allocate_node()
{ return _Node_alloc_type::allocate(__deque_buf_size(sizeof(_Tp))); }
void _M_deallocate_node(_Tp* __p)
{ _Node_alloc_type::deallocate(__p, __deque_buf_size(sizeof(_Tp))); }
_Tp**_M_allocate_map(size_t __n)
{ return _Map_alloc_type::allocate(__n); }
void _M_deallocate_map(_Tp**__p, size_t __n)
{ _Map_alloc_type::deallocate(__p, __n); }
};
#endif /* __STL_USE_STD_ALLOCATORS */
// Non-inline member functions from _Deque_base.
template <class _Tp, class _Alloc>
_Deque_base<_Tp,_Alloc>::~_Deque_base() {
if (_M_map) {
_M_destroy_nodes(_M_start._M_node, _M_finish._M_node + 1);
_M_deallocate_map(_M_map, _M_map_size);
}
}
template <class _Tp, class _Alloc>
void
_Deque_base<_Tp,_Alloc>::_M_initialize_map(size_t __num_elements)
{
//根據存儲元素個數和緩沖區大小決定中控器map容量
size_t __num_nodes =
__num_elements / __deque_buf_size(sizeof(_Tp)) + 1;
//在默認值和計算值中，取其最大者
//map管理的節點，最少是8個，最多是所需節點數加上2個
//前后各預留一個，方便擴充
_M_map_size = max((size_t) _S_initial_map_size, __num_nodes + 2);
_M_map = _M_allocate_map(_M_map_size);//分配map內存空間
//讓start.node和finish.node指向map的內部，方便map的兩端擴充
_Tp**__nstart = _M_map + (_M_map_size - __num_nodes) / 2;
_Tp**__nfinish = __nstart + __num_nodes;
__STL_TRY {
_M_create_nodes(__nstart, __nfinish);//分配map實際存儲的節點數空間
}
__STL_UNWIND((_M_deallocate_map(_M_map, _M_map_size),
_M_map = 0, _M_map_size = 0));
_M_start._M_set_node(__nstart);//使迭代器start指向正確的位置
_M_finish._M_set_node(__nfinish - 1);//使迭代器start指向正確的位置
_M_start._M_cur = _M_start._M_first;//初始化start.cur,使其指向第一個緩沖區的第一個元素
//初始化finish.cur,使其指向最后一個緩沖區的最后一個元素
_M_finish._M_cur = _M_finish._M_first +
__num_elements % __deque_buf_size(sizeof(_Tp));
}
//分配map實際存儲的節點數空間
template <class _Tp, class _Alloc>
void _Deque_base<_Tp,_Alloc>::_M_create_nodes(_Tp**__nstart, _Tp**__nfinish)
{
_Tp**__cur;
__STL_TRY {
for (__cur = __nstart; __cur < __nfinish; ++__cur)
*__cur = _M_allocate_node();
}
__STL_UNWIND(_M_destroy_nodes(__nstart, __cur));
}
//釋放map的節點數空間
template <class _Tp, class _Alloc>
void
_Deque_base<_Tp,_Alloc>::_M_destroy_nodes(_Tp**__nstart, _Tp**__nfinish)
{
for (_Tp**__n = __nstart; __n < __nfinish; ++__n)
_M_deallocate_node(*__n);
}
//deque容器的定義
//配置器默認為第二級配置器
template <class _Tp, class _Alloc = __STL_DEFAULT_ALLOCATOR(_Tp) >
class deque : protected _Deque_base<_Tp, _Alloc> {
// requirements:
__STL_CLASS_REQUIRES(_Tp, _Assignable);
typedef _Deque_base<_Tp, _Alloc> _Base;
public: // Basic types
typedef _Tp value_type;
typedef value_type* pointer;
typedef const value_type* const_pointer;
typedef value_type& reference;
typedef const value_type& const_reference;
typedef size_t size_type;
typedef ptrdiff_t difference_type;
typedef typename _Base::allocator_type allocator_type;
allocator_type get_allocator() const { return _Base::get_allocator(); }
public: // Iterators
typedef typename _Base::iterator iterator;
typedef typename _Base::const_iterator const_iterator;
#ifdef __STL_CLASS_PARTIAL_SPECIALIZATION
typedef reverse_iterator<const_iterator> const_reverse_iterator;
typedef reverse_iterator<iterator> reverse_iterator;
#else /* __STL_CLASS_PARTIAL_SPECIALIZATION */
typedef reverse_iterator<const_iterator, value_type, const_reference,
difference_type>
const_reverse_iterator;
typedef reverse_iterator<iterator, value_type, reference, difference_type>
reverse_iterator;
#endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */
protected: // Internal typedefs
typedef pointer* _Map_pointer;
static size_t _S_buffer_size() { return __deque_buf_size(sizeof(_Tp)); }
protected:
//繼承基類的成員
#ifdef __STL_USE_NAMESPACES
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;
//下面是deque的數據結構
using _Base::_M_map;
using _Base::_M_map_size;
using _Base::_M_start;
using _Base::_M_finish;
#endif /* __STL_USE_NAMESPACES */
public: // Basic accessors
iterator begin() { return _M_start; }
iterator end() { return _M_finish; }
const_iterator begin() const { return _M_start; }
const_iterator end() const { return _M_finish; }
reverse_iterator rbegin() { return reverse_iterator(_M_finish); }
reverse_iterator rend() { return reverse_iterator(_M_start); }
const_reverse_iterator rbegin() const
{ return const_reverse_iterator(_M_finish); }
const_reverse_iterator rend() const
{ return const_reverse_iterator(_M_start); }
//隨機訪問，這里調用迭代器的重載操作operator[]
reference operator[](size_type __n)
{ return _M_start[difference_type(__n)]; }
const_reference operator[](size_type __n) const
{ return _M_start[difference_type(__n)]; }
//越界檢查
#ifdef __STL_THROW_RANGE_ERRORS
void _M_range_check(size_type __n) const {
if (__n >= this->size())
__stl_throw_range_error("deque");
}
//訪問指定位置的元素
reference at(size_type __n)
{ _M_range_check(__n); return (*this)[__n]; }
const_reference at(size_type __n) const
{ _M_range_check(__n); return (*this)[__n]; }
#endif /* __STL_THROW_RANGE_ERRORS */
//返回第一個緩沖區的第一個元素
//調用迭代器的operator*
reference front() { return *_M_start; }
//返回最后一個緩沖區的最后一個元素
reference back() {
iterator __tmp = _M_finish;
--__tmp;//調用迭代器的operator--
return *__tmp;//調用迭代器的operator*
}
const_reference front() const { return *_M_start; }
const_reference back() const {
const_iterator __tmp = _M_finish;
--__tmp;
return *__tmp;
}
//返回deque容器大小，即容器元素個數
//調用迭代器的operator-
size_type size() const { return _M_finish - _M_start; }
size_type max_size() const { return size_type(-1); }
//判斷容器是否為空
/*Start and Finish are always nonsingular iterators. NOTE: this means
* that an empty deque must have one node
*/
bool empty() const { return _M_finish == _M_start; }
public:
//******************************
//* 以下是構造函數和析構函數
//* 默認構造函數
//* explicit deque( const Allocator& alloc = Allocator() );
//* 容器大小為count個初始值為value的元素
//* explicit deque( size_type count,
//* const T& value = T(),
//* const Allocator& alloc = Allocator());
//* deque( size_type count,
//* const T& value,
//* const Allocator& alloc = Allocator());
//* 容器大小為count個默認值的元素
//* explicit deque( size_type count );
//* 拷貝構造函數
//* deque( const deque& other );
//* deque( const deque& other, const Allocator& alloc );
//* 初始值為[first,last)內容的容器
//* template< class InputIt >
//* deque( InputIt first, InputIt last,
//* const Allocator& alloc = Allocator() );
//* 析構函數
//* ~deque()
//*
//****************************
// Constructor, destructor.
explicit deque(const allocator_type& __a = allocator_type())
: _Base(__a, 0) {}
deque(const deque& __x) : _Base(__x.get_allocator(), __x.size())
{ uninitialized_copy(__x.begin(), __x.end(), _M_start); }
deque(size_type __n, const value_type& __value,
const allocator_type& __a = allocator_type()) : _Base(__a, __n)
{ _M_fill_initialize(__value); }
explicit deque(size_type __n) : _Base(allocator_type(), __n)
{ _M_fill_initialize(value_type()); }
#ifdef __STL_MEMBER_TEMPLATES
// Check whether it's an integral type. If so, it's not an iterator.
template <class _InputIterator>
deque(_InputIterator __first, _InputIterator __last,
const allocator_type& __a = allocator_type()) : _Base(__a) {
typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
_M_initialize_dispatch(__first, __last, _Integral());
}
template <class _Integer>
void _M_initialize_dispatch(_Integer __n, _Integer __x, __true_type) {
_M_initialize_map(__n);
_M_fill_initialize(__x);
}
template <class _InputIter>
void _M_initialize_dispatch(_InputIter __first, _InputIter __last,
__false_type) {
_M_range_initialize(__first, __last, __ITERATOR_CATEGORY(__first));
}
#else /* __STL_MEMBER_TEMPLATES */
deque(const value_type* __first, const value_type* __last,
const allocator_type& __a = allocator_type())
: _Base(__a, __last - __first)
{ uninitialized_copy(__first, __last, _M_start); }
deque(const_iterator __first, const_iterator __last,
const allocator_type& __a = allocator_type())
: _Base(__a, __last - __first)
{ uninitialized_copy(__first, __last, _M_start); }
#endif /* __STL_MEMBER_TEMPLATES */
~deque() { destroy(_M_start, _M_finish); }
//構造函數和析構函數定義結束
//容器對象賦值操作
deque& operator= (const deque& __x) {
const size_type __len = size();
if (&__x != this) {
if (__len >= __x.size())
erase(copy(__x.begin(), __x.end(), _M_start), _M_finish);
else {
const_iterator __mid = __x.begin() + difference_type(__len);
copy(__x.begin(), __mid, _M_start);
insert(_M_finish, __mid, __x.end());
}
}
return *this;
}
//交換兩個容器的內容
//這里實際上并沒有交換具體的元素，而是交換迭代器
//和中控器信息
void swap(deque& __x) {
__STD::swap(_M_start, __x._M_start);
__STD::swap(_M_finish, __x._M_finish);
__STD::swap(_M_map, __x._M_map);
__STD::swap(_M_map_size, __x._M_map_size);
}
public:
// assign(), a generalized assignment member function. Two
// versions: one that takes a count, and one that takes a range.
// The range version is a member template, so we dispatch on whether
// or not the type is an integer.
void _M_fill_assign(size_type __n, const _Tp& __val) {
if (__n > size()) {//若新的大小比容器原來的大
fill(begin(), end(), __val);//把原來容器填充為val
insert(end(), __n - size(), __val);//容器追加填充值
}
else {//若新的大小比容器原來的小
erase(begin() + __n, end());//則擦除多余的內容
fill(begin(), end(), __val);//填充值為val覆蓋原來的內容
}
}
//對外接口的assign第一個版本
void assign(size_type __n, const _Tp& __val) {
_M_fill_assign(__n, __val);
}
#ifdef __STL_MEMBER_TEMPLATES
//對外接口的assign第二個版本
//采用迭代器的traist技術
template <class _InputIterator>
void assign(_InputIterator __first, _InputIterator __last) {
typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
_M_assign_dispatch(__first, __last, _Integral());
}
private: // helper functions for assign()
template <class _Integer>
void _M_assign_dispatch(_Integer __n, _Integer __val, __true_type)
{ _M_fill_assign((size_type) __n, (_Tp) __val); }
template <class _InputIterator>
void _M_assign_dispatch(_InputIterator __first, _InputIterator __last,
__false_type) {
_M_assign_aux(__first, __last, __ITERATOR_CATEGORY(__first));
}
template <class _InputIterator>
void _M_assign_aux(_InputIterator __first, _InputIterator __last,
input_iterator_tag);
template <class _ForwardIterator>
void _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last,
forward_iterator_tag) {
size_type __len = 0;
distance(__first, __last, __len);//計算兩個輸入迭代器的距離
if (__len > size()) {//若輸入迭代器距離比待賦值容器大小還大
_ForwardIterator __mid = __first;
advance(__mid, size());//將mid向前移動size()個距離
copy(__first, __mid, begin());//先復制[first,mid)數據
insert(end(), __mid, __last);//插入剩下的數據
}
else//否則擦除多余的數據
erase(copy(__first, __last, begin()), end());
}
#endif /* __STL_MEMBER_TEMPLATES */
public: // push_* and pop_*
//在容器尾部加數據
void push_back(const value_type& __t) {
//若當前緩沖區存在可用空間
if (_M_finish._M_cur != _M_finish._M_last - 1) {
construct(_M_finish._M_cur, __t);//直接構造對象
++_M_finish._M_cur;//調整指針所指位置
}
else//若當前緩沖區不存在可用空間
//需分配一段新的連續空間
_M_push_back_aux(__t);
}
void push_back() {
if (_M_finish._M_cur != _M_finish._M_last - 1) {
construct(_M_finish._M_cur);
++_M_finish._M_cur;
}
else
_M_push_back_aux();
}
void push_front(const value_type& __t) {
if (_M_start._M_cur != _M_start._M_first) {
construct(_M_start._M_cur - 1, __t);
--_M_start._M_cur;
}
else
_M_push_front_aux(__t);
}
void push_front() {
if (_M_start._M_cur != _M_start._M_first) {
construct(_M_start._M_cur - 1);
--_M_start._M_cur;
}
else
_M_push_front_aux();
}
void pop_back() {
if (_M_finish._M_cur != _M_finish._M_first) {
--_M_finish._M_cur;
destroy(_M_finish._M_cur);
}
else
_M_pop_back_aux();
}
void pop_front() {
if (_M_start._M_cur != _M_start._M_last - 1) {
destroy(_M_start._M_cur);
++_M_start._M_cur;
}
else
_M_pop_front_aux();
}
public:
//*******************************
/* 在指定位置之前插入數據
*******************************
* iterator insert (iterator position, const value_type& val);
*
* void insert (iterator position, size_type n, const value_type& val);
*
* template <class InputIterator>
* void insert (iterator position, InputIterator first, InputIterator last);
*/
//*******************************
// Insert
iterator insert(iterator position, const value_type& __x) {
if (position._M_cur == _M_start._M_cur) {//若當前位置為deque.begin()
push_front(__x);//則在容器頭部插入數據
return _M_start;
}
else if (position._M_cur == _M_finish._M_cur) {//若當前位置為deque.end()
push_back(__x);
iterator __tmp = _M_finish;
--__tmp;
return __tmp;
}
else {//否則在容器直接插入數據
return _M_insert_aux(position, __x);
}
}
iterator insert(iterator __position)
{ return insert(__position, value_type()); }
void insert(iterator __pos, size_type __n, const value_type& __x)
{ _M_fill_insert(__pos, __n, __x); }
void _M_fill_insert(iterator __pos, size_type __n, const value_type& __x);
#ifdef __STL_MEMBER_TEMPLATES
// Check whether it's an integral type. If so, it's not an iterator.
template <class _InputIterator>
void insert(iterator __pos, _InputIterator __first, _InputIterator __last) {
typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
_M_insert_dispatch(__pos, __first, __last, _Integral());
}
template <class _Integer>
void _M_insert_dispatch(iterator __pos, _Integer __n, _Integer __x,
__true_type) {
_M_fill_insert(__pos, (size_type) __n, (value_type) __x);
}
template <class _InputIterator>
void _M_insert_dispatch(iterator __pos,
_InputIterator __first, _InputIterator __last,
__false_type) {
insert(__pos, __first, __last, __ITERATOR_CATEGORY(__first));
}
#else /* __STL_MEMBER_TEMPLATES */
void insert(iterator __pos,
const value_type* __first, const value_type* __last);
void insert(iterator __pos,
const_iterator __first, const_iterator __last);
#endif /* __STL_MEMBER_TEMPLATES */
//改變容器大小
void resize(size_type __new_size, const value_type& __x) {
const size_type __len = size();
if (__new_size < __len)//新的大小較舊的小
erase(_M_start + __new_size, _M_finish);//擦除多余的元素
else//否則，填充新增的節點
insert(_M_finish, __new_size - __len, __x);
}
void resize(size_type new_size) { resize(new_size, value_type()); }
public:
//****************************
/* 擦除指定位置的元素
* iterator erase (iterator position);
* 擦除指定區間的元素
* iterator erase (iterator first, iterator last);
*/
//****************************
// Erase
iterator erase(iterator __pos) {
iterator __next = __pos;
++__next;
difference_type __index = __pos - _M_start;//擦除點之前元素個數
if (size_type(__index) < (this->size() >> 1)) {//若擦除點之前的元素個數較少
copy_backward(_M_start, __pos, __next);//向后移動擦除點之前的元素
pop_front();
}
else {
copy(__next, _M_finish, __pos);//否則，向前移動擦除點之后的元素
pop_back();
}
return _M_start + __index;
}
iterator erase(iterator __first, iterator __last);
void clear();
protected: // Internal construction/destruction
void _M_fill_initialize(const value_type& __value);
#ifdef __STL_MEMBER_TEMPLATES
template <class _InputIterator>
void _M_range_initialize(_InputIterator __first, _InputIterator __last,
input_iterator_tag);
template <class _ForwardIterator>
void _M_range_initialize(_ForwardIterator __first, _ForwardIterator __last,
forward_iterator_tag);
#endif /* __STL_MEMBER_TEMPLATES */
protected: // Internal push_* and pop_*
void _M_push_back_aux(const value_type&);
void _M_push_back_aux();
void _M_push_front_aux(const value_type&);
void _M_push_front_aux();
void _M_pop_back_aux();
void _M_pop_front_aux();
protected: // Internal insert functions
#ifdef __STL_MEMBER_TEMPLATES
template <class _InputIterator>
void insert(iterator __pos, _InputIterator __first, _InputIterator __last,
input_iterator_tag);
template <class _ForwardIterator>
void insert(iterator __pos,
_ForwardIterator __first, _ForwardIterator __last,
forward_iterator_tag);
#endif /* __STL_MEMBER_TEMPLATES */
iterator _M_insert_aux(iterator __pos, const value_type& __x);
iterator _M_insert_aux(iterator __pos);
void _M_insert_aux(iterator __pos, size_type __n, const value_type& __x);
#ifdef __STL_MEMBER_TEMPLATES
template <class _ForwardIterator>
void _M_insert_aux(iterator __pos,
_ForwardIterator __first, _ForwardIterator __last,
size_type __n);
#else /* __STL_MEMBER_TEMPLATES */
void _M_insert_aux(iterator __pos,
const value_type* __first, const value_type* __last,
size_type __n);
void _M_insert_aux(iterator __pos,
const_iterator __first, const_iterator __last,
size_type __n);
#endif /* __STL_MEMBER_TEMPLATES */
iterator _M_reserve_elements_at_front(size_type __n) {
size_type __vacancies = _M_start._M_cur - _M_start._M_first;
if (__n > __vacancies)
_M_new_elements_at_front(__n - __vacancies);
return _M_start - difference_type(__n);
}
iterator _M_reserve_elements_at_back(size_type __n) {
size_type __vacancies = (_M_finish._M_last - _M_finish._M_cur) - 1;
if (__n > __vacancies)
_M_new_elements_at_back(__n - __vacancies);
return _M_finish + difference_type(__n);
}
void _M_new_elements_at_front(size_type __new_elements);
void _M_new_elements_at_back(size_type __new_elements);
protected: // Allocation of _M_map and nodes
// Makes sure the _M_map has space for new nodes. Does not actually
// add the nodes. Can invalidate _M_map pointers. (And consequently,
// deque iterators.)
void _M_reserve_map_at_back (size_type __nodes_to_add = 1) {
//_M_map_size - (_M_finish._M_node - _M_map)表示map尾端節點的備用空間
if (__nodes_to_add + 1 > _M_map_size - (_M_finish._M_node - _M_map))
_M_reallocate_map(__nodes_to_add, false);
}
void _M_reserve_map_at_front (size_type __nodes_to_add = 1) {
//_M_start._M_node - _M_map表示map頭部節點的備用空間
if (__nodes_to_add > size_type(_M_start._M_node - _M_map))
_M_reallocate_map(__nodes_to_add, true);
}
void _M_reallocate_map(size_type __nodes_to_add, bool __add_at_front);
};
// Non-inline member functions
#ifdef __STL_MEMBER_TEMPLATES
template <class _Tp, class _Alloc>
template <class _InputIter>
void deque<_Tp, _Alloc>
::_M_assign_aux(_InputIter __first, _InputIter __last, input_iterator_tag)
{
iterator __cur = begin();
for ( ; __first != __last && __cur != end(); ++__cur, ++__first)
*__cur = *__first;
if (__first == __last)//若當前容器比輸入迭代器距離大
erase(__cur, end());//擦除多余的數據
else//否則插入剩下的數據
insert(end(), __first, __last);
}
#endif /* __STL_MEMBER_TEMPLATES */
template <class _Tp, class _Alloc>
void deque<_Tp, _Alloc>::_M_fill_insert(iterator __pos,
size_type __n, const value_type& __x)
{
if (__pos._M_cur == _M_start._M_cur) {//若插入點在容器頭部
iterator __new_start = _M_reserve_elements_at_front(__n);
__STL_TRY {
uninitialized_fill(__new_start, _M_start, __x);
_M_start = __new_start;
}
__STL_UNWIND(_M_destroy_nodes(__new_start._M_node, _M_start._M_node));
}
else if (__pos._M_cur == _M_finish._M_cur) {//若插入點在容器尾部
iterator __new_finish = _M_reserve_elements_at_back(__n);
__STL_TRY {
uninitialized_fill(_M_finish, __new_finish, __x);
_M_finish = __new_finish;
}
__STL_UNWIND(_M_destroy_nodes(_M_finish._M_node + 1,
__new_finish._M_node + 1));
}
else
_M_insert_aux(__pos, __n, __x);
}
#ifndef __STL_MEMBER_TEMPLATES
template <class _Tp, class _Alloc>
void deque<_Tp, _Alloc>::insert(iterator __pos,
const value_type* __first,
const value_type* __last) {
size_type __n = __last - __first;
if (__pos._M_cur == _M_start._M_cur) {
iterator __new_start = _M_reserve_elements_at_front(__n);
__STL_TRY {
uninitialized_copy(__first, __last, __new_start);
_M_start = __new_start;
}
__STL_UNWIND(_M_destroy_nodes(__new_start._M_node, _M_start._M_node));
}
else if (__pos._M_cur == _M_finish._M_cur) {
iterator __new_finish = _M_reserve_elements_at_back(__n);
__STL_TRY {
uninitialized_copy(__first, __last, _M_finish);
_M_finish = __new_finish;
}
__STL_UNWIND(_M_destroy_nodes(_M_finish._M_node + 1,
__new_finish._M_node + 1));
}
else
_M_insert_aux(__pos, __first, __last, __n);
}
template <class _Tp, class _Alloc>
void deque<_Tp,_Alloc>::insert(iterator __pos,
const_iterator __first, const_iterator __last)
{
size_type __n = __last - __first;
if (__pos._M_cur == _M_start._M_cur) {
iterator __new_start = _M_reserve_elements_at_front(__n);
__STL_TRY {
uninitialized_copy(__first, __last, __new_start);
_M_start = __new_start;
}
__STL_UNWIND(_M_destroy_nodes(__new_start._M_node, _M_start._M_node));
}
else if (__pos._M_cur == _M_finish._M_cur) {
iterator __new_finish = _M_reserve_elements_at_back(__n);
__STL_TRY {
uninitialized_copy(__first, __last, _M_finish);
_M_finish = __new_finish;
}
__STL_UNWIND(_M_destroy_nodes(_M_finish._M_node + 1,
__new_finish._M_node + 1));
}
else
_M_insert_aux(__pos, __first, __last, __n);
}
#endif /* __STL_MEMBER_TEMPLATES */
template <class _Tp, class _Alloc>
typename deque<_Tp,_Alloc>::iterator
deque<_Tp,_Alloc>::erase(iterator __first, iterator __last)
{
if (__first == _M_start && __last == _M_finish) {//若擦除整個容器內容
clear();
return _M_finish;
}
else {
difference_type __n = __last - __first;
difference_type __elems_before = __first - _M_start;
if (__elems_before < difference_type((this->size() - __n) / 2)) {
copy_backward(_M_start, __first, __last);
iterator __new_start = _M_start + __n;
destroy(_M_start, __new_start);
_M_destroy_nodes(__new_start._M_node, _M_start._M_node);
_M_start = __new_start;
}
else {
copy(__last, _M_finish, __first);
iterator __new_finish = _M_finish - __n;
destroy(__new_finish, _M_finish);
_M_destroy_nodes(__new_finish._M_node + 1, _M_finish._M_node + 1);
_M_finish = __new_finish;
}
return _M_start + __elems_before;
}
}
//清空容器內容
template <class _Tp, class _Alloc>
void deque<_Tp,_Alloc>::clear()
{
//首先清空緩沖區是滿數據的節點
for (_Map_pointer __node = _M_start._M_node + 1;
__node < _M_finish._M_node;
++__node) {
destroy(*__node, *__node + _S_buffer_size());
_M_deallocate_node(*__node);
}
//清除緩沖區還存在可用空間的節點，即只存儲部分數據
if (_M_start._M_node != _M_finish._M_node) {
destroy(_M_start._M_cur, _M_start._M_last);
destroy(_M_finish._M_first, _M_finish._M_cur);
_M_deallocate_node(_M_finish._M_first);
}
else
destroy(_M_start._M_cur, _M_finish._M_cur);
_M_finish = _M_start;//表示容器為空
}
// Precondition: _M_start and _M_finish have already been initialized,
// but none of the deque's elements have yet been constructed.
template <class _Tp, class _Alloc>
void deque<_Tp,_Alloc>::_M_fill_initialize(const value_type& __value) {
_Map_pointer __cur;
__STL_TRY {//為每個節點的緩沖區設置初值
for (__cur = _M_start._M_node; __cur < _M_finish._M_node; ++__cur)
uninitialized_fill(*__cur, *__cur + _S_buffer_size(), __value);
//最后一個緩沖區必須單獨設置初值，因為可能存在可用空間
uninitialized_fill(_M_finish._M_first, _M_finish._M_cur, __value);
}
__STL_UNWIND(destroy(_M_start, iterator(*__cur, __cur)));
}
#ifdef __STL_MEMBER_TEMPLATES
template <class _Tp, class _Alloc> template <class _InputIterator>
void deque<_Tp,_Alloc>::_M_range_initialize(_InputIterator __first,
_InputIterator __last,
input_iterator_tag)
{
_M_initialize_map(0);
__STL_TRY {
for ( ; __first != __last; ++__first)
push_back(*__first);
}
__STL_UNWIND(clear());
}
template <class _Tp, class _Alloc> template <class _ForwardIterator>
void deque<_Tp,_Alloc>::_M_range_initialize(_ForwardIterator __first,
_ForwardIterator __last,
forward_iterator_tag)
{
size_type __n = 0;
distance(__first, __last, __n);
_M_initialize_map(__n);
_Map_pointer __cur_node;
__STL_TRY {
for (__cur_node = _M_start._M_node;
__cur_node < _M_finish._M_node;
++__cur_node) {
_ForwardIterator __mid = __first;
advance(__mid, _S_buffer_size());
uninitialized_copy(__first, __mid, *__cur_node);
__first = __mid;
}
uninitialized_copy(__first, __last, _M_finish._M_first);
}
__STL_UNWIND(destroy(_M_start, iterator(*__cur_node, __cur_node)));
}
#endif /* __STL_MEMBER_TEMPLATES */
// Called only if _M_finish._M_cur == _M_finish._M_last - 1.
template <class _Tp, class _Alloc>
void deque<_Tp,_Alloc>::_M_push_back_aux(const value_type& __t)
{
value_type __t_copy = __t;
_M_reserve_map_at_back();//調整map
*(_M_finish._M_node + 1) = _M_allocate_node();//分配一個新的節點
__STL_TRY {
construct(_M_finish._M_cur, __t_copy);
_M_finish._M_set_node(_M_finish._M_node + 1);
_M_finish._M_cur = _M_finish._M_first;
}
__STL_UNWIND(_M_deallocate_node(*(_M_finish._M_node + 1)));
}
// Called only if _M_finish._M_cur == _M_finish._M_last - 1.
template <class _Tp, class _Alloc>
void deque<_Tp,_Alloc>::_M_push_back_aux()
{
_M_reserve_map_at_back();
*(_M_finish._M_node + 1) = _M_allocate_node();
__STL_TRY {
construct(_M_finish._M_cur);
_M_finish._M_set_node(_M_finish._M_node + 1);
_M_finish._M_cur = _M_finish._M_first;
}
__STL_UNWIND(_M_deallocate_node(*(_M_finish._M_node + 1)));
}
// Called only if _M_start._M_cur == _M_start._M_first.
template <class _Tp, class _Alloc>
void deque<_Tp,_Alloc>::_M_push_front_aux(const value_type& __t)
{
value_type __t_copy = __t;
_M_reserve_map_at_front();
*(_M_start._M_node - 1) = _M_allocate_node();
__STL_TRY {
_M_start._M_set_node(_M_start._M_node - 1);
_M_start._M_cur = _M_start._M_last - 1;
construct(_M_start._M_cur, __t_copy);
}
__STL_UNWIND((++_M_start, _M_deallocate_node(*(_M_start._M_node - 1))));
}
// Called only if _M_start._M_cur == _M_start._M_first.
template <class _Tp, class _Alloc>
void deque<_Tp,_Alloc>::_M_push_front_aux()
{
_M_reserve_map_at_front();
*(_M_start._M_node - 1) = _M_allocate_node();
__STL_TRY {
_M_start._M_set_node(_M_start._M_node - 1);
_M_start._M_cur = _M_start._M_last - 1;
construct(_M_start._M_cur);
}
__STL_UNWIND((++_M_start, _M_deallocate_node(*(_M_start._M_node - 1))));
}
// Called only if _M_finish._M_cur == _M_finish._M_first.
template <class _Tp, class _Alloc>
void deque<_Tp,_Alloc>::_M_pop_back_aux()
{
_M_deallocate_node(_M_finish._M_first);
_M_finish._M_set_node(_M_finish._M_node - 1);
_M_finish._M_cur = _M_finish._M_last - 1;
destroy(_M_finish._M_cur);
}
// Called only if _M_start._M_cur == _M_start._M_last - 1. Note that
// if the deque has at least one element (a precondition for this member
// function), and if _M_start._M_cur == _M_start._M_last, then the deque
// must have at least two nodes.
template <class _Tp, class _Alloc>
void deque<_Tp,_Alloc>::_M_pop_front_aux()
{
destroy(_M_start._M_cur);
_M_deallocate_node(_M_start._M_first);
_M_start._M_set_node(_M_start._M_node + 1);
_M_start._M_cur = _M_start._M_first;
}
#ifdef __STL_MEMBER_TEMPLATES
template <class _Tp, class _Alloc> template <class _InputIterator>
void deque<_Tp,_Alloc>::insert(iterator __pos,
_InputIterator __first, _InputIterator __last,
input_iterator_tag)
{
copy(__first, __last, inserter(*this, __pos));
}
template <class _Tp, class _Alloc> template <class _ForwardIterator>
void
deque<_Tp,_Alloc>::insert(iterator __pos,
_ForwardIterator __first, _ForwardIterator __last,
forward_iterator_tag) {
size_type __n = 0;
distance(__first, __last, __n);
if (__pos._M_cur == _M_start._M_cur) {
iterator __new_start = _M_reserve_elements_at_front(__n);
__STL_TRY {
uninitialized_copy(__first, __last, __new_start);
_M_start = __new_start;
}
__STL_UNWIND(_M_destroy_nodes(__new_start._M_node, _M_start._M_node));
}
else if (__pos._M_cur == _M_finish._M_cur) {
iterator __new_finish = _M_reserve_elements_at_back(__n);
__STL_TRY {
uninitialized_copy(__first, __last, _M_finish);
_M_finish = __new_finish;
}
__STL_UNWIND(_M_destroy_nodes(_M_finish._M_node + 1,
__new_finish._M_node + 1));
}
else
_M_insert_aux(__pos, __first, __last, __n);
}
#endif /* __STL_MEMBER_TEMPLATES */
template <class _Tp, class _Alloc>
typename deque<_Tp, _Alloc>::iterator
deque<_Tp,_Alloc>::_M_insert_aux(iterator __pos, const value_type& __x)
{
difference_type __index = __pos - _M_start;//計算插入點之前元素個數
value_type __x_copy = __x;
if (size_type(__index) < this->size() / 2) {//若插入點之前的元素較少
push_front(front());//先在容器頭部插入與第一個元素相同的元素
iterator __front1 = _M_start;
++__front1;
iterator __front2 = __front1;
++__front2;
__pos = _M_start + __index;//這里的pos相較與接受參數的pos已經前移一位了
iterator __pos1 = __pos;
++__pos1;
//原型
/*
* template<class InputIterator, class OutputIterator>
* OutputIterator copy (InputIterator first, InputIterator last, OutputIterator result)
* {
* while (first!=last) {
* *result = *first;
* ++result; ++first;
* }
* return result;
* }
*/
copy(__front2, __pos1, __front1);//移動元素
}
else {//若插入點之后的元素較少
push_back(back());//先在容器尾部插入與最后一個元素相同的元素
iterator __back1 = _M_finish;
--__back1;
iterator __back2 = __back1;
--__back2;
__pos = _M_start + __index;//這里的pos與接受參數的pos相同
//**原型
//* template<class BidirectionalIterator1, class BidirectionalIterator2>
//* BidirectionalIterator2 copy_backward ( BidirectionalIterator1 first,
//* BidirectionalIterator1 last,
//* BidirectionalIterator2 result )
//* {
//* while (last!=first) *(--result) = *(--last);
//* return result;
//* }
copy_backward(__pos, __back2, __back1);//移動元素
}
*__pos = __x_copy;
return __pos;
}
template <class _Tp, class _Alloc>
typename deque<_Tp,_Alloc>::iterator
deque<_Tp,_Alloc>::_M_insert_aux(iterator __pos)
{
difference_type __index = __pos - _M_start;
if (__index < size() / 2) {
push_front(front());
iterator __front1 = _M_start;
++__front1;
iterator __front2 = __front1;
++__front2;
__pos = _M_start + __index;
iterator __pos1 = __pos;
++__pos1;
copy(__front2, __pos1, __front1);
}
else {
push_back(back());
iterator __back1 = _M_finish;
--__back1;
iterator __back2 = __back1;
--__back2;
__pos = _M_start + __index;
copy_backward(__pos, __back2, __back1);
}
*__pos = value_type();
return __pos;
}
template <class _Tp, class _Alloc>
void deque<_Tp,_Alloc>::_M_insert_aux(iterator __pos,
size_type __n,
const value_type& __x)
{
const difference_type __elems_before = __pos - _M_start;
size_type __length = this->size();
value_type __x_copy = __x;
if (__elems_before < difference_type(__length / 2)) {
iterator __new_start = _M_reserve_elements_at_front(__n);
iterator __old_start = _M_start;
__pos = _M_start + __elems_before;
__STL_TRY {
if (__elems_before >= difference_type(__n)) {
iterator __start_n = _M_start + difference_type(__n);
uninitialized_copy(_M_start, __start_n, __new_start);
_M_start = __new_start;
copy(__start_n, __pos, __old_start);
fill(__pos - difference_type(__n), __pos, __x_copy);
}
else {
__uninitialized_copy_fill(_M_start, __pos, __new_start,
_M_start, __x_copy);
_M_start = __new_start;
fill(__old_start, __pos, __x_copy);
}
}
__STL_UNWIND(_M_destroy_nodes(__new_start._M_node, _M_start._M_node));
}
else {
iterator __new_finish = _M_reserve_elements_at_back(__n);
iterator __old_finish = _M_finish;
const difference_type __elems_after =
difference_type(__length) - __elems_before;
__pos = _M_finish - __elems_after;
__STL_TRY {
if (__elems_after > difference_type(__n)) {
iterator __finish_n = _M_finish - difference_type(__n);
uninitialized_copy(__finish_n, _M_finish, _M_finish);
_M_finish = __new_finish;
copy_backward(__pos, __finish_n, __old_finish);
fill(__pos, __pos + difference_type(__n), __x_copy);
}
else {
__uninitialized_fill_copy(_M_finish, __pos + difference_type(__n),
__x_copy, __pos, _M_finish);
_M_finish = __new_finish;
fill(__pos, __old_finish, __x_copy);
}
}
__STL_UNWIND(_M_destroy_nodes(_M_finish._M_node + 1,
__new_finish._M_node + 1));
}
}
#ifdef __STL_MEMBER_TEMPLATES
template <class _Tp, class _Alloc> template <class _ForwardIterator>
void deque<_Tp,_Alloc>::_M_insert_aux(iterator __pos,
_ForwardIterator __first,
_ForwardIterator __last,
size_type __n)
{
const difference_type __elemsbefore = __pos - _M_start;
size_type __length = size();
if (__elemsbefore < __length / 2) {
iterator __new_start = _M_reserve_elements_at_front(__n);
iterator __old_start = _M_start;
__pos = _M_start + __elemsbefore;
__STL_TRY {
if (__elemsbefore >= difference_type(__n)) {
iterator __start_n = _M_start + difference_type(__n);
uninitialized_copy(_M_start, __start_n, __new_start);
_M_start = __new_start;
copy(__start_n, __pos, __old_start);
copy(__first, __last, __pos - difference_type(__n));
}
else {
_ForwardIterator __mid = __first;
advance(__mid, difference_type(__n) - __elemsbefore);
__uninitialized_copy_copy(_M_start, __pos, __first, __mid,
__new_start);
_M_start = __new_start;
copy(__mid, __last, __old_start);
}
}
__STL_UNWIND(_M_destroy_nodes(__new_start._M_node, _M_start._M_node));
}
else {
iterator __new_finish = _M_reserve_elements_at_back(__n);
iterator __old_finish = _M_finish;
const difference_type __elemsafter =
difference_type(__length) - __elemsbefore;
__pos = _M_finish - __elemsafter;
__STL_TRY {
if (__elemsafter > difference_type(__n)) {
iterator __finish_n = _M_finish - difference_type(__n);
uninitialized_copy(__finish_n, _M_finish, _M_finish);
_M_finish = __new_finish;
copy_backward(__pos, __finish_n, __old_finish);
copy(__first, __last, __pos);
}
else {
_ForwardIterator __mid = __first;
advance(__mid, __elemsafter);
__uninitialized_copy_copy(__mid, __last, __pos, _M_finish, _M_finish);
_M_finish = __new_finish;
copy(__first, __mid, __pos);
}
}
__STL_UNWIND(_M_destroy_nodes(_M_finish._M_node + 1,
__new_finish._M_node + 1));
}
}
#else /* __STL_MEMBER_TEMPLATES */
template <class _Tp, class _Alloc>
void deque<_Tp,_Alloc>::_M_insert_aux(iterator __pos,
const value_type* __first,
const value_type* __last,
size_type __n)
{
const difference_type __elemsbefore = __pos - _M_start;
size_type __length = size();
if (__elemsbefore < __length / 2) {
iterator __new_start = _M_reserve_elements_at_front(__n);
iterator __old_start = _M_start;
__pos = _M_start + __elemsbefore;
__STL_TRY {
if (__elemsbefore >= difference_type(__n)) {
iterator __start_n = _M_start + difference_type(__n);
uninitialized_copy(_M_start, __start_n, __new_start);
_M_start = __new_start;
copy(__start_n, __pos, __old_start);
copy(__first, __last, __pos - difference_type(__n));
}
else {
const value_type* __mid =
__first + (difference_type(__n) - __elemsbefore);
__uninitialized_copy_copy(_M_start, __pos, __first, __mid,
__new_start);
_M_start = __new_start;
copy(__mid, __last, __old_start);
}
}
__STL_UNWIND(_M_destroy_nodes(__new_start._M_node, _M_start._M_node));
}
else {
iterator __new_finish = _M_reserve_elements_at_back(__n);
iterator __old_finish = _M_finish;
const difference_type __elemsafter =
difference_type(__length) - __elemsbefore;
__pos = _M_finish - __elemsafter;
__STL_TRY {
if (__elemsafter > difference_type(__n)) {
iterator __finish_n = _M_finish - difference_type(__n);
uninitialized_copy(__finish_n, _M_finish, _M_finish);
_M_finish = __new_finish;
copy_backward(__pos, __finish_n, __old_finish);
copy(__first, __last, __pos);
}
else {
const value_type* __mid = __first + __elemsafter;
__uninitialized_copy_copy(__mid, __last, __pos, _M_finish, _M_finish);
_M_finish = __new_finish;
copy(__first, __mid, __pos);
}
}
__STL_UNWIND(_M_destroy_nodes(_M_finish._M_node + 1,
__new_finish._M_node + 1));
}
}
template <class _Tp, class _Alloc>
void deque<_Tp,_Alloc>::_M_insert_aux(iterator __pos,
const_iterator __first,
const_iterator __last,
size_type __n)
{
const difference_type __elemsbefore = __pos - _M_start;
size_type __length = size();
if (__elemsbefore < __length / 2) {
iterator __new_start = _M_reserve_elements_at_front(__n);
iterator __old_start = _M_start;
__pos = _M_start + __elemsbefore;
__STL_TRY {
if (__elemsbefore >= __n) {
iterator __start_n = _M_start + __n;
uninitialized_copy(_M_start, __start_n, __new_start);
_M_start = __new_start;
copy(__start_n, __pos, __old_start);
copy(__first, __last, __pos - difference_type(__n));
}
else {
const_iterator __mid = __first + (__n - __elemsbefore);
__uninitialized_copy_copy(_M_start, __pos, __first, __mid,
__new_start);
_M_start = __new_start;
copy(__mid, __last, __old_start);
}
}
__STL_UNWIND(_M_destroy_nodes(__new_start._M_node, _M_start._M_node));
}
else {
iterator __new_finish = _M_reserve_elements_at_back(__n);
iterator __old_finish = _M_finish;
const difference_type __elemsafter = __length - __elemsbefore;
__pos = _M_finish - __elemsafter;
__STL_TRY {
if (__elemsafter > __n) {
iterator __finish_n = _M_finish - difference_type(__n);
uninitialized_copy(__finish_n, _M_finish, _M_finish);
_M_finish = __new_finish;
copy_backward(__pos, __finish_n, __old_finish);
copy(__first, __last, __pos);
}
else {
const_iterator __mid = __first + __elemsafter;
__uninitialized_copy_copy(__mid, __last, __pos, _M_finish, _M_finish);
_M_finish = __new_finish;
copy(__first, __mid, __pos);
}
}
__STL_UNWIND(_M_destroy_nodes(_M_finish._M_node + 1,
__new_finish._M_node + 1));
}
}
#endif /* __STL_MEMBER_TEMPLATES */
template <class _Tp, class _Alloc>
void deque<_Tp,_Alloc>::_M_new_elements_at_front(size_type __new_elems)
{
size_type __new_nodes
= (__new_elems + _S_buffer_size() - 1) / _S_buffer_size();
_M_reserve_map_at_front(__new_nodes);
size_type __i;
__STL_TRY {
for (__i = 1; __i <= __new_nodes; ++__i)
*(_M_start._M_node - __i) = _M_allocate_node();
}
# ifdef __STL_USE_EXCEPTIONS
catch(...) {
for (size_type __j = 1; __j < __i; ++__j)
_M_deallocate_node(*(_M_start._M_node - __j));
throw;
}
# endif /* __STL_USE_EXCEPTIONS */
}
template <class _Tp, class _Alloc>
void deque<_Tp,_Alloc>::_M_new_elements_at_back(size_type __new_elems)
{
size_type __new_nodes
= (__new_elems + _S_buffer_size() - 1) / _S_buffer_size();
_M_reserve_map_at_back(__new_nodes);
size_type __i;
__STL_TRY {
for (__i = 1; __i <= __new_nodes; ++__i)
*(_M_finish._M_node + __i) = _M_allocate_node();
}
# ifdef __STL_USE_EXCEPTIONS
catch(...) {
for (size_type __j = 1; __j < __i; ++__j)
_M_deallocate_node(*(_M_finish._M_node + __j));
throw;
}
# endif /* __STL_USE_EXCEPTIONS */
}
template <class _Tp, class _Alloc>
void deque<_Tp,_Alloc>::_M_reallocate_map(size_type __nodes_to_add,
bool __add_at_front)
{
//map原始節點數
size_type __old_num_nodes = _M_finish._M_node - _M_start._M_node + 1;
//map新的節點數
size_type __new_num_nodes = __old_num_nodes + __nodes_to_add;
_Map_pointer __new_nstart;
if (_M_map_size > 2 * __new_num_nodes) {//若map的大小比新節點數的兩倍還大，則只需調整迭代器start和finish
__new_nstart = _M_map + (_M_map_size - __new_num_nodes) / 2
+ (__add_at_front ? __nodes_to_add : 0);
if (__new_nstart < _M_start._M_node)
copy(_M_start._M_node, _M_finish._M_node + 1, __new_nstart);
else
copy_backward(_M_start._M_node, _M_finish._M_node + 1,
__new_nstart + __old_num_nodes);
}
else {//否則需重新分配一個新的map空間
size_type __new_map_size =
_M_map_size + max(_M_map_size, __nodes_to_add) + 2;
_Map_pointer __new_map = _M_allocate_map(__new_map_size);
__new_nstart = __new_map + (__new_map_size - __new_num_nodes) / 2
+ (__add_at_front ? __nodes_to_add : 0);
//拷貝原始map的內容
copy(_M_start._M_node, _M_finish._M_node + 1, __new_nstart);
//釋放原始map空間
_M_deallocate_map(_M_map, _M_map_size);
//更新map的起始地址和大小
_M_map = __new_map;
_M_map_size = __new_map_size;
}
//更新迭代器start和finish
_M_start._M_set_node(__new_nstart);
_M_finish._M_set_node(__new_nstart + __old_num_nodes - 1);
}
// Nonmember functions.
template <class _Tp, class _Alloc>
inline bool operator==(const deque<_Tp, _Alloc>& __x,
const deque<_Tp, _Alloc>& __y) {
return __x.size() == __y.size() &&
equal(__x.begin(), __x.end(), __y.begin());
}
template <class _Tp, class _Alloc>
inline bool operator<(const deque<_Tp, _Alloc>& __x,
const deque<_Tp, _Alloc>& __y) {
return lexicographical_compare(__x.begin(), __x.end(),
__y.begin(), __y.end());
}
#ifdef __STL_FUNCTION_TMPL_PARTIAL_ORDER
template <class _Tp, class _Alloc>
inline bool operator!=(const deque<_Tp, _Alloc>& __x,
const deque<_Tp, _Alloc>& __y) {
return !(__x == __y);
}
template <class _Tp, class _Alloc>
inline bool operator>(const deque<_Tp, _Alloc>& __x,
const deque<_Tp, _Alloc>& __y) {
return __y < __x;
}
template <class _Tp, class _Alloc>
inline bool operator<=(const deque<_Tp, _Alloc>& __x,
const deque<_Tp, _Alloc>& __y) {
return !(__y < __x);
}
template <class _Tp, class _Alloc>
inline bool operator>=(const deque<_Tp, _Alloc>& __x,
const deque<_Tp, _Alloc>& __y) {
return !(__x < __y);
}
template <class _Tp, class _Alloc>
inline void swap(deque<_Tp,_Alloc>& __x, deque<_Tp,_Alloc>& __y) {
__x.swap(__y);
}
#endif /* __STL_FUNCTION_TMPL_PARTIAL_ORDER */
#if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
#pragma reset woff 1174
#pragma reset woff 1375
#endif
__STL_END_NAMESPACE
#endif /* __SGI_STL_INTERNAL_DEQUE_H */
// Local Variables:
// mode:C++
// End:
~~~
參考資料
《STL源碼剖析》侯捷
[《STL源碼剖析-- stl_deque.h》](http://blog.csdn.net/mdl13412/article/details/6647409)
[《STL筆記之deque》](http://www.programlife.net/stl-deque.html)
- 前言
- 空間配置器
- Traits編程技術
- STL源碼剖析——迭代器
- 全局函數construct(),destroy(),uninitialized_copy(),uninitialized_fill(),uninitialized_fill_n()
- 序列容器之vector
- list容器的排序算法sort()
- 序列容器之list
- 序列容器之deque
- 容器配接器之stack
- 容器配接器之queue
- 容器配接器之priority_queue
- 最大堆heap
- 單向鏈表slist
- RB-Tree(紅黑樹)
- 關聯容器之set
- stl_pair.h學習
- 關聯容器之map
- 關聯容器之multiset
- 關聯容器之multimap
- 散列表hashtable
- stl_hash_fun.h學習
- 關聯容器之hash_set
- 關聯容器之hash_multiset
- 關聯容器之hash_map
- 關聯容器之hash_multimap
- 數值算法stl_numeric.h
- stl_relops.h學習
- 基本算法stl_algobase.h
- STL算法之set集合算法
- STL算法stl_algo.h
- STL算法之sort排序算法
- STL算法之find查找算法
- STL算法之merge合并算法
- STL算法之remove刪除算法
- STL算法之permutation排列組合
- STL函數對象