概述
1. STL 中的容器
容器，置物之所也。STL 容器即是将运用最广的一些数据结构实现出来。如下图所示：
上图以内缩方式来表达基层和衍生层的关系。所谓衍生，并非派生关系，而是内含关系。例如 heap 内含一个 vector，priority-queue 内含一个 heap、stack、queue都内含一个 deque，set/map/multimap/multiset 都内含一个 RB-tree，hash_x 都内含一个 hashtable。
2. 序列式容器之 vector
所谓序列式容器，其中的元素都可序，但未必有序。
vector 的数据安排以及操作方式，与 array 非常相似。两者唯一的差别在于空间的运用灵活性。array 是静态空间，一旦配置了就不能改变，要换个更大（或小）的，就由客户端自己来：先配置一块新空间，然后将元素从旧址复制到新址，再把原来的空间释还给系统。vector 是动态空间，随着元素的加入，它的内部机制会自行扩充空间以容纳新元素。
vector 实现的关键在于其对大小的控制以及重新配置时数据移动的效率。
2.1 vector 的定义
vector 的定义如下：
class vector {
public:
typedef T value_type;
typedef value_type* pointer;
typedef const value_type* const_pointer;
typedef value_type* iterator;
typedef const value_type* const_iterator;
typedef value_type& reference;
typedef const value_type& const_reference;
typedef size_t size_type;
typedef ptrdiff_t difference_type;
#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:
typedef simple_alloc<value_type, Alloc> data_allocator; // SGI STL 空间配置器接口
iterator start; // 表示目前使用空间的头
iterator finish; // 表示目前使用空间的尾
iterator end_of_storage; // 表示目前可用空间的尾
void insert_aux(iterator position, const T& x);
void deallocate() { // 释放空间
if (start) data_allocator::deallocate(start, end_of_storage - start);
}
void fill_initialize(size_type n, const T& value) {
start = allocate_and_fill(n, value);
finish = start + n;
end_of_storage = finish;
}
public:
// 各种迭代器
iterator begin() { return start; }
const_iterator begin() const { return start; }
iterator end() { return finish; }
const_iterator end() const { return finish; }
reverse_iterator rbegin() { return reverse_iterator(end()); }
const_reverse_iterator rbegin() const { return const_reverse_iterator(end()); }
reverse_iterator rend() { return reverse_iterator(begin()); }
const_reverse_iterator rend() const { return const_reverse_iterator(begin()); }
// size、max_size、capacity、empty
size_type size() const { return size_type(end() - begin()); }
size_type max_size() const { return size_type(-1) / sizeof(T); }
size_type capacity() const { return size_type(end_of_storage - begin()); }
bool empty() const { return begin() == end(); }
// 重载 []
reference operator[](size_type n) { return *(begin() + n); }
const_reference operator[](size_type n) const { return *(begin() + n); }
// 构造函数，大都调用 fill_initialize
vector() : start(0), finish(0), end_of_storage(0) {}
vector(size_type n, const T& value) { fill_initialize(n, value); }
vector(int n, const T& value) { fill_initialize(n, value); }
vector(long n, const T& value) { fill_initialize(n, value); }
explicit vector(size_type n) { fill_initialize(n, T()); }
vector(const vector<T, Alloc>& x) {
start = allocate_and_copy(x.end() - x.begin(), x.begin(), x.end());
finish = start + (x.end() - x.begin());
end_of_storage = finish;
}
#ifdef __STL_MEMBER_TEMPLATES
template <class InputIterator>
vector(InputIterator first, InputIterator last) :
start(0), finish(0), end_of_storage(0)
{
range_initialize(first, last, iterator_category(first));
}
#else /* __STL_MEMBER_TEMPLATES */
vector(const_iterator first, const_iterator last) {
size_type n = 0;
distance(first, last, n);
start = allocate_and_copy(n, first, last);
finish = start + n;
end_of_storage = finish;
}
#endif /* __STL_MEMBER_TEMPLATES */
// 析构函数
~vector() {
destroy(start, finish);
deallocate();
}
vector<T, Alloc>& operator=(const vector<T, Alloc>& x);
void reserve(size_type n) {
if (capacity() < n) {
const size_type old_size = size();
iterator tmp = allocate_and_copy(n, start, finish);
destroy(start, finish);
deallocate();
start = tmp;
finish = tmp + old_size;
end_of_storage = start + n;
}
}
// 首尾元素
reference front() { return *begin(); }
const_reference front() const { return *begin(); }
reference back() { return *(end() - 1); }
const_reference back() const { return *(end() - 1); }
void push_back(const T& x) {
if (finish != end_of_storage) {
construct(finish, x);
++finish;
}
else
insert_aux(end(), x);
}
void swap(vector<T, Alloc>& x) {
__STD::swap(start, x.start);
__STD::swap(finish, x.finish);
__STD::swap(end_of_storage, x.end_of_storage);
}
// 插入操作
iterator insert(iterator position, const T& x) {
size_type n = position - begin();
if (finish != end_of_storage && position == end()) {
construct(finish, x);
++finish;
}
else
insert_aux(position, x);
return begin() + n;
}
iterator insert(iterator position) { return insert(position, T()); }
#ifdef __STL_MEMBER_TEMPLATES
template <class InputIterator>
void insert(iterator position, InputIterator first, InputIterator last) {
range_insert(position, first, last, iterator_category(first));
}
#else /* __STL_MEMBER_TEMPLATES */
void insert(iterator position,
const_iterator first, const_iterator last);
#endif /* __STL_MEMBER_TEMPLATES */
void insert (iterator pos, size_type n, const T& x);
void insert (iterator pos, int n, const T& x) {
insert(pos, (size_type) n, x);
}
void insert (iterator pos, long n, const T& x) {
insert(pos, (size_type) n, x);
}
// 删除最尾端元素
void pop_back() {
--finish;
destroy(finish);
}
//清除某位置上的元素
iterator erase(iterator position) {
if (position + 1 != end())
copy(position + 1, finish, position); // 后续元素往前移动
--finish;
destroy(finish);
return position;
}
// 清除迭代器所指定的区间的元素
iterator erase(iterator first, iterator last) {
iterator i = copy(last, finish, first);
destroy(i, finish);
finish = finish - (last - first);
return first;
}
// 重新设置 vector 大小，若设置值 new_size 大于当前 size，在尾端插入 x
void resize(size_type new_size, const T& x) {
if (new_size < size())
erase(begin() + new_size, end());
else
insert(end(), new_size - size(), x);
}
void resize(size_type new_size) { resize(new_size, T()); }
void clear() { erase(begin(), end()); }
protected:
// 配置空间并填满内容，其中__STL_TRY、__STL_UNWIND 为异常相关的宏，在 stl_config.h 中定义
iterator allocate_and_fill(size_type n, const T& x) {
iterator result = data_allocator::allocate(n);
__STL_TRY {
uninitialized_fill_n(result, n, x);
return result;
}
__STL_UNWIND(data_allocator::deallocate(result, n));
}
#ifdef __STL_MEMBER_TEMPLATES
template <class ForwardIterator>
iterator allocate_and_copy(size_type n,
ForwardIterator first, ForwardIterator last) {
iterator result = data_allocator::allocate(n);
__STL_TRY {
uninitialized_copy(first, last, result);
return result;
}
__STL_UNWIND(data_allocator::deallocate(result, n));
}
#else /* __STL_MEMBER_TEMPLATES */
iterator allocate_and_copy(size_type n,
const_iterator first, const_iterator last) {
iterator result = data_allocator::allocate(n);
__STL_TRY {
uninitialized_copy(first, last, result);
return result;
}
__STL_UNWIND(data_allocator::deallocate(result, n));
}
#endif /* __STL_MEMBER_TEMPLATES */
#ifdef __STL_MEMBER_TEMPLATES
template <class InputIterator>
void range_initialize(InputIterator first, InputIterator last,
input_iterator_tag) {
for ( ; first != last; ++first)
push_back(*first);
}
// This function is only called by the constructor. We have to worry
// about resource leaks, but not about maintaining invariants.
template <class ForwardIterator>
void range_initialize(ForwardIterator first, ForwardIterator last,
forward_iterator_tag) {
size_type n = 0;
distance(first, last, n);
start = allocate_and_copy(n, first, last);
finish = start + n;
end_of_storage = finish;
}
template <class InputIterator>
void range_insert(iterator pos,
InputIterator first, InputIterator last,
input_iterator_tag);
template <class ForwardIterator>
void range_insert(iterator pos,
ForwardIterator first, ForwardIterator last,
forward_iterator_tag);
#endif /* __STL_MEMBER_TEMPLATES */
};2.2 vector 的迭代器
vector 维护的是一个连续的线性空间，所以不论其元素型别如何，普通指针 都可以作为 vector 的迭代器而满足所有必要条件，因为 vector 迭代器所需要的操作行为，如 operator*，operator->，operator++， operator–， operator+，operator-，operator+=， operator-=，普通指针天生就具备。vector 支持随机存取，而普通指针正有这样的能力。所以，vector 提供的是 Random Access Iterators。
template <class T, class Alloc = alloc>
class vector
{
public:
typedef T value_type;
typedef value_type* iterator;
...
}根据定义，如果客户端写出这样的代码：
vector<int>::iterator ivite;
vector<Shape>::iterator svite;则，ivite 型别就是 int*，svite 的型别就是 Shape*。
2.3 vector 的数据结构
vector 所采用的数据结构非常简单：连续线性空间。它以；两个迭代器 start 和 finish 分别指向配置得来的连续空间中目前已被使用的范围，并以迭代器 end_of_storage 指向整块连续空间（含备用空间）的尾端：
template <class T, class Alloc = alloc>
class vector
{
...
protected:
iterator start; // 表示目前使用空间的头
iterator finish; // 表示目前使用空间的尾
iterator end_of_storage; // 表示目前可用空间的尾
}为了降低空间配置时的速度成本，vector 实际配置的大小可能比客户端需求量更大一些，以备将来可能的扩充。这便是容量（capacity）的概念。
添加新元素时，如果超出当时的容量，则容量会扩充至两倍，如果两倍容量仍不足，就扩充至足够大的容量。上述容量的扩张必须经历“重新配置、元素移动、释放空间”等过程。
2.4 vector 的构造和相关操作
vector 缺省使用 alloc 作为空间配置器，并据此定义出 data_allocator，为的是更方便的以元素大小作为配置单位：
template <class T, class Alloc = alloc>
class vector {
...
protected:
typedef simple_alloc<value_type, Alloc> data_allocator;
...
void deallocate() {
if (start) data_allocator::deallocate(start, end_of_storage - start);
}
void fill_initialize(size_type n, const T& value) {
start = allocate_and_fill(n, value);
finish = start + n;
end_of_storage = finish;
}
public:
vector(size_type n, const T& value) { fill_initialize(n, value); }
protected:
iterator allocate_and_fill(size_type n, const T& x) {
iterator result = data_allocator::allocate(n);
__STL_TRY {
uninitialized_fill_n(result, n, x);
return result;
}
__STL_UNWIND(data_allocator::deallocate(result, n));
}构造函数调用 fill_initialize，fill_initialize调用 allocate_and_fill，allocate_and_fill 调用 uninitialized_fill_n，uninitialized_fill_n 会根据第一参数的型别特性，决定使用算法 fill_n() 或反复调用 construct() 来完成任务。
void push_back(const T& x) {
if (finish != end_of_storage) {
construct(finish, x);
++finish;
}
else
insert_aux(end(), x);
}push_back：
push_back 插入元素 x，若还有备用空间，直接在备用空间上构造，并调整迭代器 finish。如果没有备用空间了，就扩充空间（重新配置、移动数据、释放原空间）：
template <class T, class Alloc>
void vector<T, Alloc>::insert_aux(iterator position, const T& x) {
// 还有备用空间
if (finish != end_of_storage) {
construct(finish, *(finish - 1));
// 调整 finish
++finish;
T x_copy = x;
// 与 copy 本质相同，只是从后面复制,可以避免区间有重叠时覆盖数据的问题
copy_backward(position, finish - 2, finish - 1);
*position = x_copy;
}
// 已无备用空间
else {
const size_type old_size = size();
const size_type len = old_size != 0 ? 2 * old_size : 1;
// 以上配置原则为：
// 如果原大小为0，则配置1；
// 如果原大小不为0，则配置为原来2倍，前半段用来放置数据，后半段准备用来放置新数据
iterator new_start = data_allocator::allocate(len);
iterator new_finish = new_start;
__STL_TRY {
// 将原 vector 拷贝至新 vector
new_finish = uninitialized_copy(start, position, new_start);
// 为新元素设定初值 x
construct(new_finish, x);
// 调整 new_finish
++new_finish;
// 将安插点的原内容也拷贝过来
new_finish = uninitialized_copy(position, finish, new_finish);
}
# ifdef __STL_USE_EXCEPTIONS
catch(...) {
destroy(new_start, new_finish);
data_allocator::deallocate(new_start, len);
throw;
}
# endif /* __STL_USE_EXCEPTIONS */
// 析构并释放原 vector
destroy(begin(), end());
deallocate();
// 调整迭代器
start = new_start;
finish = new_finish;
end_of_storage = new_start + len;
}
}注意：一旦对 vector 的操作引起空间重新配置，指向原 vector 的所有迭代器就全部失效。
pop_back：
void pop_back() {
--finish;
destroy(finish);
}insert：
template <class T, class Alloc>
void vector<T, Alloc>::insert(iterator position, size_type n, const T& x) {
// 当 n != 0 才进行以下所有操作
if (n != 0) {
// 备用空间大于等于新增元素个数
if (size_type(end_of_storage - finish) >= n) {
T x_copy = x;
const size_type elems_after = finish - position;
iterator old_finish = finish;
// 针对插入点后现有元素与新增元素个数的数量采取不同的操作
// 插入点后现有元素个数大于新增元素个数
if (elems_after > n) {
uninitialized_copy(finish - n, finish, finish);
finish += n;
copy_backward(position, old_finish - n, old_finish);
fill(position, position + n, x_copy);
}
// 插入点后现有元素个数小于等于新增元素个数
else {
uninitialized_fill_n(finish, n - elems_after, x_copy);
finish += n - elems_after;
uninitialized_copy(position, old_finish, finish);
finish += elems_after;
fill(position, old_finish, x_copy);
}
}
else {
// 备用空间小于新增元素个数（必须配置额外的内存）
// 首先决定新长度：旧长度的2倍，或者旧长度+新增元素个数
const size_type old_size = size();
const size_type len = old_size + max(old_size, n);
// 配置新的 vector 空间
iterator new_start = data_allocator::allocate(len);
iterator new_finish = new_start;
__STL_TRY {
new_finish = uninitialized_copy(start, position, new_start);
new_finish = uninitialized_fill_n(new_finish, n, x);
new_finish = uninitialized_copy(position, finish, new_finish);
}
# ifdef __STL_USE_EXCEPTIONS
catch(...) {
// 如有异常发生，实现 commit or rollback 语义
destroy(new_start, new_finish);
data_allocator::deallocate(new_start, len);
throw;
}
# endif /* __STL_USE_EXCEPTIONS */
// 清除并释放旧的 vector
destroy(start, finish);
deallocate();
// 调整迭代器
start = new_start;
finish = new_finish;
end_of_storage = new_start + len;
}
}
}erase：
iterator erase(iterator position) {
if (position + 1 != end())
copy(position + 1, finish, position);
--finish;
destroy(finish);
return position;
}
iterator erase(iterator first, iterator last) {
iterator i = copy(last, finish, first);
destroy(i, finish);
finish = finish - (last - first);
return first;
}resize 和 clear：
void resize(size_type new_size, const T& x) {
if (new_size < size())
erase(begin() + new_size, end());
else
insert(end(), new_size - size(), x);
}
void resize(size_type new_size) { resize(new_size, T()); }
void clear() { erase(begin(), end()); }3. 序列式容器之 list
相对于 vector 的连续线性空间，list 就显得复杂许多，它的好处是每次插入或删除一个元素，就配置或释放一个元素的空间。因此，list 对于空间的运用绝对精准，一点也不浪费。而且对于任何位置的元素插入或删除，list 都是常数时间。
list 和 vector 是两个最常用的容器。在什么时机下选择哪一种容器，必须视元素的多寡、元素构造复杂度（有无 non-trivial copy construct，non-trivial copy assignmen operator）、元素存取行为的特性而定。
3.1 list 的节点、迭代器和数据结构
每一个设计过 list 的人都知道，list 本身和 list 的节点是不同的结构，需要分开设计。以下是 STL list 的节点结构：
template <class T>
struct __list_node
{
typedef void* void_pointer; // 型别为 void*，其实可设为 __list_node<T>*
void_pointer prev;
void_pointer next;
T data;
};list_node_allocator(n) 表示配置 n 个节点空间。以下四个函数：
...
protected:
// 配置一个节点并返回
link_type get_node() { return list_node_allocator::allocate(); }
// 释放一个节点
void put_node(link_type p) { list_node_allocator::deallocate(p); }
// 产生一个节点，带有元素值
link_type create_node(const T& x) {
link_type p = get_node();
__STL_TRY {
construct(&p->data, x);
}
__STL_UNWIND(put_node(p));
return p;
}
// 销毁一个节点
void destroy_node(link_type p) {
destroy(&p->data);
put_node(p);
}
...list 提供许多构造函数，其中一个是默认构造函数，构造一个空的 list：
...
protected
void empty_initialize() {
node = get_node();
node->next = node;
node->prev = node;
}
public:
list() { empty_initialize(); }
...其他构造函数与 vector 类似，调用 fill_initialize：
void fill_initialize(size_type n, const T& value) {
empty_initialize();
__STL_TRY {
insert(begin(), n, value);
}
__STL_UNWIND(clear(); put_node(node));
}list 不再能够像 vector 一样以普通指针作为迭代器，因为其节点不保证在存储空间连续存在。list 的迭代器必须有能力指向 list 的节点，并有能力进行正确的递增、递减、取值、成员存取等操作。
由于 STL list 是一个双向链表，迭代器必须具备前移、后移的能力，所以 list 提供的迭代器是 Bidirectional Iterators。此外，list 的插入（insert）和接合 splice 都不会造成原有 list 迭代器失效，删除（erase）操作只会导致指向被删除的那个迭代器失效，其他迭代器不受影响。
以下是 list 迭代器的设计：
template<class T, class Ref, class Ptr>
struct __list_iterator {
typedef __list_iterator<T, T&, T*> iterator;
typedef __list_iterator<T, const T&, const T*> const_iterator;
typedef __list_iterator<T, Ref, Ptr> self;
typedef bidirectional_iterator_tag iterator_category;
typedef T value_type;
typedef Ptr pointer;
typedef Ref reference;
typedef __list_node<T>* link_type;
typedef size_t size_type;
typedef ptrdiff_t difference_type;
link_type node; // 指向 list 节点
__list_iterator(link_type x) : node(x) {}
__list_iterator() {}
__list_iterator(const iterator& x) : node(x.node) {}
bool operator==(const self& x) const { return node == x.node; }
bool operator!=(const self& x) const { return node != x.node; }
// 迭代器取值，取的是节点的数据值
reference operator*() const { return (*node).data; }
#ifndef __SGI_STL_NO_ARROW_OPERATOR
pointer operator->() const { return &(operator*()); }
#endif /* __SGI_STL_NO_ARROW_OPERATOR */
// 迭代器递增1，返回左值、右值
self& operator++() {
node = (link_type)((*node).next);
return *this;
}
self operator++(int) {
self tmp = *this;
++*this;
return tmp;
}
// 迭代器递减，返回左值、右值
self& operator--() {
node = (link_type)((*node).prev);
return *this;
}
self operator--(int) {
self tmp = *this;
--*this;
return tmp;
}
};3.2 list 的数据结构
SGI list 不仅仅是一个双向链表，还是循环双向链表。所以它只需一个指针，便可以完整表现整个链表：
template <class T, class Alloc = alloc>
class list {
protected:
typedef void* void_pointer;
typedef __list_node<T> list_node;
typedef simple_alloc<list_node, Alloc> list_node_allocator;
public:
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 list_node* link_type;
typedef size_t size_type;
typedef ptrdiff_t difference_type;
public:
typedef __list_iterator<T, T&, T*> iterator;
typedef __list_iterator<T, const T&, const T*> const_iterator;
...
protected:
link_type node;让指针 node 指向刻意置于尾端的一个空白节点，node 便能符合 STL 对于“前闭后开”区间的要求，成为 last 迭代器，如下函数便可轻易完成：
// begin、end、rbegin、rend
iterator begin() { return (link_type)((*node).next); }
const_iterator begin() const { return (link_type)((*node).next); }
iterator end() { return node; }
const_iterator end() const { return node; }
reverse_iterator rbegin() { return reverse_iterator(end()); }
const_reverse_iterator rbegin() const { return const_reverse_iterator(end()); }
reverse_iterator rend() { return reverse_iterator(begin()); }
const_reverse_iterator rend() const { return const_reverse_iterator(begin()); }
// empty、size、max_size
bool empty() const { return node->next == node; }
size_type size() const {
size_type result = 0;
distance(begin(), end(), result);
return result;
}
size_type max_size() const { return size_type(-1); }
// front、back
reference front() { return *begin(); }
const_reference front() const { return *begin(); }
reference back() { return *(--end()); }
const_reference back() const { return *(--end()); }3.3 list 的构造和相关操作
list 默认使用 alloc 作为空间配置器，并据此另外定义一个list list_node_allocator，为的是更方便地以节点大小配置单位：
template <class T, class Alloc = alloc>
class list {
protected:
...
typedef __list_node<T> list_node;
typedef simple_alloc<list_node, Alloc> list_node_allocator;
...
}list 的常见操作主要包括：insert、push_front、push_back、erase、pop_front、pop_back、clear、remove、unique、splice、merge、sort 等。
// 在指定节点插入一个节点
iterator insert(iterator position, const T& x) {
link_type tmp = create_node(x);
tmp->next = position.node;
tmp->prev = position.node->prev;
(link_type(position.node->prev))->next = tmp;
position.node->prev = tmp;
return tmp;
}
// 插入一个节点，作为头节点
void push_front(const T& x) { insert(begin(), x); }
// 插入一个节点，作为尾节点
void push_back(const T& x) { insert(end(), x); }
// 删除指定节点
iterator erase(iterator position) {
link_type next_node = link_type(position.node->next);
link_type prev_node = link_type(position.node->prev);
prev_node->next = next_node;
next_node->prev = prev_node;
destroy_node(position.node);
return iterator(next_node);
}
// 删除头节点
void pop_front() { erase(begin()); }
// 删除尾节点
void pop_back() {
iterator tmp = end();
erase(--tmp);
}
// 清空链表
template <class T, class Alloc>
void list<T, Alloc>::clear() {
link_type cur = (link_type) node->next;
while (cur != node) {
link_type tmp = cur;
cur = (link_type) cur->next;
destroy_node(tmp);
}
node->next = node;
node->prev = node;
}
// 移除指定值的元素
template <class T, class Alloc>
void list<T, Alloc>::remove(const T& value) {
iterator first = begin();
iterator last = end();
while (first != last) {
iterator next = first;
++next;
if (*first == value) erase(first);
first = next;
}
}
// 移除数值相同的连续元素
template <class T, class Alloc>
void list<T, Alloc>::unique() {
iterator first = begin();
iterator last = end();
if (first == last) return;
iterator next = first;
while (++next != last) {
if (*first == *next)
erase(next);
else
first = next;
next = first;
}
}
// 将 [first,last) 内的所有元素移动到 position 之前，是一个非公开接口
void transfer(iterator position, iterator first, iterator last) {
if (position != last) {
(*(link_type((*last.node).prev))).next = position.node;
(*(link_type((*first.node).prev))).next = last.node;
(*(link_type((*position.node).prev))).next = first.node;
link_type tmp = link_type((*position.node).prev);
(*position.node).prev = (*last.node).prev;
(*last.node).prev = (*first.node).prev;
(*first.node).prev = tmp;
}
}
// 接合操作：将某连续范围的元素从一个 list 移动到另一个（或者同一）list 的某个定点
// 为了提供各种接口弹性，list<T>::splice 有许多版本
void splice(iterator position, list& x) {
if (!x.empty())
transfer(position, x.begin(), x.end());
}
void splice(iterator position, list&, iterator i) {
iterator j = i;
++j;
if (position == i || position == j) return;
transfer(position, i, j);
}
void splice(iterator position, list&, iterator first, iterator last) {
if (first != last)
transfer(position, first, last);
}
// 将 x 合并到 *this 上，两个 lists 的内容都必须先经过递增排序
template <class T, class Alloc>
void list<T, Alloc>::merge(list<T, Alloc>& x) {
iterator first1 = begin();
iterator last1 = end();
iterator first2 = x.begin();
iterator last2 = x.end();
// 两个 list 都已是递增排序
while (first1 != last1 && first2 != last2)
if (*first2 < *first1) {
iterator next = first2;
transfer(first1, first2, ++next);
first2 = next;
}
else
++first1;
if (first2 != last2) transfer(last1, first2, last2);
}
// 翻转 list
template <class T, class Alloc>
void list<T, Alloc>::reverse() {
// 若链表尾空或者只有一个节点，则不进行任何操作
if (node->next == node || link_type(node->next)->next == node) return;
iterator first = begin();
++first;
while (first != end()) {
iterator old = first;
++first;
transfer(begin(), old, first);
}
}
// list 不能使用 STL 的 sort 算法，必须使用自己的 sort，采用的是 quick sort
// 原因是 STL 算法 sort 只接受 RamdonAccessIterator
template <class T, class Alloc>
void list<T, Alloc>::sort() {
// 若链表尾空或者只有一个节点，则不进行任何操作
if (node->next == node || link_type(node->next)->next == node) return;
list<T, Alloc> carry;
list<T, Alloc> counter[64];
int fill = 0;
while (!empty()) {
carry.splice(carry.begin(), *this, begin());
int i = 0;
while(i < fill && !counter[i].empty()) {
counter[i].merge(carry);
carry.swap(counter[i++]);
}
carry.swap(counter[i]);
if (i == fill) ++fill;
}
for (int i = 1; i < fill; ++i) counter[i].merge(counter[i-1]);
swap(counter[fill-1]);
}最后
以上就是机灵春天为你收集整理的STL 源码剖析读书笔记三：序列式容器之 vector、list的全部内容，希望文章能够帮你解决STL 源码剖析读书笔记三：序列式容器之 vector、list所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
发表评论 取消回复