微信手机网站搭建网站设计与推广

前言

各位读者朋友们大家好！上期我们讲了vector的使用以及底层的模拟实现，这期我们来讲list。

一. list的介绍及使用

1.1 list的介绍

list的文档

这里的list就是双向带头循环链表

1.2 list的使用

list的接口较多，我们要先掌握如何正确的使用，然后再去深入研究底层的原理，以达到可扩展的能力。以下是list的一些常见的重要接口。

1.2.1 list的构造

构造函数(Constructor)	接口说明
list (size_type n, const value_type& val = value_type())	构造的list中包含n个值为val的元素
list()	构造空的list
list(const list& x)	拷贝构造
list(InputItetator first,InputIterator last)	用一段迭代器区间构造list

• list (size_type n, const value_type& val = value_type())
  
• list()
  
• list(const list& x)
  
• list(InputItetator first,InputIterator last)
  

1.2.2 list iterator的使用

这里我们暂时将list的迭代器理解为指针，该指针指向list中的某一节点

函数声明	接口说明
begin + end	返回第一个元素的迭代器+返回最后一个元素下一个位置的迭代器
rbegin + rend	返回第一个元素的reverse_iterator，即end位置的迭代器+返回begin位置前一个位置的迭代器

可以看到这里的list的迭代器是双向的迭代器



如果想在某个位置插入元素就不能对迭代器进行+运算了
这里我们在第三个位置之前插入1314，要对begin进行三次自加，而不能使用begin+3

list<int> l(5, 520);
int k = 3;
list<int>::iterator it = l.begin();
while (k--)
{++it;
}
l.insert(it, 1314);
for (auto a : l)
{cout << a << " ";
}
cout << endl;

1.2.3 list capacity

函数声明	接口说明
empty	检测list是否为空，是返回true，否则返回false
size	返回list的有效节点个数

void test_list2()
{list<int> l1,l2;if (l1.empty()){cout << "true" << endl;cout << l1.size() << endl;}else{cout << "false" << endl;cout << l1.size() << endl;}l2.push_back(1314);cout << l2.size() << endl;
}

1.2.4 list element access

函数声明	接口说明
front	返回list的第一个节点中的值的引用
back	返回list的最后一个节点中的值的引用

void test_list3()
{list<int> l;l.push_back(520);l.push_back(520);l.push_back(520);l.push_back(520);for (auto a : l){cout << a << " ";}cout << endl;l.front() = 1314;l.back() = 1314;for (auto a : l){cout << a << " ";}
}

将第一个和最后一个位置的值改为了1314

1.2.5 list modifiers

函数声明	接口说明
push_front	在list首元素之前插入值为val的元素
pop_front	删除list的第一个元素
push_back	尾插值为val的元素
emplace_back	尾插一个元素
pop_back	将list的最后一个元素删除
insert	在pos位置插入值为val的元素
erase	删除pos位置的元素

• push_front
  

• pop_front
  

• push_back 和 pop_back
  

• emplace_back
  
  emplace_back在功能上跟push_back类似。但是emplace_back支持直接构造，不用再拷贝构造了，在最后一种情况下emplace_back比push_back高效。

• insert 和 erase
  

• splice
  
  将一个链表插到另一个链表的指定位置

void test_list4()
{list<int> lt1,lt2;lt1.push_back(520);lt1.push_back(520);lt2.push_back(1314);lt2.push_back(1314);lt1.splice(lt1.begin(), lt2);for (auto a : lt1){cout << a << " ";}cout << endl;for (auto a : lt2){cout << a << " ";}
}

插入后lt2就被置空了。
这一接口也可以用来调整结点的顺序

• merge
  
  这一功能的实现的是有序链表的合并
  
  将大的尾插到一个头节点后最后将头节点接到lt1上

上面就讲完了list常用接口的使用，下面我们开始模拟实现list

二. list的模拟实现

2.1 list的底层结构

template <class T>// 链表的节点
struct list_node
{T _data;list_node<T>* _next;list_node<T>* _prev;list_node(const T& x = T()):_data(x), _next(nullptr), _prev(nullptr){}
};template <class T>
class list
{typedef list_node<T> Node;
public:
list()
{_head = new Node;_head->_next = _head;_head->_prev = _head;_size = 0;
}
private:Node* _head;size_t _size;
};

2.2 普通迭代器

因为list的节点在内存中不是连续存储的，因此不能使用原生指针作为迭代器，我们可以封装一个类来作为迭代器，通过运算符重载来实现迭代器的功能。

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

2.3 const迭代器

但是这样要写成两个类，而且两个类的方法只有两个不同，很是冗余，有没有方法能实现成一个类呢？
我们看一下库里是如何实现的：

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){}Ptr operator -> (){return &_node->_data;}Ref operator*(){return _node->_data;}Self& operator++(){_node = _node->_next;return *this;}Self& operator++(int)// 后置++{Self tmp(*this);_node = _node->_next;return tmp;}Self& operator--(){_node = _node->_prev;return *this;}Self& operator--(int){Self tmp(*this);_node = _node->_prev;return *this;}bool operator==(const Self& s) const{return _node == s._node;}bool operator!=(const Self& s) const{return _node != s._node;}
};

