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(-) / 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(), finish(), end_of_storage() {}
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(), finish(), end_of_storage()
{
range_initialize(first, last, iterator_category(first));
}
#else /* __STL_MEMBER_TEMPLATES */
vector(const_iterator first, const_iterator last) {
size_type n = ;
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() - ); }
const_reference back() const { return *(end() - ); }
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 + != end())
copy(position + , 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 = ;
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 - ));
// 調整 finish
++finish;
T x_copy = x;
// 與 copy 本質相同,隻是從後面複制,可以避免區間有重疊時覆寫資料的問題
copy_backward(position, finish - , finish - );
*position = x_copy;
}
// 已無備用空間
else {
const size_type old_size = size();
const size_type len = old_size != ? * old_size : ;
// 以上配置原則為:
// 如果原大小為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 != ) {
// 備用空間大于等于新增元素個數
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 + != end())
copy(position + , 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 = ;
distance(begin(), end(), result);
return result;
}
size_type max_size() const { return size_type(-); }
// 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[];
int fill = ;
while (!empty()) {
carry.splice(carry.begin(), *this, begin());
int i = ;
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 = ; i < fill; ++i) counter[i].merge(counter[i-]);
swap(counter[fill-]);
}