CONTENTS
备注：
本读书笔记基于侯捷先生的《STL源码剖析》，截图和注释版权均属于原作者所有。
本读书笔记中的源码部分直接拷贝自SGI-STL，部分代码删除了头部的版权注释，但代码版权属于原作者。
小弟初看stl，很多代码都不是太懂，注释可能有很多错误，还请路过的各位大牛多多给予指导。
为了降低学习难度，作者这里换到了SGI-STL-2.91.57的源码来学习，代码下载地址为【 http://jjhou.boolan.com/jjwbooks-tass.htm 】
首先贴一张deque的内存组成图：
stl_deque.h：
__STL_BEGIN_NAMESPACE
#if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
#pragma set woff 1174
#endif
// Note: this function is simply a kludge to work around several compilers'
// bugs in handling constant expressions.
inline size_t __deque_buf_size(size_t n, size_t sz)//确定deque的单个缓冲区的大小
{
return n != 0 ? n : (sz < 512 ? size_t(512 / sz) : size_t(1));
}
#ifndef __STL_NON_TYPE_TMPL_PARAM_BUG
template <class T, class Ref, class Ptr, size_t BufSiz>
struct __deque_iterator {
typedef __deque_iterator<T, T&, T*, BufSiz> iterator;
typedef __deque_iterator<T, const T&, const T*, BufSiz> const_iterator;
static size_t buffer_size() {return __deque_buf_size(BufSiz, sizeof(T)); }
#else /* __STL_NON_TYPE_TMPL_PARAM_BUG */
template <class T, class Ref, class Ptr>
struct __deque_iterator {
typedef __deque_iterator<T, T&, T*> iterator;
typedef __deque_iterator<T, const T&, const T*> const_iterator;
static size_t buffer_size() {return __deque_buf_size(0, sizeof(T)); }
#endif
typedef random_access_iterator_tag iterator_category;
typedef T value_type;
typedef Ptr pointer;
typedef Ref reference;
typedef size_t size_type;
typedef ptrdiff_t difference_type;
typedef T** map_pointer;//关键所在，这里的map_pointer是指向指针的指针。
typedef __deque_iterator self;
T* cur;
T* first;
T* last;
map_pointer node;//这里的node指向的是deque的内部的map，它的解引用指向了deque的一个缓冲区，因此必须是指向指针的指针。
__deque_iterator(T* x, map_pointer y)
: cur(x), first(*y), last(*y + buffer_size()), node(y) {}
__deque_iterator() : cur(0), first(0), last(0), node(0) {}
__deque_iterator(const iterator& x)
: cur(x.cur), first(x.first), last(x.last), node(x.node) {}
reference operator*() const { return *cur; }//对iterator解引用直接返回*cur
#ifndef __SGI_STL_NO_ARROW_OPERATOR
pointer operator->() const { return &(operator*()); }//重写了->运算符
#endif /* __SGI_STL_NO_ARROW_OPERATOR */
//两个iterator相减，其实就是计算距离。这里需要考虑的是两个iterator分别在不同的缓冲区上。
//这样需要考虑两个缓冲区间的元素的数目。
difference_type operator-(const self& x) const {
return difference_type(buffer_size()) * (node - x.node - 1) +
(cur - first) + (x.last - x.cur);
}
//由于deque是缓冲区+map，因此递增递减很可能会遇到当前缓冲区边界，会跳到下一个/上一个缓冲区里。
//这里直接调用了下面的重载后的+ -
self& operator++() {
++cur;
if (cur == last) {//如果curr在递增之后指向了最后一个元素的下一个元素，说明curr已经到了当前缓冲区末尾
set_node(node + 1);//此时需要转到下一个缓冲区中。
cur = first;//然后curr指向新缓冲区的第一个元素。
}
return *this;
}
self operator++(int) {
self tmp = *this;
++*this;
return tmp;
}
self& operator--() {
if (cur == first) {
set_node(node - 1);
cur = last;
}
--cur;
return *this;
}
self operator--(int) {
self tmp = *this;
--*this;
return tmp;
}
//+= -=操作符重载之后，后面的+ -就很容易解决了。这里先算出目标所在的缓冲区，然后更改指向就可以了。
self& operator+=(difference_type n) {
//如果移动范围在当前缓冲区内，直接移动即可。
difference_type offset = n + (cur - first);
if (offset >= 0 && offset < difference_type(buffer_size()))
cur += n;
else {
//如果要移动的范围已经超出了当前缓冲区，那么就先计算出要移动到的新的缓冲区
difference_type node_offset =
offset > 0 ? offset / difference_type(buffer_size())
: -difference_type((-offset - 1) / buffer_size()) - 1;
set_node(node + node_offset);
//新缓冲区移动好之后，再移动到指定的位置。
cur = first + (offset - node_offset * difference_type(buffer_size()));
}
return *this;
}
self operator+(difference_type n) const {
self tmp = *this;
return tmp += n;
}
self& operator-=(difference_type n) { return *this += -n; }
self operator-(difference_type n) const {
self tmp = *this;
return tmp -= n;
}
reference operator[](difference_type n) const { return *(*this + n); }
bool operator==(const self& x) const { return cur == x.cur; }
bool operator!=(const self& x) const { return !(*this == x); }
bool operator<(const self& x) const {
return (node == x.node) ? (cur < x.cur) : (node < x.node);
}
//set_node主要是用来更改iterator指向的缓冲区，更改好之后，刷新下first，last
//first = 新缓冲区的第一个元素
//last = 新缓冲区的最后一个元素的下一个位置
void set_node(map_pointer new_node) {
node = new_node;
first = *new_node;
last = first + difference_type(buffer_size());
}
};
#ifndef __STL_CLASS_PARTIAL_SPECIALIZATION
#ifndef __STL_NON_TYPE_TMPL_PARAM_BUG
template <class T, class Ref, class Ptr, size_t BufSiz>
inline random_access_iterator_tag
iterator_category(const __deque_iterator<T, Ref, Ptr, BufSiz>&) {
return random_access_iterator_tag();
}
template <class T, class Ref, class Ptr, size_t BufSiz>
inline T* value_type(const __deque_iterator<T, Ref, Ptr, BufSiz>&) {
return 0;
}
template <class T, class Ref, class Ptr, size_t BufSiz>
inline ptrdiff_t* distance_type(const __deque_iterator<T, Ref, Ptr, BufSiz>&) {
return 0;
}
#else /* __STL_NON_TYPE_TMPL_PARAM_BUG */
template <class T, class Ref, class Ptr>
inline random_access_iterator_tag
iterator_category(const __deque_iterator<T, Ref, Ptr>&) {
return random_access_iterator_tag();
}
template <class T, class Ref, class Ptr>
inline T* value_type(const __deque_iterator<T, Ref, Ptr>&) { return 0; }
template <class T, class Ref, class Ptr>
inline ptrdiff_t* distance_type(const __deque_iterator<T, Ref, Ptr>&) {
return 0;
}
#endif /* __STL_NON_TYPE_TMPL_PARAM_BUG */
#endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */
// See __deque_buf_size(). The only reason that the default value is 0
// is as a workaround for bugs in the way that some compilers handle
// constant expressions.
template <class T, class Alloc = alloc, size_t BufSiz = 0>
class deque {
public: // Basic types
typedef T 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;
public: // Iterators
#ifndef __STL_NON_TYPE_TMPL_PARAM_BUG
typedef __deque_iterator<T, T&, T*, BufSiz> iterator;
typedef __deque_iterator<T, const T&, const T&, BufSiz> const_iterator;
#else /* __STL_NON_TYPE_TMPL_PARAM_BUG */
typedef __deque_iterator<T, T&, T*> iterator;
typedef __deque_iterator<T, const T&, const T*> const_iterator;
#endif /* __STL_NON_TYPE_TMPL_PARAM_BUG */
#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;//map_pointer是指向指针的指针，用来指向内部管理缓冲区的map。
typedef simple_alloc<value_type, Alloc> data_allocator;
typedef simple_alloc<pointer, Alloc> map_allocator;
static size_type buffer_size() { //返回缓冲区的大小（容量）
return __deque_buf_size(BufSiz, sizeof(value_type));
}
static size_type initial_map_size() { return 8; }//返回map的初始大小（即初始化时有多少个缓冲区）
protected: // Data members
iterator start;//deque内部存储的iterator，分别指向【第一个元素】和【最后一个元素的下一个元素】。
iterator finish;//注意，由于deque可以两头删改，因此start指向的可能不是缓冲区的第一个元素，finish指向的可能缓冲区的最后一个元素的下一个元素。
//这里【第一个元素】和【最后一个元素的下一个元素】只是逻辑上的概念。
map_pointer map;
size_type map_size;
public: // Basic accessors
iterator begin() { return start; }
iterator end() { return finish; }
const_iterator begin() const { return start; }
const_iterator end() const { return finish; }
reverse_iterator rbegin() { return reverse_iterator(finish); }
reverse_iterator rend() { return reverse_iterator(start); }
const_reverse_iterator rbegin() const {
return const_reverse_iterator(finish);
}
const_reverse_iterator rend() const {
return const_reverse_iterator(start);
}
reference operator[](size_type n) { return start[difference_type(n)]; }
const_reference operator[](size_type n) const {
return start[difference_type(n)];
}
reference front() { return *start; }//返回第一个有效元素。
reference back() {//返回最后一个有效元素。
iterator tmp = finish;
--tmp;
return *tmp;
}
const_reference front() const { return *start; }
const_reference back() const {
const_iterator tmp = finish;
--tmp;
return *tmp;
}
size_type size() const { return finish - start;; }//返回deque内的元素个数。
size_type max_size() const { return size_type(-1); }//缓冲区的数目是可以扩充的，因此deque的理论最大值与内存有关。
bool empty() const { return finish == start; }//deque是否为空
public: // Constructor, destructor.
//默认构造函数
deque()
: start(), finish(), map(0), map_size(0)
{
create_map_and_nodes(0);
}
//拷贝构造函数
deque(const deque& x)
: start(), finish(), map(0), map_size(0)
{
create_map_and_nodes(x.size());//先根据要拷贝的deque的大小创建一个新的deque
__STL_TRY {
uninitialized_copy(x.begin(), x.end(), start);//将老的deque复制到新的里面
}
__STL_UNWIND(destroy_map_and_nodes());//出错了就把申请的内存全部释放掉
}
//用一个固定值填满deque
deque(size_type n, const value_type& value)
: start(), finish(), map(0), map_size(0)
{
fill_initialize(n, value);
}
deque(int n, const value_type& value)
: start(), finish(), map(0), map_size(0)
{
fill_initialize(n, value);
}
deque(long n, const value_type& value)
: start(), finish(), map(0), map_size(0)
{
fill_initialize(n, value);
}
explicit deque(size_type n)
: start(), finish(), map(0), map_size(0)
{
fill_initialize(n, value_type());
}
#ifdef __STL_MEMBER_TEMPLATES
template <class InputIterator>
deque(InputIterator first, InputIterator last)
: start(), finish(), map(0), map_size(0)
{
range_initialize(first, last, iterator_category(first));
}
#else /* __STL_MEMBER_TEMPLATES */
deque(const value_type* first, const value_type* last)
: start(), finish(), map(0), map_size(0)
{
create_map_and_nodes(last - first);
__STL_TRY {
uninitialized_copy(first, last, start);
}
__STL_UNWIND(destroy_map_and_nodes());
}
deque(const_iterator first, const_iterator last)
: start(), finish(), map(0), map_size(0)
{
create_map_and_nodes(last - first);
__STL_TRY {
uninitialized_copy(first, last, start);
}
__STL_UNWIND(destroy_map_and_nodes());
}
#endif /* __STL_MEMBER_TEMPLATES */
~deque() {
//先把deque内部的元素销毁掉
destroy(start, finish);
//然后释放掉内存
destroy_map_and_nodes();
}
//赋值构造函数
deque& operator= (const deque& x) {
const size_type len = size();
if (&x != this) {
if (len >= x.size())
erase(copy(x.begin(), x.end(), start), finish);//如果本地的大小>外部deque的大小，直接抹掉多出来的
else {//如果本地大小<外部deque的大小，多出来的调用insert方法。
const_iterator mid = x.begin() + difference_type(len);
copy(x.begin(), mid, start);
insert(finish, mid, x.end());
}
}
return *this;
}
void swap(deque& x) {
__STD::swap(start, x.start);
__STD::swap(finish, x.finish);
__STD::swap(map, x.map);
__STD::swap(map_size, x.map_size);
}
public: // push_* and pop_*
//在尾端插入一个元素。
void push_back(const value_type& t) {
//首先看下当前的缓冲区是否还有空余的位置。
if (finish.cur != finish.last - 1) {
construct(finish.cur, t);//有空余位置，构造。
++finish.cur;
}
else
push_back_aux(t);//只有一个空余位置，那么就申请新的缓冲区。
}
//在头部插入一个数据。
void push_front(const value_type& t) {
//首先看下当前的缓冲区是否还有空余的位置。
if (start.cur != start.first) {
construct(start.cur - 1, t);//有空余位置，构造。
--start.cur;//头部iterator递减一个。
}
else
push_front_aux(t);//没有了，只能去上一个缓冲区里找地方了。
}
//从尾部删除一个元素
void pop_back() {
if (finish.cur != finish.first) {//首先检查下最后一个元素是不是当前缓冲区的第一个元素
--finish.cur;//不是，比较简单，直接删除即可。
destroy(finish.cur);
}
else
pop_back_aux();//是当前缓冲区的第一个元素，那么删除之后就需要跳到上一个缓冲区了。
}
//从头部删除一个元素
void pop_front() {
if (start.cur != start.last - 1) {//首先检查下第一个元素是不是当前缓冲区的最后一个元素
destroy(start.cur);//不是，比较简单，直接删除即可。
++start.cur;
}
else
pop_front_aux();//是当前缓冲区的最后一个元素，那么删除之后就需要跳到下一个缓冲区了。
}
public: // Insert
//在指定位置插入数据
//如果插入点在头部或者尾部，那么直接调用push_xx
//其他位置，就比较麻烦了，需要大量的位置移动才能拿到空位
iterator insert(iterator position, const value_type& x) {
if (position.cur == start.cur) {
push_front(x);
return start;
}
else if (position.cur == finish.cur) {
push_back(x);
iterator tmp = finish;
--tmp;
return tmp;
}
else {
return insert_aux(position, x);
}
}
//在指定位置插入一个空（默认构造函数）元素
iterator insert(iterator position) { return insert(position, value_type()); }
void insert(iterator pos, size_type n, const value_type& x);
void insert(iterator pos, int n, const value_type& x) {
insert(pos, (size_type) n, x);
}
void insert(iterator pos, long n, const value_type& x) {
insert(pos, (size_type) n, x);
}
#ifdef __STL_MEMBER_TEMPLATES
template <class InputIterator>
void insert(iterator pos, InputIterator first, InputIterator last) {
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(start + new_size, finish);
else
insert(finish, new_size - len, x);
}
void resize(size_type new_size) { resize(new_size, value_type()); }
public: // Erase
//删除指定位置的元素。
//如果要删除的位置距离头部比较近，那么就把删除位置前面的元素向后移一格，然后删除第一个元素。
//如果要删除的位置距离尾部比较近，那么就把删除位置后面的元素向前移一格，然后删除最后一个元素。
iterator erase(iterator pos) {
iterator next = pos;
++next;
difference_type index = pos - start;
if (index < (size() >> 1)) {
copy_backward(start, pos, next);
pop_front();
}
else {
copy(next, finish, pos);
pop_back();
}
return start + index;
}
iterator erase(iterator first, iterator last);
void clear();
protected: // Internal construction/destruction
void create_map_and_nodes(size_type num_elements);
void destroy_map_and_nodes();
void fill_initialize(size_type n, const value_type& value);
#ifdef __STL_MEMBER_TEMPLATES
template <class InputIterator>
void range_initialize(InputIterator first, InputIterator last,
input_iterator_tag);
template <class ForwardIterator>
void range_initialize(ForwardIterator first, ForwardIterator last,
forward_iterator_tag);
#endif /* __STL_MEMBER_TEMPLATES */
protected: // Internal push_* and pop_*
void push_back_aux(const value_type& t);
void push_front_aux(const value_type& t);
void pop_back_aux();
void 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 insert_aux(iterator pos, const value_type& x);
void insert_aux(iterator pos, size_type n, const value_type& x);
#ifdef __STL_MEMBER_TEMPLATES
template <class ForwardIterator>
void insert_aux(iterator pos, ForwardIterator first, ForwardIterator last,
size_type n);
#else /* __STL_MEMBER_TEMPLATES */
void insert_aux(iterator pos,
const value_type* first, const value_type* last,
size_type n);
void insert_aux(iterator pos, const_iterator first, const_iterator last,
size_type n);
#endif /* __STL_MEMBER_TEMPLATES */
//在deque头部预留n个空的元素位置。
iterator reserve_elements_at_front(size_type n) {
size_type vacancies = start.cur - start.first;//先获取下当前头部的空余位置数量
if (n > vacancies) //如果需求的数量大于当前数量，那就必须在前面申请新的数量
new_elements_at_front(n - vacancies);
return start - difference_type(n);
}
//在deque尾部预留n个空余的元素位置。
iterator reserve_elements_at_back(size_type n) {
size_type vacancies = (finish.last - finish.cur) - 1;
if (n > vacancies)
new_elements_at_back(n - vacancies);
return finish + difference_type(n);
}
void new_elements_at_front(size_type new_elements);
void new_elements_at_back(size_type new_elements);
void destroy_nodes_at_front(iterator before_start);
void destroy_nodes_at_back(iterator after_finish);
protected: // Allocation of map and nodes
// Makes sure the map has space for new nodes. Does not actually
// add the nodes. Can invalidate map pointers. (And consequently,
// deque iterators.)
//在map尾部预留n个空间，不够则重新申请
void reserve_map_at_back (size_type nodes_to_add = 1) {
if (nodes_to_add + 1 > map_size - (finish.node - map))
reallocate_map(nodes_to_add, false);
}
//在map头部预留n个空间，不够则重新申请
void reserve_map_at_front (size_type nodes_to_add = 1) {
if (nodes_to_add > start.node - map)
reallocate_map(nodes_to_add, true);
}
void reallocate_map(size_type nodes_to_add, bool add_at_front);
pointer allocate_node() { return data_allocator::allocate(buffer_size()); }
void deallocate_node(pointer n) {
data_allocator::deallocate(n, buffer_size());
}
#ifdef __STL_NON_TYPE_TMPL_PARAM_BUG
public:
//判断两个deque是否相等。
bool operator==(const deque<T, Alloc, 0>& x) const {
return size() == x.size() && equal(begin(), end(), x.begin());
}
bool operator!=(const deque<T, Alloc, 0>& x) const {
return size() != x.size() || !equal(begin(), end(), x.begin());
}
bool operator<(const deque<T, Alloc, 0>& x) const {
return lexicographical_compare(begin(), end(), x.begin(), x.end());
}
#endif /* __STL_NON_TYPE_TMPL_PARAM_BUG */
};
// Non-inline member functions
//在指定位置插入n个相同的元素。
template <class T, class Alloc, size_t BufSize>
void deque<T, Alloc, BufSize>::insert(iterator pos,
size_type n, const value_type& x) {
//如果指定的位置是deque的头部，那么首先在deque的头部预留n个位置，然后调用拷贝构造函数。
if (pos.cur == start.cur) {
iterator new_start = reserve_elements_at_front(n);
uninitialized_fill(new_start, start, x);
start = new_start;
} //如果指定的位置是deque的尾部，那么首先在deque的尾部预留n个位置，然后调用拷贝构造函数。
else if (pos.cur == finish.cur) {
iterator new_finish = reserve_elements_at_back(n);
uninitialized_fill(finish, new_finish, x);
finish = new_finish;
}
else //调用通用方法。
insert_aux(pos, n, x);
}
#ifndef __STL_MEMBER_TEMPLATES
//在指定位置插入【first，last)的元素
template <class T, class Alloc, size_t BufSize>
void deque<T, Alloc, BufSize>::insert(iterator pos,
const value_type* first,
const value_type* last) {
size_type n = last - first;//先获取要插入元素的个数。
if (pos.cur == start.cur) {//如果指定的位置是deque的头部，那么首先在deque的头部预留n个位置，然后调用拷贝构造函数。
iterator new_start = reserve_elements_at_front(n);
__STL_TRY {
uninitialized_copy(first, last, new_start);
start = new_start;
}
__STL_UNWIND(destroy_nodes_at_front(new_start));
}
else if (pos.cur == finish.cur) {//如果指定的位置是deque的尾部，那么首先在deque的尾部预留n个位置，然后调用拷贝构造函数。
iterator new_finish = reserve_elements_at_back(n);
__STL_TRY {
uninitialized_copy(first, last, finish);
finish = new_finish;
}
__STL_UNWIND(destroy_nodes_at_back(new_finish));
}
else//调用通用方法。
insert_aux(pos, first, last, n);
}
//在指定位置插入【first，last)的元素
template <class T, class Alloc, size_t BufSize>
void deque<T, Alloc, BufSize>::insert(iterator pos,
const_iterator first,
const_iterator last)
{
size_type n = last - first;
if (pos.cur == start.cur) {
iterator new_start = reserve_elements_at_front(n);
__STL_TRY {
uninitialized_copy(first, last, new_start);
start = new_start;
}
__STL_UNWIND(destroy_nodes_at_front(new_start));
}
else if (pos.cur == finish.cur) {
iterator new_finish = reserve_elements_at_back(n);
__STL_TRY {
uninitialized_copy(first, last, finish);
finish = new_finish;
}
__STL_UNWIND(destroy_nodes_at_back(new_finish));
}
else
insert_aux(pos, first, last, n);
}
#endif /* __STL_MEMBER_TEMPLATES */
//删除【first,last)间的元素
template <class T, class Alloc, size_t BufSize>
deque<T, Alloc, BufSize>::iterator
deque<T, Alloc, BufSize>::erase(iterator first, iterator last) {
if (first == start && last == finish) {
clear();//如果起始结束为整个deque的起始和结束，那么直接全部删除。
return finish;
}
else {
//先计算出删除区间距离deque头部的距离，以判断要删除区间距离头部还是尾部比较近。
difference_type n = last - first;
difference_type elems_before = first - start;
if (elems_before < (size() - n) / 2) {//要删除区间距离头部比较近，那么就吧头部的数据向后拷贝
copy_backward(start, first, last);
iterator new_start = start + n;
destroy(start, new_start);//然后删除原来头部的数据。
for (map_pointer cur = start.node; cur < new_start.node; ++cur)
data_allocator::deallocate(*cur, buffer_size());
start = new_start;
}
else {//要删除区间距离尾部比较近，那么就把尾部的数据向前拷贝，然后删除原来尾部的数据。
copy(last, finish, first);
iterator new_finish = finish - n;
destroy(new_finish, finish);
for (map_pointer cur = new_finish.node + 1; cur <= finish.node; ++cur)
data_allocator::deallocate(*cur, buffer_size());
finish = new_finish;
}
return start + elems_before;
}
}
//删除所有的元素,注意这里必须要保留头部缓冲区
template <class T, class Alloc, size_t BufSize>
void deque<T, Alloc, BufSize>::clear() {
//从头部+1 开始，删除到尾部（不包括尾部缓冲区），这样就把中间的塞满元素的缓冲区以及里面的数据全部删掉。
for (map_pointer node = start.node + 1; node < finish.node; ++node) {
//注意这里start.node + 1，结束判断是<
destroy(*node, *node + buffer_size());
data_allocator::deallocate(*node, buffer_size());
}
//再删除头，尾部缓冲区中的数据，并将尾部的缓冲区也删掉
if (start.node != finish.node) {
destroy(start.cur, start.last);
destroy(finish.first, finish.cur);
data_allocator::deallocate(finish.first, buffer_size());
}
else
destroy(start.cur, finish.cur);
finish = start;
}
//创建一个可以容纳num_elements个元素的deque
template <class T, class Alloc, size_t BufSize>
void deque<T, Alloc, BufSize>::create_map_and_nodes(size_type num_elements) {
size_type num_nodes = num_elements / buffer_size() + 1;
map_size = max(initial_map_size(), num_nodes + 2);//先算出map的大小
map = map_allocator::allocate(map_size);//申请特定容量的map
map_pointer nstart = map + (map_size - num_nodes) / 2;
map_pointer nfinish = nstart + num_nodes - 1;
map_pointer cur;
__STL_TRY {
for (cur = nstart; cur <= nfinish; ++cur)
*cur = allocate_node();//将每个map节点都指向一个新申请的缓冲区。
}
# ifdef __STL_USE_EXCEPTIONS
catch(...) {
for (map_pointer n = nstart; n < cur; ++n)
deallocate_node(*n);
map_allocator::deallocate(map, map_size);
throw;
}
# endif /* __STL_USE_EXCEPTIONS */
start.set_node(nstart);//设置好各种变量
finish.set_node(nfinish);
start.cur = start.first;
finish.cur = finish.first + num_elements % buffer_size();
}
//删除deque申请的内存
// This is only used as a cleanup function in catch clauses.
template <class T, class Alloc, size_t BufSize>
void deque<T, Alloc, BufSize>::destroy_map_and_nodes() {
for (map_pointer cur = start.node; cur <= finish.node; ++cur)
deallocate_node(*cur);
map_allocator::deallocate(map, map_size);
}
//申请n个元素空间，并用指定的元素初始化
template <class T, class Alloc, size_t BufSize>
void deque<T, Alloc, BufSize>::fill_initialize(size_type n,
const value_type& value) {
create_map_and_nodes(n);//先申请元素
map_pointer cur;
__STL_TRY {
//从头部开始到尾部（不包括尾部缓冲区），先把前面的缓冲区塞满
for (cur = start.node; cur < finish.node; ++cur)
uninitialized_fill(*cur, *cur + buffer_size(), value);
//最后一个缓冲区可能塞不满，在for循环之后额外调用fill函数。
uninitialized_fill(finish.first, finish.cur, value);
}
# ifdef __STL_USE_EXCEPTIONS
catch(...) {
for (map_pointer n = start.node; n < cur; ++n)
destroy(*n, *n + buffer_size());
destroy_map_and_nodes();
throw;
}
# endif /* __STL_USE_EXCEPTIONS */
}
#ifdef __STL_MEMBER_TEMPLATES
//初始化，将【first，last）的数据拷贝到deque
template <class T, class Alloc, size_t BufSize>
template <class InputIterator>
void deque<T, Alloc, BufSize>::range_initialize(InputIterator first,
InputIterator last,
input_iterator_tag) {
//input_iterator_tag无法直接操作获取到【first，last）间的数量，因此只能先申请一个最小deque，然后
//慢慢的往里面添加。
create_map_and_nodes(0);
for ( ; first != last; ++first)
push_back(*first);
}
template <class T, class Alloc, size_t BufSize>
template <class ForwardIterator>
void deque<T, Alloc, BufSize>::range_initialize(ForwardIterator first,
ForwardIterator last,
forward_iterator_tag) {
//forward_iterator_tag可以直接操作获取到【first，last）间的数量。
//可以根据这个数量直接把deque的内存初始化好，然后可以直接拷贝。提高效率
size_type n = 0;
distance(first, last, n);
create_map_and_nodes(n);
__STL_TRY {
uninitialized_copy(first, last, start);
}
__STL_UNWIND(destroy_map_and_nodes());
}
#endif /* __STL_MEMBER_TEMPLATES */
//首先确认下该函数的调用逻辑：只有当前缓冲区只有一个空位时，需要申请新的缓冲区时才会调到此函数.
// Called only if finish.cur == finish.last - 1.
template <class T, class Alloc, size_t BufSize>
void deque<T, Alloc, BufSize>::push_back_aux(const value_type& t) {
value_type t_copy = t;
reserve_map_at_back();//首先扩容下map，使它能容纳新的缓冲区。
*(finish.node + 1) = allocate_node();//申请新的缓冲区，并放入map中。
__STL_TRY {
construct(finish.cur, t_copy);//在当前的这个（该缓冲区最后一个）空位上调用构造函数。
finish.set_node(finish.node + 1);//更新finish指针，使cur指向下一个空位。这里是新申请的缓冲区的第一个位置。
finish.cur = finish.first;
}
__STL_UNWIND(deallocate_node(*(finish.node + 1)));
}
//首先确认下该函数的调用逻辑：只有当前缓冲区没有空位时，需要申请新的缓冲区时才会调到此函数.
// Called only if start.cur == start.first.
template <class T, class Alloc, size_t BufSize>
void deque<T, Alloc, BufSize>::push_front_aux(const value_type& t) {
value_type t_copy = t;
reserve_map_at_front();//首先扩容下map，使它能容纳新的缓冲区。
*(start.node - 1) = allocate_node();//申请新的缓冲区，并放入map中。
__STL_TRY {
start.set_node(start.node - 1);//这里先更新指针，将start指向新的缓冲区的最后一个位置。
start.cur = start.last - 1;
construct(start.cur, t_copy);//然后在start的位置的上调用拷贝构造函数。
}
# ifdef __STL_USE_EXCEPTIONS
catch(...) {
start.set_node(start.node + 1);
start.cur = start.first;
deallocate_node(*(start.node - 1));
throw;
}
# endif /* __STL_USE_EXCEPTIONS */
}
//首先确认下该函数的调用逻辑。当最后一个缓冲区本来就是空的情况下，又一次调用了pop_back，此时才回调用该函数。
//此时会把最后一个缓冲区删掉,然后删除倒数第二个缓冲区的最后一个元素。
// Called only if finish.cur == finish.first.
template <class T, class Alloc, size_t BufSize>
void deque<T, Alloc, BufSize>:: pop_back_aux() {
deallocate_node(finish.first);//先把最后一个缓冲区给删掉。
finish.set_node(finish.node - 1);//更新finish指向倒数第二个缓冲区的最后一个元素。
finish.cur = finish.last - 1;
destroy(finish.cur);//删掉finish指向的元素。
}
// Called only if start.cur == start.last - 1. Note that if the deque
// has at least one element (a necessary precondition for this member
// function), and if start.cur == start.last, then the deque must have
// at least two nodes.
//需要注意该函数的调用逻辑。如果当前要删除的元素是当前缓冲区的最后一个元素，删了之后当前缓冲区会被一并删除。
template <class T, class Alloc, size_t BufSize>
void deque<T, Alloc, BufSize>::pop_front_aux() {
destroy(start.cur);//先删除当前元素
deallocate_node(start.first);//再删除当前缓冲区
start.set_node(start.node + 1);//更新start，指向第二个缓冲区。
start.cur = start.first;
}
#ifdef __STL_MEMBER_TEMPLATES
//各种 insert 方法。
template <class T, class Alloc, size_t BufSize>
template <class InputIterator>
void deque<T, Alloc, BufSize>::insert(iterator pos,
InputIterator first, InputIterator last,
input_iterator_tag) {
copy(first, last, inserter(*this, pos));
}
template <class T, class Alloc, size_t BufSize>
template <class ForwardIterator>
void deque<T, Alloc, BufSize>::insert(iterator pos,
ForwardIterator first,
ForwardIterator last,
forward_iterator_tag) {
size_type n = 0;
distance(first, last, n);
if (pos.cur == start.cur) {
iterator new_start = reserve_elements_at_front(n);
__STL_TRY {
uninitialized_copy(first, last, new_start);
start = new_start;
}
__STL_UNWIND(destroy_nodes_at_front(new_start));
}
else if (pos.cur == finish.cur) {
iterator new_finish = reserve_elements_at_back(n);
__STL_TRY {
uninitialized_copy(first, last, finish);
finish = new_finish;
}
__STL_UNWIND(destroy_nodes_at_back(new_finish));
}
else
insert_aux(pos, first, last, n);
}
#endif /* __STL_MEMBER_TEMPLATES */
//在指定位置插入一个元素。
template <class T, class Alloc, size_t BufSize>
typename deque<T, Alloc, BufSize>::iterator
deque<T, Alloc, BufSize>::insert_aux(iterator pos, const value_type& x) {
difference_type index = pos - start;
value_type x_copy = x;
//如果这个位置里头部比较近，那么就在头部插入一个元素，将前面的数据全部向前复制一格，
//然后把要插入的数据更新到指定的位置上。这里头部插入的元素是front()的原因是便于统一处理构造与析构流程。
if (index < size() / 2) {
push_front(front());
iterator front1 = start;
++front1;
iterator front2 = front1;
++front2;
pos = start + index;
iterator pos1 = pos;
++pos1;
copy(front2, pos1, front1);
}
else {
//如果要插入的位置距离尾部比较近，就在尾部插入一个元素，将后面的好数据全部向后复制一格。
//然后把要插入的数据更新到指定的位置上。
push_back(back());
iterator back1 = finish;
--back1;
iterator back2 = back1;
--back2;
pos = start + index;
copy_backward(pos, back2, back1);
}
*pos = x_copy;
return pos;
}
//在指定的位置插入n个元素，每个元素都用x赋值。
template <class T, class Alloc, size_t BufSize>
void deque<T, Alloc, BufSize>::insert_aux(iterator pos,
size_type n, const value_type& x) {
const difference_type elems_before = pos - start;
size_type length = size();
value_type x_copy = x;
//和上面的函数一样。首先看下插入点距离头部还是尾部比较近。
//如果距离头部比较近，就在头部先申请n个空格，然后将头部数据向前赋值，然后用x把空出的位置填满。
if (elems_before < length / 2) {
iterator new_start = reserve_elements_at_front(n);
iterator old_start = start;
pos = start + elems_before;
__STL_TRY {
if (elems_before >= difference_type(n)) {
iterator start_n = start + difference_type(n);
uninitialized_copy(start, start_n, new_start);
start = new_start;
copy(start_n, pos, old_start);
fill(pos - difference_type(n), pos, x_copy);
}
else {
__uninitialized_copy_fill(start, pos, new_start, start, x_copy);
start = new_start;
fill(old_start, pos, x_copy);
}
}
__STL_UNWIND(destroy_nodes_at_front(new_start));
}
else {
//如果距离尾部比较近，就在尾部先申请n个空格，然后将尾部数据向后赋值，然后用x把空出的位置填满。
iterator new_finish = reserve_elements_at_back(n);
iterator old_finish = finish;
const difference_type elems_after = difference_type(length) - elems_before;
pos = finish - elems_after;
__STL_TRY {
if (elems_after > difference_type(n)) {
iterator finish_n = finish - difference_type(n);
uninitialized_copy(finish_n, finish, finish);
finish = new_finish;
copy_backward(pos, finish_n, old_finish);
fill(pos, pos + difference_type(n), x_copy);
}
else {
__uninitialized_fill_copy(finish, pos + difference_type(n),
x_copy,
pos, finish);
finish = new_finish;
fill(pos, old_finish, x_copy);
}
}
__STL_UNWIND(destroy_nodes_at_back(new_finish));
}
}
//和上面的函数类似，只不过这里用于赋值的元素是由【first,last)决定的。
#ifdef __STL_MEMBER_TEMPLATES
template <class T, class Alloc, size_t BufSize>
template <class ForwardIterator>
void deque<T, Alloc, BufSize>::insert_aux(iterator pos,
ForwardIterator first,
ForwardIterator last,
size_type n)
{
const difference_type elems_before = pos - start;
size_type length = size();
if (elems_before < length / 2) {
iterator new_start = reserve_elements_at_front(n);
iterator old_start = start;
pos = start + elems_before;
__STL_TRY {
if (elems_before >= difference_type(n)) {
iterator start_n = start + difference_type(n);
uninitialized_copy(start, start_n, new_start);
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) - elems_before);
__uninitialized_copy_copy(start, pos, first, mid, new_start);
start = new_start;
copy(mid, last, old_start);
}
}
__STL_UNWIND(destroy_nodes_at_front(new_start));
}
else {
iterator new_finish = reserve_elements_at_back(n);
iterator old_finish = finish;
const difference_type elems_after = difference_type(length) - elems_before;
pos = finish - elems_after;
__STL_TRY {
if (elems_after > difference_type(n)) {
iterator finish_n = finish - difference_type(n);
uninitialized_copy(finish_n, finish, finish);
finish = new_finish;
copy_backward(pos, finish_n, old_finish);
copy(first, last, pos);
}
else {
ForwardIterator mid = first;
advance(mid, elems_after);
__uninitialized_copy_copy(mid, last, pos, finish, finish);
finish = new_finish;
copy(first, mid, pos);
}
}
__STL_UNWIND(destroy_nodes_at_back(new_finish));
}
}
#else /* __STL_MEMBER_TEMPLATES */
template <class T, class Alloc, size_t BufSize>
void deque<T, Alloc, BufSize>::insert_aux(iterator pos,
const value_type* first,
const value_type* last,
size_type n)
{
const difference_type elems_before = pos - start;
size_type length = size();
if (elems_before < length / 2) {
iterator new_start = reserve_elements_at_front(n);
iterator old_start = start;
pos = start + elems_before;
__STL_TRY {
if (elems_before >= difference_type(n)) {
iterator start_n = start + difference_type(n);
uninitialized_copy(start, start_n, new_start);
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) - elems_before);
__uninitialized_copy_copy(start, pos, first, mid, new_start);
start = new_start;
copy(mid, last, old_start);
}
}
__STL_UNWIND(destroy_nodes_at_front(new_start));
}
else {
iterator new_finish = reserve_elements_at_back(n);
iterator old_finish = finish;
const difference_type elems_after = difference_type(length) - elems_before;
pos = finish - elems_after;
__STL_TRY {
if (elems_after > difference_type(n)) {
iterator finish_n = finish - difference_type(n);
uninitialized_copy(finish_n, finish, finish);
finish = new_finish;
copy_backward(pos, finish_n, old_finish);
copy(first, last, pos);
}
else {
const value_type* mid = first + elems_after;
__uninitialized_copy_copy(mid, last, pos, finish, finish);
finish = new_finish;
copy(first, mid, pos);
}
}
__STL_UNWIND(destroy_nodes_at_back(new_finish));
}
}
template <class T, class Alloc, size_t BufSize>
void deque<T, Alloc, BufSize>::insert_aux(iterator pos,
const_iterator first,
const_iterator last,
size_type n)
{
const difference_type elems_before = pos - start;
size_type length = size();
if (elems_before < length / 2) {
iterator new_start = reserve_elements_at_front(n);
iterator old_start = start;
pos = start + elems_before;
__STL_TRY {
if (elems_before >= n) {
iterator start_n = start + n;
uninitialized_copy(start, start_n, new_start);
start = new_start;
copy(start_n, pos, old_start);
copy(first, last, pos - difference_type(n));
}
else {
const_iterator mid = first + (n - elems_before);
__uninitialized_copy_copy(start, pos, first, mid, new_start);
start = new_start;
copy(mid, last, old_start);
}
}
__STL_UNWIND(destroy_nodes_at_front(new_start));
}
else {
iterator new_finish = reserve_elements_at_back(n);
iterator old_finish = finish;
const difference_type elems_after = length - elems_before;
pos = finish - elems_after;
__STL_TRY {
if (elems_after > n) {
iterator finish_n = finish - difference_type(n);
uninitialized_copy(finish_n, finish, finish);
finish = new_finish;
copy_backward(pos, finish_n, old_finish);
copy(first, last, pos);
}
else {
const_iterator mid = first + elems_after;
__uninitialized_copy_copy(mid, last, pos, finish, finish);
finish = new_finish;
copy(first, mid, pos);
}
}
__STL_UNWIND(destroy_nodes_at_back(new_finish));
}
}
#endif /* __STL_MEMBER_TEMPLATES */
//在前面申请new_elements个空白的元素
template <class T, class Alloc, size_t BufSize>
void deque<T, Alloc, BufSize>::new_elements_at_front(size_type new_elements) {
size_type new_nodes = (new_elements + buffer_size() - 1) / buffer_size();
//首先根据要申请的元素的数目确定缓冲区需要增加的数目。
reserve_map_at_front(new_nodes);//增加map以能够匹配新增加的缓冲区
size_type i;
__STL_TRY {
for (i = 1; i <= new_nodes; ++i)
*(start.node - i) = allocate_node();//增加新的缓冲区，并把新缓冲区绑定到map上。
}
# ifdef __STL_USE_EXCEPTIONS
catch(...) {
for (size_type j = 1; j < i; ++j)
deallocate_node(*(start.node - j));
throw;
}
# endif /* __STL_USE_EXCEPTIONS */
}
//在后面申请new_elements个空白的元素，和在前面申请流程一样。
template <class T, class Alloc, size_t BufSize>
void deque<T, Alloc, BufSize>::new_elements_at_back(size_type new_elements) {
size_type new_nodes = (new_elements + buffer_size() - 1) / buffer_size();
reserve_map_at_back(new_nodes);
size_type i;
__STL_TRY {
for (i = 1; i <= new_nodes; ++i)
*(finish.node + i) = allocate_node();
}
# ifdef __STL_USE_EXCEPTIONS
catch(...) {
for (size_type j = 1; j < i; ++j)
deallocate_node(*(finish.node + j));
throw;
}
# endif /* __STL_USE_EXCEPTIONS */
}
template <class T, class Alloc, size_t BufSize>
void deque<T, Alloc, BufSize>::destroy_nodes_at_front(iterator before_start) {
for (map_pointer n = before_start.node; n < start.node; ++n)
deallocate_node(*n);
}
template <class T, class Alloc, size_t BufSize>
void deque<T, Alloc, BufSize>::destroy_nodes_at_back(iterator after_finish) {
for (map_pointer n = after_finish.node; n > finish.node; --n)
deallocate_node(*n);
}
//申请新的map，将老的数据拷贝过来。
template <class T, class Alloc, size_t BufSize>
void deque<T, Alloc, BufSize>::reallocate_map(size_type nodes_to_add,
bool add_at_front) {
size_type old_num_nodes = finish.node - start.node + 1;//当前有效map的大小。
size_type new_num_nodes = old_num_nodes + nodes_to_add;//获得新的有效map的大小。
map_pointer new_nstart;
if (map_size > 2 * new_num_nodes) {
//如果map的总大小>新的有效map的大小的2倍，那么不用申请新的map，直接
//把当前map中的数据移动下即可。
new_nstart = map + (map_size - new_num_nodes) / 2
+ (add_at_front ? nodes_to_add : 0);
if (new_nstart < start.node)
copy(start.node, finish.node + 1, new_nstart);
else
copy_backward(start.node, finish.node + 1, new_nstart + old_num_nodes);
}
else {
//如果需要申请新的map，那么首先确定下新的map的总大小。
size_type new_map_size = map_size + max(map_size, nodes_to_add) + 2;
//然后申请一块新的map.
map_pointer new_map = map_allocator::allocate(new_map_size);
new_nstart = new_map + (new_map_size - new_num_nodes) / 2
+ (add_at_front ? nodes_to_add : 0);
//将旧的map的数据拷贝过来。
copy(start.node, finish.node + 1, new_nstart);
map_allocator::deallocate(map, map_size);//释放掉旧的map。
//更新各种变量。
map = new_map;
map_size = new_map_size;
}
start.set_node(new_nstart);
finish.set_node(new_nstart + old_num_nodes - 1);
}
// Nonmember functions.
#ifndef __STL_NON_TYPE_TMPL_PARAM_BUG
template <class T, class Alloc, size_t BufSiz>
bool operator==(const deque<T, Alloc, BufSiz>& x,
const deque<T, Alloc, BufSiz>& y) {
return x.size() == y.size() && equal(x.begin(), x.end(), y.begin());
}
template <class T, class Alloc, size_t BufSiz>
bool operator<(const deque<T, Alloc, BufSiz>& x,
const deque<T, Alloc, BufSiz>& y) {
return lexicographical_compare(x.begin(), x.end(), y.begin(), y.end());
}
#endif /* __STL_NON_TYPE_TMPL_PARAM_BUG */
#if defined(__STL_FUNCTION_TMPL_PARTIAL_ORDER) && \
!defined(__STL_NON_TYPE_TMPL_PARAM_BUG)
template <class T, class Alloc, size_t BufSiz>
inline void swap(deque<T, Alloc, BufSiz>& x, deque<T, Alloc, BufSiz>& y) {
x.swap(y);
}
#endif
#if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
#pragma reset woff 1174
#endif
__STL_END_NAMESPACE
发表评论