C++ : STL容器之list剖析

STL容器之list剖析

一、几个重要接口（一）push_back 与 emplace_back（二）sort1、系统中的sort2、list中的sort （三）splice（四）unique 和 merge1、unique2、merge 二、list的模拟实现（一）结点类的实现（二）迭代器的实现1、->运算符重载 （三）list实现 三、结束语

一、几个重要接口

（一）push_back 与 emplace_back

push_back 和emplace_back的用法大致是一致的，只是二者在一种特定情况下 emplace_back 相比于 push_back 更优一些。

class Pos{public:int _row;int _col;Pos(int row = 0, int col = 0):_row(row), _col(col){cout << "Pos(int row, int col)" << endl;}Pos(const Pos& p):_row(p._row), _col(p._col){cout << "Pos(const Pos& p)" << endl;}};void test03() {list<Pos> lt;// 构造+拷贝构造Pos p1(1, 1);lt.push_back(p1);//lt.push_back((2, 2));    //这种写法不对，//隐式类型转换针对的是构造函数，这里是括号运算符lt.push_back(Pos(2, 2));lt.push_back({3,3});lt.emplace_back(p1);lt.emplace_back(Pos(2, 2));//lt.emplace_back({ 3,3 });// 直接构造lt.emplace_back(3, 3);}

我们采用push_back往链表尾部插入元素，可以分为三种情况：

1、先构造一个Pos类型，然后调用拷贝构造
2、使用匿名对象构造，在调用拷贝构造。
3、使用initializer_list初始化，在拷贝构造。

如果我们将其换成emplace_back，那么前面两种情况和push_back相同，而不再支持initializer_list，直接调用构造即可，因此这种情况更优。

（二）sort

在list中实现了一个排序sort,我们知道在标准库里面也有一个全局的sort，为什么还要单独实现呢？其实list容器无法使用这个sort，这里我们需要引入迭代器的分类。

前面的迭代器我们曾经分为iterator,const_iterator,reverse_iterator, const_reverse_iterator这几种，下面我们按照新的方式来分类迭代器。

1、单项迭代器：只能正向访问，支持++
2、双向迭代器：可以双向访问支持++, –
3、随机迭代器：支持++， --， +， -

系统中sort采取的是双向迭代器，故而不能使用。因此单独实现了这个sort函数。

1、系统中的sort

我们只需要给出随机迭代器的首尾迭代器，就可以对容器进行排序，默认情况下给出的是按照升序排列，如果想降序，可以使用greater类对象。

void test04() {vector<int> v1 = { 1,20,3,-4,5 };for (auto e : v1){cout << e << " ";}cout << endl;//sort(v1.begin(), v1.end());sort(v1.begin(), v1.end(), greater<int>());for (auto e : v1){cout << e << " ";}cout << endl;}

2、list中的sort

void test05() {/*greater<int> gt;    lt1.sort(gt);*/list<int> lt1 = { 1,54,23,5,53,34 };    lt1.sort(greater<int>());for (auto e : lt1){cout << e << " ";}}

（三）splice

将一个链表中的一个/多个结点转移到另外一个链表的position 位置处·。

在这里，我们还可以使用splice函数实现选择当前的一个结点，将它放在当前链表的链表头位置。

void test06(){list<int> lt1 = { 1,2,3,4,5 };// LRUint x;while (cin >> x){auto pos = find(lt1.begin(), lt1.end(), x);if (pos != lt1.end()){lt1.splice(lt1.begin(), lt1, pos);}for (auto e : lt1){cout << e << " ";}cout << endl;}}

（四）unique 和 merge

把这两个函数放在一起是因为在使用这两个函数之前都需要对list进行排序。

1、unique

将链表进行去重操作。

2、merge

将两个有序链表进行归并操作。

void test07() {list<int> l1({ 2,4,2,5,7,8,6,3,3 });list<int> l2({ 21,42,42,5,57,86,68,32,3 });l1.sort();l2.sort();l1.merge(l2);for (auto& x : l1) {cout << x << " ";}cout << endl;l1.unique();for (auto& x : l1) {cout << x << " ";}}

二、list的模拟实现

（一）结点类的实现

考虑到泛型编程的特点，我们在创建默认构造的时候，使用临时对象充当缺省参数。

template<class T>struct list_node {T _data;list_node* _prev;list_node* _next;list_node(const T& data = T()):_data(data), _prev(nullptr), _next(nullptr){};};

（二）迭代器的实现

我们知道，在之前的string和vector中，我们使用了原生指针做迭代器，是因为它具有连续的物理空间，而链表的实现则需要使用到类。

在实现const_iterator的时候，不可以简单的用const list_iterator来定义，此时类里面的指针也不能够被改变。

我们知道，const迭代器希望访问的元素不能被修改，因此我们只需要保证&以及->得到的值不会改变即可。
在这里，std库里面有一个十分巧妙的方法，添加了两个模板参数，实现了const_iterator和iterator两个类的融合。

1、->运算符重载

->运算符返回的是链表结点类型元素的数值信息的地址

Ptr* operator->(){return &_node->_data;}

需要注意的是，我们在取相应位置的元素时，只需要写一个->即可拿到相应的数据。

void test03() {    list<Pos> lt;// 构造+拷贝构造Pos p1(1, 1);lt.push_back(p1);// 为了可读性，特殊处理，省略了一个->auto it2 = lt.begin();cout << it2->_row << ":" << it2->_col << endl;cout << it2.operator->()->_row << ":" << it2.operator->()->_col << endl;}

template<class T, class Ref, class Ptr>struct list_iterator {typedef list_node<T> Node;typedef list_iterator<T, Ref, Ptr> Self;Node* _node;list_iterator(Node* node):_node(node){}Ref& operator* (){return _node->_data;}Ptr* operator->(){return &_node->_data;}Self& operator++(){_node = _node->_next;return *this;}Self& operator--(){_node = _node->_prev;return *this;}Self operator++(int){Self tmp(_node);_node = _node->_next;return tmp;}Self operator--(int){Self tmp(_node);_node = _node->_prev;return tmp;}bool operator!=(const Self& s){return s._node != _node;}};

（三）list实现

list实现的是一个有头双向循环链表，维护两个值，_head和_size。

实现要点：
1、typedef 在这里相当于实现了一个内部类
2、迭代器的返回值一定要有构造函数，不可以直接返回结点，小编当时走火入魔以为可以隐式类型转换，发生错误。
3、建议多使用复用，在这里我们只用实现insert和erase操作，即可完成其他操作的复写。同时，在维护_size时，只需要在这两个函数里面维护即可。

template<class T>class list{typedef list_node<T> Node;public:/*typedef list_iterator<T> iterator;typedef list_const_iterator<T> const_iterator;*/typedef list_iterator<T, T&, T*> iterator;typedef list_iterator<T, const T&, const T*> const_iterator;iterator begin(){return iterator(_head->_next);}iterator end(){return iterator(_head);}const_iterator begin() const{return const_iterator(_head->_next);}const_iterator end() const{return const_iterator(_head);}void empty_init(){_head = new Node();_head->_next = _head;_head->_prev = _head;_size = 0;}list(){empty_init();}// lt2(lt1)list(const list<T>& lt){empty_init();for (auto& e : lt){push_back(e);}}// lt2 = lt3//list& operator=(list lt)list<T>& operator=(list<T> lt){swap(lt);return *this;}~list(){clear();delete _head;_head = nullptr;}void swap(list<T>& tmp){std::swap(_head, tmp._head);std::swap(_size, tmp._size);}void clear(){auto it = begin();while (it != end()){it = erase(it);}}list(size_t n, const T& val = T()){empty_init();for (size_t i = 0; i < n; i++){push_back(val);}}void push_back(const T& x){/*Node* new_node = new Node(x);Node* tail = _head->_prev;tail->_next = new_node;new_node->_prev = tail;new_node->_next = _head;_head->_prev = new_node;*/insert(end(), x);}void push_front(const T& x){insert(begin(), x);}void pop_front(){erase(begin());}void pop_back(){erase(--end());}iterator insert(iterator pos, const T& val){Node* cur = pos._node;Node* newnode = new Node(val);Node* prev = cur->_prev;// prev newnode curprev->_next = newnode;newnode->_prev = prev;newnode->_next = cur;cur->_prev = newnode;++_size;return iterator(newnode);}iterator erase(iterator pos){assert(pos != end());Node* del = pos._node;Node* prev = del->_prev;Node* next = del->_next;prev->_next = next;next->_prev = prev;delete del;--_size;return iterator(next);}private:Node* _head;size_t _size;};

三、结束语

介绍完vector和sting之后，防止过于繁琐，后面的文章都是重点讲解一些特殊成员对象。感谢小伙伴一如既往的支持！