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;
//支持迭代器也就支持范围for
for (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_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;
}
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();
// 拷贝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);
}
测试结果：
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
{
// 惯例
// 全部都是公有，一般用struct
template<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;
//支持迭代器也就支持范围for
for (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;
}