list简介
- list可以在常数范围内在任意位置进行插入和删除的序列式容器，并且容器可以双向迭代。 - list底层是一个带头双向链表结构，通过指针连接前一个和后一个元素。 - list支持在任意位置进行插入、删除元素，效率更好。 - list不支持随机访问
list基本框架
namespace xty { //带头双向循环链表 template<class T> struct list_node { list_node<T>* _prev; list_node<T>* _next; T _data; }; template<class T> class list { typedef list_node<T> node; private: node* _head;//头指针 }; }
list构造函数
我们实现一个无参构造函数，但是在这之前我们需要做一些准备工作，先实现一个申请list_node的构造函数，在struct类里面实现。
list_node结构体的默认构造
//带头双向循环链表 template<class T> struct list_node { list_node<T>* _prev; list_node<T>* _next; T _data; //在创建list_node变量时，自动调用构造 list_node(const T& val = T()) :_prev(nullptr) ,_next(nullptr) ,_data(val) {} };
为什么不使用class，而使用struct呢？
因为我们想达到这样一个目的：想要让别人自由的访问自己的成员函数，不做任何限制，就用struct。而list_node，list是要经常使用的，因此使用struct修饰list_node比较方便。
list类的默认构造
仅仅申请一个空的头结点，next都指向头
list() { //两种申请方法都可以 //_head = new list_node<T> _head = new node; _head->next = _head; _head->prev = _head; //_head->_data已经在new的时候调用构造了 }
push_back()
先记录一下尾结点，插入更简单。
void push_back(const T& x) { //留记录尾结点 node* tail = _head->_prev; node* new_node = new node(x);//传入x值 tail->_next = new_node; new_node->_next = _head; _head->_prev = new_node; new_node->_prev = tail; }
teartor迭代器
整体框架：
//iteartor template<class T> struct __list_iterator { typedef list_node<T> node; node* _node;//成员变量 //构造函数 __list_iterator(node* x) :_node(x) {} T& operator*() { return _node->_data; } //++返回相应的迭代器 __list_iterator<T> operator++() { _node = _node->_next; return *this; } //是位置是否相等，不是内容是否相等。 bool operator!=(__list_iterator<T> x) { return _node != x._node; } }; template<class T> class list { typedef list_node<T> node; public: //迭代器重命名 typedef __list_iterator<T> iterator; public: //仅仅申请一个空的头结点，next都指向头 list() { //两种申请方法都可以 //_head = new list_node<T> _head = new node; _head->_next = _head; _head->_prev = _head; //_head->_data已经在new的时候调用构造了了 } iterator begin() { iterator it(_head->_next); return it; } iterator end() { return iterator(_head); }
语法细节理解：
- 为什么把iterator和list进行单独封装？写一块不好吗？
首先list只会用到迭代器的begin()和end()函数。其他的像++，其实都是通过迭代器的对象调用的（并不是list的对象调用的）。把iterator从list中抽离出来，不仅可以减少list的复杂性，还能让人更加清楚，迭代器其实也是一个模板，它能被抽离出来，用以实现各种数据结构的迭代！而list内部的begin和end接口，千篇一律。这样就达到的封装的目的！所以，还是分开写的好，逻辑更清晰，更容易维护。
2.struct __list_iterator结构体里面为什么要写构造函数呢？
在c++里struct也被当做是类！类里有构造函数很正常，还可以有拷贝构造呢！只不过struct默认是public的。这样我们在声明该类型的变量时，函数会自动调用构造函数，使该结构体的数据自动是被初始化过的。
xty::list<int>::iterator it = lt.begin(); //调用对象需要用list //xty::list<int>::iterator it(lt.begin()); //调用对象需要用list while (it != lt.end()) { cout << *it << endl; ++it; }
写了构造函数之后，第二种声明方式也是可以的。而第一种方式其实调用的是拷贝构造函数，但是编译器给优化成了拷贝构造，我们没有写拷贝构造，编译器会调用默认的拷贝构造，是一个浅拷贝。但是我们不是经常说浅拷贝会造成析构问题？这里为什么不会？因为我们没有写析构函数，而且析构函数。为什么不写析构函数呢？因为没有什么可以析构的，函数的结点是list里的内容，不需要迭代器的析构函数管，因此我们不写析构函数。
3.迭代器++返回的是迭代器的类型。
4.注意：_list_iterator是类名，_list_iterator才是类型！
5.list里面的begin要返回迭代器类型，然而怎么由指针转化成迭代器类型呢？要利用迭代器的构造函数来返回。
迭代器里面的其他接口
bool operator==(const __list_iterator<T>& x) { return _node == x._node; } //i++ __list_iterator<T> operator++(int) { __list_iterator<T> tem(*this); _node = _node->_next; return tem; } __list_iterator<T> operator--() { _node = _node->_prev; return *this; } __list_iterator<T> operator--(int) { __list_iterator<T> tem(*this); _node = _node->_prev; return tem; }
语法细节理解：
- 注意迭代器传进来的参数基本上都是迭代器，如果不更改，最好加上const和&。
- 如果命名空间冲突，注意在函数声明和定义的时候也要加上空间名。
void Print(xty::list<int>& lt);
- 我们发现__list_iterator 有点长，我们重命名一下。
//iteartor template<class T> struct __list_iterator { typedef list_node<T> node; typedef __list_iterator<T> self; node* _node;//成员变量 //构造函数 __list_iterator(node* x) :_node(x) {} T& operator*() { return _node->_data; } //++返回相应的迭代器 self operator++() { _node = _node->_next; return *this; } //是位置是否相等，不是内容是否相等。 bool operator!=(const __list_iterator<T>& x) { return _node != x._node; } bool operator==(const __list_iterator<T>& x) { return _node == x._node; } //i++ self operator++(int) { self tem(*this); _node = _node->_next; return tem; } self operator--() { _node = _node->_prev; return *this; } self operator--(int) { self tem(*this); _node = _node->_prev; return tem; } };
const迭代器
要实现const迭代器只需要再写一个const类即可。
记住是指针可以修改，但是内容不可以修改，因此不能在this那加const。
//迭代器重命名 typedef __list_iterator<T> iterator; typedef const__list_iterator<T> const_iterator; public: const_iterator begin()const { const_iterator it(_head->_next); return it; } const_iterator end()const { return const_iterator(_head); }
list里面的迭代器修改仅仅需要，typedef一下，然后将构造函数改成所需要的const类型即可。
而我们需要再实现一个const类型的iterator
template<class T> struct const__list_iterator { typedef list_node<T> node; typedef const__list_iterator<T> self; node* _node;//成员变量 //构造函数 const__list_iterator(node* x) :_node(x) {} const T& operator*() //值不仅可以修改！！ { return _node->_data; } //++返回相应的迭代器 self operator++() //指针可以修改！！ { _node = _node->_next; return *this; } //是位置是否相等，不是内容是否相等。 bool operator!=(const self& x)const { return _node != x._node; } bool operator==(const self& x)const { return _node == x._node; } //i++ self operator++(int) //指针可以修改！！！ { self tem(*this); _node = _node->_next; return tem; } self operator--() //指针可以修改！！！ { _node = _node->_prev; return *this; } self operator--(int) //指针可以修改！！！ { self tem(*this); _node = _node->_prev; return tem; } };
问题：代码写完之后，我们发现实际上只有operator*()的返回值加了const，其他的地方没有改，因此，我们利用模板参数赋用解决问题。
通过模板参数实现复用
template<class T,class Ref> struct __list_iterator { typedef list_node<T> node; typedef __list_iterator<T,Ref> self; node* _node;//成员变量 //构造函数 __list_iterator(node* x) :_node(x) {} Ref operator*() { return _node->_data; } ... } template<class T> class list { typedef list_node<T> node; public: //迭代器重命名 typedef __list_iterator<T, T&> iterator; typedef __list_iterator<T,const T&> const_iterator; public: //仅仅申请一个空的头结点，next都指向头 list() { //两种申请方法都可以 //_head = new list_node<T> _head = new node; _head->_next = _head; _head->_prev = _head; //_head->_data已经在new的时候调用构造了了 } }
通过增加类模板参数，这种问题被很巧妙的解决了。请好好体会！
operator->()
当我们遇到自定义类型数据链表时，访问数据就会比较麻烦。
struct AA { int _a1; int _a2; AA(int a1 = 0, int a2 = 0) :_a1(a1) , _a2(a2) {} }; void test_aa() { xty::list<AA> lt; lt.push_back(AA(1, 1)); lt.push_back(AA(2, 2)); lt.push_back(AA(3, 3)); lt.push_back(AA(4, 4)); xty::list<AA>::iterator it = lt.begin(); while (it != lt.end()) { cout << (*it)._a1 << ":" << (*it)._a2 << endl; ++it; } }
如上例子所示，cout方式，在这里很是别扭，因为it是迭代器，我们能不能通过重载->来访问这样的数据呢？
显然是可以的！如下：
T* operator->() { return &(_node->_data); }
所以我们通过如下方式打印链表的数据：
xty::list<AA>::iterator it = lt.begin(); while (it != lt.end()) { //cout << (*it)._a1 << ":" << (*it)._a2 << endl; cout << it->_a1 << ":" << it->_a2 << endl; ++it; }
但是这个代码是不是有一点别扭？没看出来的话，我再打印一次：
//两种打印方式一样！！！ cout << it->_a1 << ":" << it->_a2 << endl; cout << it.operator->()->_a1 << ":" << it.operator->()->_a2 << endl;
==解释：==之所以出现这样的原因，是因为编译器自动把两个连续的->优化成一个->，防止观感上的差异，这样设计能让人立马看出这个其实是在访问AA的数据。
为了适应const和非const两种迭代器，我们再设计一个模板参数。如下实例：
//iteartor template<class T,class Ref, class Ptr> struct __list_iterator { typedef list_node<T> node; typedef __list_iterator<T,Ref,Ptr> self; node* _node;//成员变量 Ptr operator->() { return &(_node->_data); } ................... } 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; public:
反向迭代器
库里面反向迭代器是用正向迭代器实现的！即把正向迭代器的++，重载成反向迭代器的–。
并且迭代器的rbegin()和rend()，恰好和正向迭代器相反！
具体实现
namespace xty { template<class Iterator, class Ref, class Ptr > struct RverseIterator { typedef RverseIterator<Iterator, Ref, Ptr> Self; Iterator _cur; //正向迭代器的对象 RverseIterator(Iterator it) :_cur(it) {} Ref operator*() { Iterator tem = _cur; --tem; return *tem; } //Iterator& operator++() //{ // _cur--; // return *this; //} Self& operator++() { _cur--; return *this; } Self& operator--() { _cur++; return *this; } bool operator!=(const Self& it) { return _cur != it._cur; } }; }
其中list类里面再添加typedef和rbegin和rend()内容！
其中list类里面再添加typedef和rbegin和rend()内容！
这样使用正向迭代器封装的反向迭代器就实现了
insert()
//在pos位置前插入,返回插入位置的迭代器 iterator insert(iterator pos, const T& x) { node* new_node = new node(x); node* cur = pos._node; node* prev = cur->_prev; prev->_next = new_node; new_node->_prev = prev; new_node->_next = cur; cur->_prev = new_node; return iterator(cur); }
erase()
返回删除元素的下一个位置的迭代器。
iterator erase(iterator pos) { //不能删头 assert(pos._node!=_head); node* cur = pos._node; node* prev = cur->_prev; prev->_next = cur->_next; cur->_next->_prev = prev; delete cur; return iterator(prev->_next) }
注意：删除元素后，pos位置的数据就被删除了，会产生迭代器失效问题，如果再使用pos需要重新赋值。
clear()
清空list的内容，可以借助迭代器和erase()来删除。
void clear() { iterator it = begin(); while (it != end()) { it = erase(it); //erase(it++); } }
析构函数
结合clear()来编写。
~list() { clear(); delete _head; _head = nullptr; }
迭代器区间构造
因为迭代器区间构造，也需要一个头结点，所以，我们方便复用，又定义了一个初始化函数，具体改动如下：
list() { empty_init(); //两种申请方法都可以 //_head = new list_node<T> //_head = new node; //_head->_next = _head; //_head->_prev = _head; //_head->_data已经在new的时候调用构造了了 } void empty_init() { _head = new node; _head->_next = _head; _head->_prev = _head; } template<class Iterator> list(Iterator first, Iterator last) { empty_init(); while (first != last) { push_back(*first); ++first; } }
拷贝构造
提供了两种方法，第一种方法效率较低，第二种利用swap提高了效率。
lt2(lt) //list(const list<T>& lt) //{ // empty_init(); // for (auto e : lt) // { // push_back(e); // } //} void swap(list<T>& tem) { std::swap(_head, tem._head); } list(const list<T>& lt) { empty_init();//初始化this list<T> tem(lt.begin(), lt.end()); swap(tem); }
operator=()
实现较为简单。
//注意这里不能传引用 list<T>& operator=(list<T> lt) { swap(lt); return *this; }
最后一个问题：
const list<int> lt;
这行代码能调用构造函数吗？
答案是肯定的，因为变量在最开始是没有const属性的，定义好了以后，才有const属性。否则const都没法定义出来了。
