文章目录

• 1、认识List
• 2、list模拟实现

1、认识List

List实际上是一个双向带头循环列表。

想要遍历List就使用迭代器，方括号只是特定的一种，而迭代器则是通用的。

	list lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);list::iterator it = lt.begin();while (it != lt.end()){cout << *it << " ";++it;}cout << endl;

列表库中提供了一个sort，不用算法库中的sort，是因为算法库中的sort用了快排，需要三数取中，这对于链表来讲很不高效。虽然模板语法上可传任意类型参数，但内部使用迭代器对迭代器有要求，库里接口参数的名字会暗示要传随机迭代器。

迭代器分为三种，单向，双向，随机。单向迭代器例子就是单链表，只能++；链表就是双向迭代器，可++，可–；vector，string的迭代器就是随机迭代器，++ – 以及加减都可用。

要求传单向也可以传双向，随机，要求传双向也可以传随机。

不过列表用sort，显而易见，性能不够好。

2、list模拟实现

写完这篇后我修改了一下，完整代码在这里：

https://gitee.com/kongqizyd/start-some-c-codes-for-learning.c/tree/master/List

先开个头

	templatestruct list_node{list_node* next;list_node* prev;T data;};templateclass list{typedef list_node node;public:list(){head = new node;head->prev = head;head->next = head;}private:node* _head;};

添加插入函数

	struct list_node{list_node* next;list_node* prev;T data;list_node(const T& x):next(nullptr), prev(nullptr), data(x){}};

		void push_back(const T& x){node* tail = head->prev;node* newnode = new node(x);tail->next = newnode;newnode->prev = tail;newnode->next = head;head->prev = newnode;}

如果是单纯的链表结构，那么用一个指针指向一个节点，++就能到下一个节点，但是现在创建的链表不是这样，它的类型是list_node < int >*类型的，解引用后就是list_node，不一定能++正确，它不像链表一样是连续的物理空间。再造一个结构体，里面做些重载函数。

现有一个类list和一个结构体list_node, 在list之前再加一个结构体。

	templatestruct _list_iterator{typedef list_node node;typedef _list_iterator self;node* _node;_list_iterator(node* n):_node(n){}T& operator*(){return _node->data;}self& operator++(){_node = _node->next;return *this;}bool operator!=(const self& s){return _node != s._node;}};

然后在list类里写上测试代码

	void Test_list1(){list lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);list::iterator it = lt.begin();while (it != lt.end()){cout << *it << " ";++it;}cout << endl;for (auto e : lt){cout << e << " ";}cout << endl;}

用struct写是为了公开代码，让代码不受限制。测试代码中的迭代器，begin赋值给it，是浅拷贝，因为我们没写拷贝构造，但是也过了；是因为这里没写析构函数，而且节点不需要释放，因为节点不是迭代器结构体的，而是其他结构体的，所以它没有资格释放。除此之外，前后置+±-以及等于和不等于函数

		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 tmp;}bool operator==(const self& s){return _node != s._node;}bool operator!=(const self& s){return _node != s._node;}

以及begin和end加上const版本和打印函数

		iterator begin(){return iterator(head->next);}iterator begin() const{return iterator(head->next);} iterator end(){return iterator(head);}iterator end() const{return iterator(head);}void print_list(const list& lt){list::iterator it = lt.begin();while (it != lt.end()){(*it) *= 2;cout << *it << " ";++it;}cout << endl;}

但是用const的begin和end构造出来的迭代器里面可以修改数值，这是因为他们构造出来普通迭代器，内容依然可以修改，const修饰的只是指针而已，不是内容。我们要返回const迭代器。

之前已经写过typedef _list_iterator< T > iterator，那么可不可以这样写
typedef const iterator const_iterator。

这就相当于T和T const，也就是这样把迭代器本身变成不可修改了。const迭代器应当可以++，我们要的是cosnt T*。

我们可以这样写，再创建一个结构体，然后把名字中加上const，和原有结构体区分开来。然后改一下这个函数

		const T& operator*(){return _node->data;}

list类里

	templateclass list{typedef list_node node;public:typedef _list_iterator iterator;typedef _list_const_iterator const_iterator;const_iterator end() const{return const_iterator(head);}const_iterator begin() const{return const_iterator(head->next);} 

打印函数里就是这样

list::const_iterator it = lt.begin();

然后把之前那个const结构体去掉，归到原先的结构体里，引入新的模板

	templatestruct _list_iterator{typedef list_node node;typedef _list_iterator self;node* _node;_list_iterator(node* n):_node(n){}Ref operator*(){return _node->data;}

	templateclass list{typedef list_node node;public:typedef _list_iterator iterator;typedef _list_iterator const_iterator;//typedef _list_const_iterator const_iterator;

如果传的是普通的，那就是T和T&。如果是const对象，那就是T和const T&，在_list_iterator结构体那里const T&就是Ref.

继续看迭代器的使用

	struct AA{int _a1;int _a2;AA(int a1, int a2):_a1(a1),_a2(a2){}};void test_list2(){list lt;lt.push_back(AA(1, 1));lt.push_back(AA(2, 2));lt.push_back(AA(3, 3));list::iterator it = lt.begin();while (it != lt.end()){cout << *it << " ";}cout << endl;}

程序会报错，因为it是AA的数据，需要重载<<。但还有别的办法

		list::iterator it = lt.begin();while (it != lt.end()){cout << it->_a1<< ":" << it->_a2 << " ";++it;}cout << endl;

本质是指针的迭代器，这样写貌似看起来更合理，那么就得重载->这个符号。在list_iterator写上这个函数

		T* operator->(){return &_node->data;}

其实本应当是it->->_a1。it一次解引用得到AA*，再次解引用得到AA，不过编译器就会识别为2个。原本的写法是这样：cout << it.operator->()->_a1 << “:” << it.operator->()->_a2 << " ";

如果这里是const，那么又要增加一个模板参数。

完善列表，写插入等函数。

		void push_back(const T& x){/*node* tail = head->prev;node* newnode = new node(x);tail->next = newnode;newnode->prev = tail;newnode->next = head;head->prev = newnode;*/insert(end(), x);}void push_front(const T& x){insert(begin(), x);}void pop_back(){erase(--end());}void pop_front(){erase(begin());}void insert(iterator pos, const T& x){node* cur = pos.node;node* _prev = cur->prev;node* newnode = new node(x);prev->next = newnode;newnode->prev = prev;newnode->next = cur;cur->prev = newnode;}void erase(iterator pos){assert(pos != end());node* prev = pos.node->prev;node* next = pos.node->next;prev->next = next;next->prev = prev;delete pos.node;}

写上clear函数以及要让erase函数传回来现在的位置还有析构函数。

		void clear(){iterator it = begin();while (it != end()){it = erase(it);}}

		iterator erase(iterator pos){assert(pos != end());node* prev = pos.node->prev;node* next = pos.node->next;prev->next = next;next->prev = prev;delete pos.node;return iterator(next);}

		~list(){clear();delete head;head = nullptr;}

迭代器区间函数，顺便改一下初始化。

		void empty_init(){head = new node;head->next = head;head->prev = head;}list(){empty_init();}templatelist(Iterator first, Iterator last){empty_init();while (firse != last){push_back(*first);++first;}}

拷贝构造，两种方式。

		void swap(list& tmp){std::swap(head, tmp.head);}list(const list& lt){/*empty_init();for (auto e : lt){push_back(e);}*/list tmp(lt.begin(), lt.end());swap(tmp)}

重载=

		list& operator=(list lt){swap(lt);return *this;}

结束。