list的使用和模拟实现

list 的使用

list 就是带头双向循环链表

要用到的头文件和命名空间

#include <iostream>
#include <list> //带头双向循环链表
#include <vector>
#include <initializer_list>
#include <algorithm>using namespace std;

构造

void test_list1()
{//无参构造list<int> lt1;//n个val构造list<int> lt2(10, 1);//迭代器区间构造vector<int> v1({1, 2, 3, 4, 5});list<int> lt3(lt2.begin(), lt2.end());list<int> lt4(v1.begin(), v1.end());//迭代器区间构造也可以传指针//指针就是一种特殊的迭代器，前提是指针是指向数组的指针//迭代器的行为本质模拟的就是指向数组的指针int a[] = { 1, 2, 3, 4 };list<int> lt5(a, a + 4);//initializer_list构造list<int> lt6 = { 1, 2, 3, 4, 5 };//拷贝构造list<int> lt7 = lt2;// 1、封装，通用的相似的遍历容器的方式，并且封装屏蔽容器结构的差异和底层实现细节// 2、通用/复用，实现算法时用迭代器函数模板方式实现，跟底层容器解耦list<int>::iterator it4 = lt4.begin();while (it4 != lt4.end()){cout << *it4 << " ";it4++;}cout << endl;for (auto e : lt4){cout << e << " ";}cout << endl;//一个算法，不是所有的容器都可以使用，算法对迭代器是有一些要求的，//算法迭代器名字就是要求，迭代器有：随机/单项/双向迭代器//单项<双向<随机，就是随机迭代器可以适用其他的迭代器的算法//因为随机可以看作特殊的双向，双向可以看作特殊的单项//例如：sort要求RandomAccessIterator，即容器迭代器是随机迭代器//vector就符合要求，但list的迭代器是BidirectionalIterator(双向迭代器)，不能使用sortsort(a, a + 4);sort(v1.begin(), v1.end());//sort(lt4.begin(), lt4.end()); //运行报错
}int main()
{test_list1();return 0;
}

void test_list2()
{list<int> lt1 = { 1, 2, 3, 4, 5, 6, 7 };// 尾插lt1.push_back(10);// 头插lt1.push_front(10);for (auto e : lt1){cout << e << " ";}cout << endl;// 改变lt1中元素个数lt1.resize(20, 4);for (auto e : lt1){cout << e << " ";}cout << endl;lt1.resize(3);for (auto e : lt1){cout << e << " ";}cout << endl;//因为list不能使用算法库的sort，所以自己实现了一个sort//算法库的sort用的快排，list内部实现的sort用的归并排序//它们的时间复杂度都是NlogN,但经过测验可知，要排的数据//少的时候可以用list内部的，数据量大的话最好用算法库里的//可以通过将list中的数据拷贝到vector，再排序，再拷贝回来的方式
}int main()
{test_list2();return 0;
}

测试算法库中的sort和list中的sort的快慢

void test_op1()
{srand(time(0));const int N = 1000000;list<int> lt;vector<int> v;for (int i = 0; i < N; ++i){auto e = rand() + i;lt.push_back(e);v.push_back(e);}int begin1 = clock();sort(v.begin(), v.end());int end1 = clock();int begin2 = clock();lt.sort();int end2 = clock();cout << "vector sort:" << end1 - begin1 << endl;cout << "list sort:" << end2 - begin2 << endl;}int main()
{test_op1();return 0;
}