写一段程序来体现一下实例化的过程

2.4 insert

iterator insert(iterator pos, const T& x)
{Node* newnode = new Node(x);Node* cur = pos._node;Node* prev = cur->_prev;// prev newnode curnewnode->_prev = prev;newnode->_next = cur;cur->_prev = newnode;prev->_next = newnode;++_size;return newnode;
}

有了insert我们可以服复用hinsert来实现push_back和push_front

void push_back(const T& x)
{insert(end(), x);
}
void push_front(const T& x)
{insert(begin(), x);
}

2.5 erase

将pos节点的前节点和后节点相连然后将pos节点释放即可

iterator erase(iterator pos)
{assert(pos != end());Node* next = pos._node->_next;Node* prev = pos._node->_prev;next->_prev = prev;prev->_next = next;delete pos._node;--_size;return next;
}

有了erase就可以复用erase来实现pop_back和pop_front了

void pop_back()
{erase(--end());
}
void pop_front()
{erase(begin());
}

2.6 迭代器失效

2.7 list的析构函数

~list()
{clear();delete _head;_head = nullptr;
}
void clear()
{auto it = begin();while (it != end()){it = erase(it);}
}

将所有节点删除之后再将头结点释放

2.9 list的构造函数

void empty_init()
{_head = new Node;_head->_next = _head;_head->_prev = _head;_size = 0;
}
list()
{empty_init();
}
list(const list<T>& tmp)
{empty_init();for (auto& a : tmp){push_back(a);}
}

构造一个头节点，将tmp的节点尾插到头节点后

2.8 operator=

	list<T>& operator=(list<T> tmp){swap(tmp);return *this;}

依旧是现代写法

三. 按需实例化

编译器在对模板进行实例化的时候，使用哪些成员函数就实例化哪些成员函数，不会全部实例化。

四. initializer_list

C++11中支持下面的写法：

不需要一直push_back数据，这里是因为支持了initializer_list

initializer_list底层是两个指针，第一个指针指向第一个数据，第二个指针指向最后一个数据的下一位置

我们写的list如果要支持这种写法需要写一个新的构造函数

list(initializer_list<T> il)
{empty_init();for (auto& a : il){push_back(a);}
}

跟普通的构造函数一样，只是参数变了而已，最正确的写法应该如下，因为我们是构造函数


这样就是隐式类型转换了

所以就有了下面的玩法：

五. list.h

namespace Yuey
{template <class T>// 链表的节点struct list_node{T _data;list_node<T>* _next;list_node<T>* _prev;list_node(const T& x = T()):_data(x), _next(nullptr), _prev(nullptr){}};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){}Ptr operator -> (){return &_node->_data;}Ref operator*(){return _node->_data;}Self& operator++(){_node = _node->_next;return *this;}Self& operator++(int)// 后置++{Self tmp(*this);_node = _node->_next;return tmp;}Self& operator--(){_node = _node->_prev;return *this;}Self& operator--(int){Self tmp(*this);_node = _node->_prev;return *this;}bool operator==(const Self& s) const{return _node == s._node;}bool operator!=(const Self& s) const{return _node != s._node;}};struct AA{int _a1 = 520;int _a2 = 1314;};template <class T>class list{typedef list_node<T> Node;public:typedef list_iterator<T, T&, T*> iterator;typedef list_iterator<T, const T&, const T*> const_iterator;void empty_init(){_head = new Node;_head->_next = _head;_head->_prev = _head;_size = 0;}list(){empty_init();}list(initializer_list<T> il){empty_init();for (auto& a : il){push_back(a);}}list(const list<T>& tmp){empty_init();for (auto& a : tmp){push_back(a);}}~list(){clear();delete _head;_head = nullptr;}void clear(){auto it = begin();while (it != end()){it = erase(it);}}void swap(list<T>& tmp){std::swap(_head, tmp._head);std::swap(_size, tmp._size);}list<T>& operator=(list<T> tmp){swap(tmp);return *this;}iterator begin(){return iterator(_head->_next);}iterator end(){return _head;}const_iterator begin() const{return const_iterator(_head->_next);}const_iterator end() const{return _head;}iterator insert(iterator pos, const T& x){Node* newnode = new Node(x);Node* cur = pos._node;Node* prev = cur->_prev;// prev newnode curnewnode->_prev = prev;newnode->_next = cur;cur->_prev = newnode;prev->_next = newnode;++_size;return newnode;}void push_back(const T& x){insert(end(), x);}void push_front(const T& x){insert(begin(), x);}iterator erase(iterator pos){assert(pos != end());Node* next = pos._node->_next;Node* prev = pos._node->_prev;next->_prev = prev;prev->_next = next;delete pos._node;--_size;return next;}void pop_back(){erase(--end());}void pop_front(){erase(begin());}private:Node* _head;size_t _size;};
}

结语

以上我们就讲完了list的用法以及模拟实现，希望对大家有所帮助，感谢大家的阅读，欢迎大家批评指正！