前言
我们前面已经对string和vector进行了学习使用，以及对他们的底层进行了模拟实现！本期我们继续学习STL的另外一个容器---list。
本期内容介绍
什么是list？
list的常用接口
什么是list?
还是来看看官方的文档说明！
这里通过官方文档我们可以知道！list是一个带头双向循环的链表！在插入和删除时，时间复杂度是常量级别的！
list常用接口
在正式的开始介绍接口使用前，我们还是来了解一下类型重命名！
这里主要用到的就是上面的三个! value_type 就是T， reference 是value_type&, size_type 就是size_t
构造、拷贝构造、赋值拷贝、析构
list<int> lt1;//空构造
list<int> lt2(10, 6);//n 个 val构造
vector<int> v = { 1, 2,4,56,7,8,-1 };
list<int> lt3(v.begin(), v.end());//迭代器区间构造
list<int> lt4(lt2);//拷贝构造这里除了介绍这些常见的外！这里在穿插一个C++11引入的一个非常好用的，初始化序列初始化！
这个在上期vector的模拟实现已经介绍了，auto ret = {1,2,3};此时的ret就是initializer_list<int>。
list<int> lt5 = { 1,2,3,4,5 };//C++11的初始化序列初始化
list<int> lt4(lt2);//拷贝构造
list<int> lt5 = { 1,2,3,4,5 };//C++11的初始化序列初始化
lt5 = lt4;//赋值拷贝
析构还是一样的：清理资源、释放空间~！
迭代器
正向
list<int> lt = { 1,2,3,4,5 };//C++11的初始化序列初始化
const list<int> clt = { 10, 20,30, 40 };
list<int>::iterator it = lt.begin();//正向
while (it != lt.end())
{
cout << *it << " ";
++it;
}
cout << endl;
list<int>::const_iterator cit = clt.begin();//const正向
while (cit != clt.end())
{
cout << *cit << " ";
++cit;
}
cout << endl;
支持迭代器必然支持范围for,范围for就是傻傻的替换迭代器！
反向
list<int>::reverse_iterator it = lt.rbegin();//反向
while (it != lt.rend())
{
cout << *it << " ";
++it;
}
cout << endl;
list<int>::const_reverse_iterator cit = clt.rbegin();//const反向
while (cit != clt.rend())
{
cout << *cit << " ";
++cit;
}
cout << endl;
const和非const的区别主要还是权限的问题~！如果不修改建议使用const的！！！
注意：这里的迭代器需要指定类域的原因是模板的原因，模板参数不一样就是一个类，为了让迭代器用法统且不冲突，需要指定是哪个类的迭代器~！
容量
empty
list<int> lt = { 1,2,3,4,5,6,7,8,9 };
bool ret = lt.empty();
cout << ret << endl;
size
list<int> lt = { 1,2,3,4,5,6,7,8,9 };
size_t sz = lt.size();
cout << sz << endl;
元素访问
这里文档上说的很清楚：如果是空链表的话，你去取头和尾的数据是未定义的行为！！因为当链表为空时，头尾就是哨兵位的头结点，我们只是规定头结点的next指向实际链表的第一个节点，_prev指向对后一个元素，并未规定头结点的数据域存的是啥，所以如果为空链表，你去取就是未定义行为！
这和begin迭代器不一样，迭代器是返回链表的元素，这里是返回引用！
list<int> lt = { 1,2,3,4,5,6,7,8,9 };
int front = lt.front();
int back = lt.back();
cout << front << " " << back << endl;
const list<int> clt = { 10, 20,30, 40 };
int cfront = clt.front();
int cback = clt.back();
cout << cfront << " " << cback << endl;
修改
删除的这三个是涉及右值引用！在后面的C++11那一期会专门介绍~！
assign
list<int> lt = { 1,2,3,4,5,6,7,8,9,10 };
list<int> lt2;
list<int> lt3 = { 0, 2,4,6,8 };
lt.assign(5, 1);
for (auto& e : lt)
{
cout << e << " ";
}
cout << endl;
lt2.assign(++lt3.begin(), --lt3.end());
for (auto& e : lt2)
{
cout << e << " ";
}
cout << endl;
这个和构造函数那里很像，但是不一样！这个是已经存的你再去把他的原来内容用指定的内容替换掉！
push_front
list<int> lt = { 1,2,3,4 };
lt.push_front(0);
for (auto& e : lt)
{
cout << e << " ";
}
cout << endl;
pop_front
list<int> lt = { 1,2,3,4 };
lt.pop_front();
for (auto& e : lt)
{
cout << e << " ";
}
cout << endl;
push_back
list<int> lt = { 1,2,3,4 };
lt.push_back(-5);
for (auto& e : lt)
{
cout << e << " ";
}
cout << endl;
pop_back
list<int> lt = { 1,2,3,4 };
lt.pop_back();
for (auto& e : lt)
{
cout << e << " ";
}
cout << endl;
insert
list<int> lt = { 1,2,3,4 };
lt.insert(lt.begin(), 0);//在pos位置插入一个val
lt.insert(++lt.begin(), 5, -1);//在pos位置插入n个val
vector<int> v = { 90, 98, 23,34,56 };
lt.insert(lt.begin(), v.begin(), v.end());//在pos位置插入一个迭代器区间
erase
list<int> lt = { 1,2,3,4 };
lt.erase(lt.begin());//删除pos位置的元素
lt.erase(++lt.begin(), lt.end());//删除一段迭代器区间
resize
由于是链表，所以不用考虑扩容的问题！这里的resize就要变成了尾插和尾插了！
list<int> lt = { 1,2,3,4 };
lt.resize(3);//相当于尾删，只保留前n个元素
lt.resize(10, 0);//相当于尾插到节点数目为10，不够的就是0
swap
还是和前面的两个容器的一样，他这里的是对list对象的属性进行交换！
list<int> lt1 = { 1,2,3,4 };
list<int> lt2 = { 10,20,30,40 };
lt1.swap(lt2);
clear
list<int> lt = { 1,2,3,4 };
lt.clear();
cout << lt.size() << endl;
其他操作
splice
splice是粘结，结合的意思！这个接口的作用是转移链表的元素！重载了三个：
将一个链表的数据转移到另一个链表的pos位置
将一个链表的i位置的元素转移到另一个链表的pos位置
将一个链表的一个迭代器区间转移到另一个链表的pos位置
list<int> lt1 = { 1,2,3,4,5,6,7,8,9 };
list<int> lt2 = { 0, -1,-2 };
lt1.splice(lt1.begin(), lt2);//在pos位置，将x转移过来
lt2.splice(lt2.end(), lt1, ++lt1.begin());//在pos位置将x的i位置的一个元素转移过来
lt2.splice(++lt2.begin(), lt1, ++lt1.begin(), --lt1.end());//在pos位置将x的一段迭代器区间给转移过来
remove
这个函数的作用是：删除所有特定的值！
list<int> lt = { 2,3,2,2,2,4,5,6,1,2 };
lt.remove(2);
print(lt);
remove_if
这个函数的作用是删除符合条件的元素，这里的形参可以是一个对象，也可以是一个函数指针！
bool is_odd(const int& val)
{
return val % 2 == 0;
}
struct single_digit
{
bool operator() (const int& val)
{
return val < 10;
}
};
void test_list7()
{
list<int> lt = { 2,3,2,2,2,4,5,6,1,2,21,11,23 };
lt.remove_if(is_odd);
print(lt);
lt.remove_if(single_digit());
print(lt);
}
unique
一看名字就知道这是去重的，但是这个去重是去重连续相邻的重复元素！
list<int> lt = { 2,3,2,2,2,2,4,5,6,1,2,21,11,23 };
lt.unique();
print(lt);
merge
这接口的作用就是：合并两个链表！但注意：这两个链表必须是有序的！！！！
list<int> lt1 = { 1,3,7,8,9 };
list<int> lt2 = { 2,4,5,7,9 };
lt1.merge(lt2);
print(lt1);
print(lt2);//此时lt2是空的
sort
这个接口的作用是：对链表进行排序！它的底层是归并排序！
list<int> lt = { 1,3,2,1,-1,7,8,9 };
lt.sort();
print(lt);
但是这个效率就很，，，不太好~！不是归并不行，是链表排序不太行！
OK，举个例子：
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);
}这个代码是将同样的数据插入到一个vector和一个list，分别对他们排序，看他们排序花费的时间！
差了两倍多！！！再来看一个：
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);
}这个代码是：先将两个链表插入相同的数据，在将一个放到vector中排序，然后再拷回来，一个是直接调用链表的sort！
直接差了4倍！所以，list的这个sort效率真不咋地，建议少用~！
reverse
这个函数的作用就是反转链表！
list<int> lt = { 1,2,3,4,5,6,7,8 };
lt.reverse();
print(lt);
非成员函数swap
有这个接口的原因和前面的几个容器一样！防止调到标准库里面的那个！
list<int> lt1 = { 1,2,3};
list<int> lt2 = { 10,20,30, 50};
swap(lt1, lt2);
print(lt1);
print(lt2);
OK，本期内容就分享到这里，我们下期再见~！
结束语：不要因为别人的三言两语就打破你的深思熟虑！
