1.list

vector:顺序表

list:链表

为什么会有list?

补充vector的缺点存在的

vector缺点:

1.头部和中部的插入删除效率低 O(N) 因为需要挪动数据

2.插入数据空间不够需要增容 增容需要开新空间 拷贝数据 释放旧空间 会付出很大代价

优点:

1.支持下标的随机访问 间接的就很好的支持排序 二分查找 堆算法

list就是为了解决vector的缺陷

优点:

1.list头部 中间插入不再需要挪动数据 效率高 O(1)

2.list插入数据是新增节点 不需要增容

缺点:

1.不支持随机访问

所以实际使用中vector和list是两个相辅相成的容器

2.使用

1°四个默认构造函数/迭代器

//const迭代器
void print_list(const list& lt)
{list::const_iterator it = lt.begin();while (it != lt.end()){cout << *it << " ";++it;}cout << endl;
}void test_list1()
{list lt1;//构造lt1.push_back(1);lt1.push_back(2);lt1.push_back(3);lt1.push_back(4);//迭代器list::iterator it1 = lt1.begin();while (it1 != lt1.end()){cout << *it1 << " ";++it1;}cout << endl;list lt2(lt1);//拷贝构造print_list(lt2);list lt3;lt3.push_back(10);lt3.push_back(20);lt3.push_back(30);lt3.push_back(40);lt1 = lt3;//赋值//只要一个容器支持迭代器 就可以使用范围for的操作//范围forfor (auto e : lt1){cout << e << " ";}cout << endl;//reverse 逆置//reserve 保留//反向迭代器list::reverse_iterator rit1 = lt1.rbegin();while (rit1 != lt1.rend()){cout << *rit1 << " ";++rit1;}cout << endl;
}

2°尾插/尾删

void test_list2() 
{list lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);lt.push_front(0);lt.push_front(-1);print_list(lt);lt.pop_back();lt.pop_front();print_list(lt);
}

3°插入/删除/查找

void test_list3()
{list lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);lt.push_back(5);lt.push_back(6);print_list(lt);//lt.insert(lt.begin() + 3, 30);//不支持 链表加不到 空间不连续 vector支持//在3的前面插入30list::iterator pos = find(lt.begin(), lt.end(), 3);if (pos != lt.end()){lt.insert(pos, 30);//3前面插入30 //这里insert以后失效了嘛?lt.erase(pos);//删除3}print_list(lt);
}

4°逆置/排序

void test_list4()
{list lt;lt.push_back(3);lt.push_back(2);lt.push_back(1);lt.push_back(5);print_list(lt);//从小到大lt.sort();print_list(lt);//从大到小lt.reverse();print_list(lt);
}

5°迭代器失效

//list迭代器失效
void test_list5()
{list lt;lt.push_back(3);lt.push_back(2);lt.push_back(1);lt.push_back(5);lt.push_back(4);lt.push_back(6);//删除所有的偶数list::iterator it = lt.begin();while (it != lt.end()){if (*it % 2 == 0){it = lt.erase(it);//erase后这个位置就一句失效了 需要拿it接收//cout << *it << endl;//失效后解引用就直接报错 所以要拿it接收}else{++it;}}print_list(lt);//lt.erase(it);//这个没有问题 it失效了 没有用it 所以没有事//*it//再用it 就有问题//迭代器失效了没有什么事 但访问失效的迭代器就会有问题//迭代器失效的总结://1.vector的iterator insert(push_back) erase都会导致失效//2.list的iterator erase会导致失效
}

3.底层实现

底层是带头的双向循环链表

1°构造

namespace szh
{//链表相关数据templatestruct __list_node{__list_node* _next;__list_node* _prev;T _data;//构造__list_node(const T& x = T())//全缺省 构造传参 :_data(x),_next(nullptr),_prev(nullptr){}};//链表类templateclass list{typedef __list_node Node;public://带头双向循环链表//构造list(){_head = new Node;_head->_next = _head;_head->_prev = _head;}private:Node* _head;};
}

