list
大体上与之前学的string,vector类似，list不支持[]访问，擅长头插，头删，尾插，尾删，中间元素插入删除，因为list底层是双向循环带头链表
一段代码演示：
#include <iostream>
#include <list>
using namespace std;int main()
{//尾插list<int> lt1;lt1.push_back(1);lt1.push_back(1);lt1.push_back(1);lt1.push_back(1);list<int> lt2 = { 1,2,3,4,5 };//迭代器list<int>::iterator it1 = lt1.begin();//迭代器进行访问while (it1 != lt1.end()){cout << *it1 << " ";++it1;}cout << endl;//支持迭代器也就支持范围forfor (auto e : lt2){cout << e << " ";}cout << endl;
}
代码结果如下：
这里list的迭代器会有所不同
用原生指针解决不了
push_back和emplace_back
先来看一段代码：
class Pos
{int _row;int _col;public:Pos(int row, int col):_row(row),_col(col){cout << "Pos(int row, int col)" << endl;}//拷贝构造Pos(const Pos& p):_row(p._row), _col(p._col){cout << "Pos(const Pos&p)" << endl;}
};int main()
{//构造+拷贝构造//push_backlist<Pos> lt;//有名对象Pos p1(1, 1);lt.push_back(p1);//匿名对象lt.push_back(Pos(2, 2));//隐式类型转换lt.push_back({ 3,3 });//emplace_back，可以看作模板lt.emplace_back(p1);lt.emplace_back(Pos(2, 2));//lt.emplace_back({3,3});不可以，因为形参类型未知//可以传递多个参数，相当于直接构造了Pos//直接构造lt.emplace_back(3, 3);return 0;
}
splice
一个应用的地方在于可以提高修改元素内容的效率：
int main()
{list<int> lt1 = { 1,2,3,4,5 };//LRU//这里可以理解为转移链表里面的元素int x;while (cin >> x){auto pos = find(lt1.begin(), lt1.end(), x);if (pos != lt1.end()){//这里的含义是把lt1里的pos转移到开头位置lt1.splice(lt1.begin(), lt1, pos);}}return 0;
}
sort–排序
示例代码如下：
int main()
{list<int> lt1 = { 1,20,3,-4,5 };for (auto e : lt1){cout << e << " ";}cout << endl;//默认是升序lt1.sort();for (auto e : lt1){cout << e << " ";}cout << endl;//如果需要降序，要用到仿函数greater//有名对象的写法//greater<int> gt;//lt1.sort(gt);//匿名对象的写法,更推荐lt1.sort(greater<int>());//vector的方式也可以写vector<int> v1 = { 1,20,3,-4,5 };for (auto e : v1){cout << e << " ";}cout << endl;//这里同样也是默认升序sort(v1.begin(), v1.end());for (auto e : v1){cout << e << " ";}cout << endl;//降序也要用到仿函数sort(v1.begin(), v1.end(), greater<int>());for (auto e : v1){cout << e << " ";}cout << endl;
}
运行结果如下：
迭代器的分类
不能随便乱用迭代器，因为底层是不一样的，可以理解为随机单向迭代器包含于双向迭代器，双向迭代器包含于随机迭代器
上面的排序,sort的底层是特殊处理过的，vector的底层是快排
效率对比测试：
测试的代码：
void test_op1()
{srand(time(0));const int N = 1000000;list<int> lt1;list<int> lt2;vector<int> v;for (int i = 0; i < N; ++i){auto e = rand() + i;lt1.push_back(e);v.push_back(e);}int begin1 = clock();// 排序sort(v.begin(), v.end());int end1 = clock();int begin2 = clock();lt1.sort();int end2 = clock();printf("vector sort:%d\n", end1 - begin1);printf("list sort:%d\n", end2 - begin2);
}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();lt1.push_back(e);lt2.push_back(e);}int begin1 = clock();// 拷贝vectorvector<int> v(lt2.begin(), lt2.end());// 排序sort(v.begin(), v.end());// 拷贝回lt2lt2.assign(v.begin(), v.end());int end1 = clock();int begin2 = clock();lt1.sort();int end2 = clock();printf("list copy vector sort copy list sort:%d\n", end1 - begin1);printf("list sort:%d\n", end2 - begin2);
}
测试结果：
list的模拟实现
尾插的操作与前面学习的双向循环链表类似：
迭代器这里需要注意，与前面学习的string和vector不一样：
这里需要注意的是迭代器不可以通过下标的方式进行访问，像我们前面学过的string和vector底层结构是数组，物理结构是连续的，但是list的底层是双向循环链表，物理空间不连续，需要借助类封装节点指针，重载运算符，模拟指针的行为
operator->访问
代码如下：
list.h
T* operator->()//访问里面元素
{return &_node->_data;//取里面地址
}
Test.cpp
soobin::list<Pos> lt2;
Pos p1(1, 1);
lt2.push_back(p1);
lt2.push_back(Pos(2, 2));
lt2.push_back({ 3,3 });soobin::list<Pos>::iterator it2 = lt2.begin();
while (it2 != lt2.end())
{cout << (*it2)._row << ":" << (*it2)._col << endl;//为了可读性，特殊处理，省略了一个->cout << it2->_row << ":" << it2->_col << endl;//显示写法，第一个->是运算符重载，第二个->是结构体元素访问cout << it2.operator->()->_row << ":" << it2.operator->()->_col << endl;++it2;
}
cout << endl;
总体代码如下：
List.h
#include <assert.h>
namespace soobin
{// 惯例// 全部都是公有，一般用structtemplate<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>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--(){_node = _node->_prev;return *this;}Self operator++(int){Self tmp(*this);_node = _node->_next;return tmp;}Self operator--(int){Self tmp(*this);_node = _node->_prev;return tmp;}bool operator!=(const Self& s){return _node != s._node;}};template<class T>class list{typedef list_node<T> Node;public:typedef list_iterator<T> iterator;iterator begin(){return iterator(_head->_next);}iterator end(){return iterator(_head);}void empty_init(){_head = new Node();_head->_next = _head;_head->_prev = _head;}list(){empty_init();}void push_back(const T& x){Node* new_node = new Node(x);Node* tail = _head->_prev;tail->_next = new_node;new_node->_prev = tail;new_node->_next = _head;_head->_prev = new_node;}private:Node* _head;};
}
Test.h
#include <iostream>
#include <list>
#include <vector>
#include <algorithm>
using namespace std;//int main()
//{//尾插//list<int> lt1;//lt1.push_back(1);//lt1.push_back(1);//lt1.push_back(1);//lt1.push_back(1);//list<int> lt2 = { 1,2,3,4,5 };//迭代器//list<int>::iterator it1 = lt1.begin();//迭代器进行访问//while (it1 != lt1.end())//{// cout << *it1 << " ";// ++it1;//}//cout << endl;//支持迭代器也就支持范围for//for (auto e : lt2)//{// cout << e << " ";//}//cout << endl;
//}class Pos
{
public:int _row;int _col;Pos(int row, int col):_row(row),_col(col){cout << "Pos(int row, int col)" << endl;}//拷贝构造Pos(const Pos& p):_row(p._row), _col(p._col){cout << "Pos(const Pos&p)" << endl;}
};//int main()
//{//构造+拷贝构造//push_back
// list<Pos> lt;//有名对象
// Pos p1(1, 1);
// lt.push_back(p1);
// //匿名对象
// lt.push_back(Pos(2, 2));//隐式类型转换
// lt.push_back({ 3,3 });//emplace_back，可以看作模板
// lt.emplace_back(p1);
// lt.emplace_back(Pos(2, 2));//lt.emplace_back({3,3});不可以，因为形参类型未知//可以传递多个参数，相当于直接构造了Pos//直接构造
// lt.emplace_back(3, 3);
// return 0;
//}//int main()
//{//for (auto e : lt1)//{// cout << e << " ";//}//cout << endl;//int x;//cin >> x;//auto it = find(lt1.begin(), lt1.end(), x);//if (it != lt1.end())//{// it.erase(it);//}
// return 0;
//}//int main()//{// list<int> lt1 = { 1,2,3,4,5 };//LRU//这里可以理解为转移链表里面的元素// int x;// while (cin >> x)// {// auto pos = find(lt1.begin(), lt1.end(), x);// if (pos != lt1.end())// {//这里的含义是把lt1里的pos转移到开头位置// lt1.splice(lt1.begin(), lt1, pos);// }// }// return 0;//}//int main()
//{
// list<int> lt1 = { 1,20,3,-4,5 };
// for (auto e : lt1)
// {
// cout << e << " ";
// }
// cout << endl;//默认是升序
// lt1.sort();
// for (auto e : lt1)
// {
// cout << e << " ";
// }
//cout<<endl;
// //如果需要降序，要用到仿函数greater//有名对象的写法//greater<int> gt;//lt1.sort(gt);//匿名对象的写法,更推荐//lt1.sort(greater<int>());//vector的方式也可以写//vector<int> v1 = { 1,20,3,-4,5 };//for (auto e : v1)//{// cout << e << " ";//}//cout << endl;//这里同样也是默认升序//sort(v1.begin(), v1.end());//for (auto e : v1)//{// cout << e << " ";//}//cout << endl;//降序也要用到仿函数//sort(v1.begin(), v1.end(), greater<int>());//for (auto e : v1)//{// cout << e << " ";
// }//cout << endl;
//}
//void test_op1()
//{
// srand(time(0));
// const int N = 1000000;// list<int> lt1;
// list<int> lt2;// vector<int> v;
//
// for (int i = 0; i < N; ++i)
// {
// auto e = rand() + i;
// lt1.push_back(e);
// v.push_back(e);
// }// int begin1 = clock();// 排序
// sort(v.begin(), v.end());
// int end1 = clock();// int begin2 = clock();
// lt1.sort();
// int end2 = clock();// printf("vector sort:%d\n", end1 - begin1);
// printf("list sort:%d\n", end2 - begin2);
//}//void test_op2()
//{
// const int N = 1000000;// list<int> lt1;
// list<int> lt2;// for (int i = 0; i < N; ++i)
// {
// auto e = rand();
// lt1.push_back(e);
// lt2.push_back(e);
// }// int begin1 = clock();// 拷贝vector// vector<int> v(lt2.begin(), lt2.end());// 排序
// sort(v.begin(), v.end());// 拷贝回lt2
// lt2.assign(v.begin(), v.end());// int end1 = clock();// int begin2 = clock();
// lt1.sort();
// int end2 = clock();// printf("list copy vector sort copy list sort:%d\n", end1 - begin1);
// printf("list sort:%d\n", end2 - begin2);
//}#include "List.h"int main()
{soobin::list<int> lt1;lt1.push_back(1);lt1.push_back(1);lt1.push_back(1);lt1.push_back(1);//不直接在it1上进行改动是因为会造成没有指针指向哨兵位等问题//迭代器soobin::list<int>::iterator it1 = lt1.begin();//迭代器进行访问while (it1 != lt1.end()){//也可以写*it1 = 2;cout << *it1 << " ";++it1;}cout << endl;//支持迭代器也就支持范围forfor (auto e : lt1){cout << e << " ";}cout << endl;soobin::list<Pos> lt2;Pos p1(1, 1);lt2.push_back(p1);lt2.push_back(Pos(2, 2));lt2.push_back({ 3,3 });soobin::list<Pos>::iterator it2 = lt2.begin();while (it2 != lt2.end()){cout << (*it2)._row << ":" << (*it2)._col << endl;//为了可读性，特殊处理，省略了一个->cout << it2->_row << ":" << it2->_col << endl;//显示写法，第一个->是运算符重载，第二个->是结构体元素访问cout << it2.operator->()->_row << ":" << it2.operator->()->_col << endl;++it2;}cout << endl;return 0;
}