void test_op2()
{srand(time(0));const int N = 1000000;list<int> lt1;list<int> lt2;for (int i = 0; i < N; ++i){auto e = rand() + i;lt1.push_back(e);lt2.push_back(e);}int begin1 = clock();//拷贝vectorvector<int> v(lt1.begin(), lt1.end());//排序sort(v.begin(), v.end());//拷贝回lt1lt1.assign(v.begin(), v.end());int end1 = clock();int begin2 = clock();lt2.sort();int end2 = clock();cout << "list copy vector sort copy list sort:" << end1 - begin1 << endl;cout << "list sort:" << end2 - begin2 << endl;}int main()
{test_op2();return 0;
}

void test_list3()
{//merge归并排序list<double> first, second;first.push_back(3.1);first.push_back(2.2);first.push_back(2.9);second.push_back(3.7);second.push_back(7.1);second.push_back(1.4);//归并排序前提：两个list对象都已经有序first.sort();second.sort();//归并后，second的数据全在first，second为空first.merge(second);cout << "first:";for (auto e : first){cout << e << " ";}cout << endl;cout << "second:";for (auto e : second){cout << e << " ";}cout << endl << endl;//unique去掉重复的数据list<int> lt1 = { 2, 3, 1, 3, 5, 4, 6, 1, 8, 9, 0, 1, 2 };//去重之前要排好序lt1.sort();lt1.unique();for (auto e : lt1){cout << e << " ";}cout << endl << endl;//remove删除val这个值,如果这个值有多个，就全删list<int> lt2 = { 2, 3, 1, 3, 5, 4, 6, 1, 8, 9, 0, 1, 2 };for (auto e : lt2){cout << e << " ";}cout << endl;lt2.remove(2);for (auto e : lt2){cout << e << " ";}cout << endl << endl;//splice转移，将一个迭代器或迭代器区间中的值转移到pos迭代器位置之前//可以在同一个对象中转移，也可以在两个不同对象中转移list<int> lt3 = { 1, 2, 3, 4, 5, 6 };for (auto e : lt3){cout << e << " ";}cout << endl;auto it3 = find(lt3.begin(), lt3.end(), 5);if (it3 != lt3.end()){//将5转移到头部位置lt3.splice(lt3.begin(), lt3, it3);}for (auto e : lt3){cout << e << " ";}cout << endl;list<int> lt4 = { 7, 8, 9, 10 };cout << "转移前lt3:";for (auto e : lt3){cout << e << " ";}cout << endl;cout << "转移前lt4:";for (auto e : lt4){cout << e << " ";}cout << endl;//将lt4中的数据转移到lt3的头部位置lt3.splice(lt3.begin(), lt4, lt4.begin(), lt4.end());cout << "转移后lt3:";for (auto e : lt3){cout << e << " ";}cout << endl;cout << "转移后lt4:";for (auto e : lt4){cout << e << " ";}cout << endl;
}int main()
{test_list3();return 0;
}

list 的模拟实现

list.h

#pragma oncenamespace bs
{//节点template<class T>struct list_node{T _data;list_node<T>* _next;list_node<T>* _prev;list_node(const T& val = T()):_data(val),_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){}Ref& operator*(){return _node->_data;}Ptr 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 tmp;}bool operator!=(const Self& it) const{return _node != it._node;}bool operator==(const Self& it) const{return _node == it._node;}};//链表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;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;}list(){empty_init();}//lt2(lt1)//list(const list<T>& lt)list(const list& lt) //在类里面可以不加模板参数{empty_init();for (const auto& e : lt){push_back(e);}}list(initializer_list<T> il){empty_init();for (const auto& e : il){push_back(e);}}void swap(list<T>& lt){std::swap(_head, lt._head);std::swap(_size, lt._size);}//lt1 = lt3list<T>& operator=(list<T> lt){swap(lt);return *this;}lt1 = lt3//list<T>& operator=(const list<T>& lt)//{//	if (this != &lt)//	{//		clear();//		for (const auto& e : lt)//		{//			push_back(e);//		}//	}//	return *this;//}~list(){clear();delete _head;_head = nullptr;}void clear(){iterator it = begin();while (it != end()){it = erase(it);}}void push_back(const T& x){insert(end(), x);}void push_front(const T& x){insert(begin(), x);}void pop_back(){erase(--end());}void pop_front(){erase(begin());}iterator insert(iterator pos, const T& val){Node* cur = pos._node;Node* prev = cur->_prev;Node* newnode = new Node(val);//prev newnode curprev->_next = newnode;newnode->_next = cur;cur->_prev = newnode;newnode->_prev = prev;++_size;//返回新插入节点位置的迭代器return iterator(newnode);}iterator erase(iterator pos){Node* cur = pos._node;Node* prev = cur->_prev;Node* next = cur->_next;//prev cur nextprev->_next = next;next->_prev = prev;delete cur;--_size;//返回下一个位置的迭代器//return iterator(next);return next; //单参数构造函数的隐式类型转换}size_t size(){//size_t n = 0;//for (auto& e : *this)//{//	++n;//}//return n;return _size;}private:Node* _head;size_t _size = 0;};}

test.cpp

#include "list.h"namespace bs
{template<class T>void Print(const bs::list<T>& lt){//类模板未实例化，不能去类模板中找后面的东西//编译器就分不清const_iterator是嵌套类型还是静态成员变量//typename告诉编译器，我确认过了这里是类型//typename list<T>::const_iterator it = lt.begin();auto it = lt.begin();while (it != lt.end()){//it += 1; //const迭代器，指向内容不能修改cout << *it << " ";++it;}cout << endl;}void test_list1(){bs::list<int> lt1;lt1.push_back(1);lt1.push_back(2);lt1.push_back(3);lt1.push_back(4);bs::list<int>::iterator it1 = lt1.begin();while (it1 != lt1.end()){cout << *it1 << " ";++it1;}cout << endl;}void test_list2(){bs::list<int> lt1;lt1.push_back(1);lt1.push_back(2);lt1.push_back(3);lt1.push_back(4);bs::list<int>::iterator it1 = lt1.begin();while (it1 != lt1.end()){*it1 += 1; //迭代器，指向内容可以修改cout << *it1 << " ";++it1;}cout << endl;Print(lt1);}struct Pos{int _row;int _col;Pos(int row = 0, int col = 0):_row(row),_col(col){}};void test_list3(){bs::list<Pos> lt1;lt1.push_back({ 1, 1 });lt1.push_back({ 2, 2 });lt1.push_back({ 3, 3 });lt1.push_back({ 4, 4 });//bs::list<Pos>::iterator it1 = lt1.begin();auto it1 = lt1.begin();while (it1 != lt1.end()){//cout << (*it1)._row << ":" << (*it1)._col << endl;//为了可读性，这里省略了一个->//cout << it1->_row << ":" << it1->_col << endl;cout << it1.operator->()->_row << ":" << it1.operator->()->_col << endl;++it1;}cout << endl;}void test_list4(){bs::list<int> lt1;lt1.push_back(1);lt1.push_back(2);lt1.push_back(3);lt1.push_back(4);Print(lt1);lt1.push_front(10);lt1.push_front(20);Print(lt1);lt1.pop_front();lt1.pop_front();Print(lt1);lt1.pop_back();lt1.pop_back();Print(lt1);}void test_list5(){bs::list<int> lt1;lt1.push_back(1);lt1.push_back(2);lt1.push_back(3);lt1.push_back(4);Print(lt1);bs::list<int> lt2 = lt1;Print(lt2);bs::list<int> lt3 = { 10, 20, 30 };lt1 = lt3;Print(lt1);}void test_list6(){bs::list<int> lt1 = { 10, 20, 30 };Print(lt1);bs::list<double> lt2 = { 10.1, 20.1, 30.1 };Print(lt2);}
}int main()
{bs::test_list6();//test_op2();return 0;
}