• 先定义一个struct结构体 next prev data
• typedef一下 后面方便new空间

2°析构

namespace szh
{//链表相关数据templatestruct __list_node{__list_node* _next;__list_node* _prev;T _data;//构造__list_node(const T& x = T())//全缺省 构造传参 :_data(x),_next(nullptr),_prev(nullptr){}};//链表类templateclass list{typedef __list_node Node;public://删数据void clear(){iterator it = begin();while (it != end()){erase(it++);//一个一个删数据}}//析构 整个都不要 头结点直接干掉~list(){clear();delete _head;//头节点也删除_head = nullptr;//制空}private:Node* _head;};
}

• 利用迭代器遍历+erase

3°拷贝构造

namespace szh
{//链表相关数据templatestruct __list_node{__list_node* _next;__list_node* _prev;T _data;//构造__list_node(const T& x = T())//全缺省 构造传参 :_data(x),_next(nullptr),_prev(nullptr){}};//链表类templateclass list{typedef __list_node Node;public://拷贝构造 lt2(lt1)list(const list& lt){_head = new Node;_head->_next = _head;_head->_prev = _head;类里面不需要指定迭代器类型利用迭代器进行尾插//const_iterator it = lt.begin();//while (it != lt.end())//{//	//this->pop_back(*it);//	push_back(*it);//	++it;//}//范围for更简洁for (auto e : lt)push_back(e);}private:Node* _head;};
}

• 迭代器遍历或者范围for遍历

4°赋值

namespace szh
{//链表相关数据templatestruct __list_node{__list_node* _next;__list_node* _prev;T _data;//构造__list_node(const T& x = T())//全缺省 构造传参 :_data(x),_next(nullptr),_prev(nullptr){}};//链表类templateclass list{typedef __list_node Node;public:赋值 lt1=lt3 //list& operator=(const list& lt)//{//	if (this != <)//不同//	{//		clear();//先释放this相关内容//		for (auto e : lt)//lt3的数据插入lt1//			push_back(e);//	}//	return *this;//}//赋值现代写法//lt1=lt3list& operator=(list lt){swap(_head, lt._head);//直接交换return *this;}//lt出了作用域 析构函数销毁第一个链表 也就是lt1原来的链表节点private:Node* _head;};
}

• 第一种:先释放this 然后范围for+尾插
• 第二种:直接交换

5°push_back/insert

namespace szh
{//链表相关数据templatestruct __list_node{__list_node* _next;__list_node* _prev;T _data;//构造__list_node(const T& x = T())//全缺省 构造传参 :_data(x),_next(nullptr),_prev(nullptr){}};//链表类templateclass list{typedef __list_node Node;public://尾插void push_back(const T& x){//只有一个头部再尾插 头部也是尾部//有多个节点//两者逻辑相同//结构设计的优势 有没有数据插入的逻辑都是一样的Node* tail = _head->_prev;//找尾部Node* newnode = new Node(x);//变成newnode tail head三者的连接tail->_next = newnode;newnode->_prev = tail;newnode->_next = _head;_head->_prev = newnode;//四个指针的连接//tail的next newnode的prev newnode的next head的prev//insert(end(), x);}void insert(iterator pos, const T& x){Node* cur = pos._node;Node* prev = cur->_prev;Node* newnode = new Node(x);//prev newnode cur连接prev->_next = newnode;newnode->_prev = prev;newnode->_next = cur;cur->_prev = newnode;}private:Node* _head;};
}

• 注意四个节点的连接

6°pop_back/erase

namespace szh
{//链表相关数据templatestruct __list_node{__list_node* _next;__list_node* _prev;T _data;//构造__list_node(const T& x = T())//全缺省 构造传参 :_data(x),_next(nullptr),_prev(nullptr){}};//链表类templateclass list{typedef __list_node Node;public:void pop_back(){//erase(iterator(_head->_prev));erase(--end());}void erase(iterator pos){assert(pos != end());Node* cur = pos._node;//.对象Node* prev = cur->_prev;Node* next = cur->_next;delete cur;//delete[] cur;prev->_next = next;next->_prev = prev;}private:Node* _head;};
}

