[数据结构与算法]容器深究——list详解与sort排序

三种遍历方式：

1. 迭代器遍历

list<int> It;
It.push_back(1);
It.push_back(2);
It.push_back(3);
It.push_back(4);
list<int> iterator it=It.begin();
while(it!=It.end())
{
	cout<<*it<<"";
	++it;
}
cout<<endl;

• 范围for（推荐，因为看起来简洁）

/*在Linux下要加上 g++ test_list1.cpp -std=C++11*/
//纯范围for
list<int> It;
It.push_back(1);
It.push_back(2);
It.push_back(3);
It.push_back(4);
for(auto e: It)
{
	cout<<e<<"";
}
cout<<endl;
//迭代器区间+范围for
int a[]={16,2,3,77};
list<int> it1(a,a+4);
//原生指针可以当天然的迭代器使用，其实vector和string的迭代器也是原生指针
for(auto e: it1)
{
	cout<<e<<"";
}
cout<<endl;

拓展知识
sort排序（包含在算法argorithm头文件中的）：

• 升序

#include<algorithm>
//sort排序是在其中包含的
int a[]={16,2,3,77};
vector<int> v(a,a+4);
sort(v.begin(),v.end());//两个参数为迭代器区间

输出结果将是把数组a按升序排序，说到这里可能就有人会问怎么样用它降序排列呢？

标准库里已经有现成的了，就在functional里，include进来就行了。functional提供了一堆基于模板的比较函数对象。它们是（看名字知意思)：equal_to、not_equal_to、greater、greater_equal、less、less_equal。对于这个问题来说，greater就足够了，直接拿过来用：

• 降序

#include<algorithm>
#include<functional> //greater模板函数包含其中
int a[]={16,2,3,77};
vector<int> v(a,a+4);
sort(v.begin(),v.end()，greater<int>());

注意：这种方式不能对list进行排序，因为sort的底层是快速排序，快速排序要求容器的迭代器必须是随机迭代器（list是双向迭代器）
比如：快速排序要三个数取中优化，不支持随机访问，效率不够

//不支持sort(It.begin(),It.end())这种用法
It.sort();
//支持，但是不建议使用

常见的迭代器分为三类：

单向：只能使用++，如 forword_list
双向：++，–，如 list
随机：++，–，+，-等，如vector、string