• pos位置前后的连接

7°push_front/pop_front

namespace szh
{//链表相关数据templatestruct __list_node{__list_node* _next;__list_node* _prev;T _data;//构造__list_node(const T& x = T())//全缺省 构造传参 :_data(x),_next(nullptr),_prev(nullptr){}};//链表类templateclass list{typedef __list_node Node;public:void push_front(const T& x){insert(begin(), x);}void pop_front(){erase(begin());}private:Node* _head;};
}

• 复用insert和erase

8°迭代器

namespace szh
{//链表相关数据templatestruct __list_node{__list_node* _next;__list_node* _prev;T _data;//构造__list_node(const T& x = T())//全缺省 构造传参 :_data(x),_next(nullptr),_prev(nullptr){}};//模拟迭代器//__list_iterator -> iterator//__list_iterator -> const_iteratortemplatestruct __list_iterator{//list类型typedef __list_node Node;typedef __list_iterator Self;//增加模板参数 //__list_iterator -> const_iterator//定义一个节点Node* _node;//初始化__list_iterator(Node* node):_node(node)//初始化节点{}//*itRef operator*()//T&->Ref{return _node->_data;}Ptr operator->()//T*->Ptr{return &_node->_data;}//++it 返回类型应该是迭代器Self operator++(){_node = _node->_next;//++其实是往下走一个节点return *this;//返回++之后的值}//it++ 返回++之前的值Self operator++(int){Self tmp(*this);//_node = _node->_prev;++(*this);return tmp;}Self operator--(){			_node = _node->_prev;return *this;}Self operator--(int){Self tmp(*this);//_node = _node->_prev;--(*this);return tmp;}//it!=end()bool operator!=(const Self it){return _node != it._node;}};templateclass list{typedef __list_node Node;public:typedef __list_iterator iterator;//const_iterator是如何实现的typedef __list_iterator 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);}private:Node* _head;};
}

• T T& T* ->T Ref Ptr 三个模板参数 对应传参

9°测试

namespace szh
{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;}struct Date{int _year = 0;int _month = 1;int _day = 1;};void test_list2(){模拟指针的行为//int* p1 = new int;//*p1;//Date* p2 = new Date;//*p2;//p2->_year;//这样访问list lt;lt.push_back(Date());lt.push_back(Date());list::iterator it = lt.begin();while (it != lt.end()){//cout << *it << " ";//*it 节点里面的数据 Date 不支持输出cout << it->_year << "-" << it->_month << "-" << it->_day << endl;//需要重载operator-> 本质是it->->_year 但是为了可读性 编译器特殊处理了一下cout << (*it)._year << "-" << (*it)._month << "-" << (*it)._day << endl;//拿到对象后再访问year month day 这种方式不需要重载operator->++it;}cout << endl;}void print_list(const list& lt){list::const_iterator it = lt.begin();//const调非const begin的this需要constwhile (it != lt.end()){//*it = 1;//可改 应该用const迭代器 所以begin和end应该有两个版本cout << *it << " ";++it;}cout << endl;}void test_list3(){list lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);print_list(lt);}void test_list4(){list lt1;lt1.push_back(1);lt1.push_back(2);lt1.push_back(3);lt1.push_back(4);list lt2(lt1);//深浅拷贝问题 print_list(lt2);//lt2先析构 lt1再次析构 程序崩溃 所以要自己实现拷贝构造list lt3;lt3.push_back(10);lt3.push_back(20);lt3.push_back(30);lt3.push_back(40);lt1 = lt3;print_list(lt1);}
}

#include "list.h"int main()
{//szh::test_list1();//szh::test_list2();//szh::test_list3();//szh::test_list4();return 0;
}

【C++】9.list 完