开题
思来想去，感觉数组和线性表好像没什么好写的，—— 但是呢，为了体现《数据结构》一书的完整性，还是抽出了一篇。
刚好自己的C++容器很久没有复习过了，这篇文章和下一篇就来讨论一下STL3类容器吧！^-^
那这一节，我们就从“数组和线性表”出发，一起来看看STL中的顺序容器和关联容器！
然后，线性表的相关代码已经托管到Github上了~我是代码，快点我
3大容器类型
顺序容器：vector/deque/list 关联容器：set/multiset/map/multimap 容器适配器：stack/queue/priority_queue
迭代器
本文在遍历容器时，使用了迭代器的概念；那，就先说明一下迭代器的概念：
迭代器是一种类，它能够用来遍历标准模板库容器中的部分或全部元素。
如果说模版是把类型和算法分开，那么迭代器就是把模版和算法分开！ 迭代器能够为不同的模版提供标准的算法，比如algorithm.h中的算法！ 本文就用到了sort(it1,it2),reverse(it1,it2);
vector
vector常用于后插与删除，提供数据高效地随机访问，可以用于定义二维数组！ vector实际存储结构类似数组（所有数据存储在一起），但是会动态扩容，默认采用大小翻倍的策略进行扩容！
来看看vector的常用API：
void TestVector(int length)
{
vector<int> v1(1,2);
vector<vector<int> > vv;
vector<int> v;
for(int i=0;i<length;i++)
{
cout<<"size: "<<v.size()<<endl;//已有元素数量
v.push_back(50-i);
cout<<"capacity: "<<v.capacity()<<endl;//最大可容纳元素的数量，采用翻倍的策略进行扩容
}
sort(v.begin(),v.end());//排序
reverse(v.begin(),v.end());//倒置
v[length-1]=12;
for(vector<int>::iterator it=v.begin();it<v.end();it++)
{
cout<<*it<<endl;
}
cout<<"location: "<<find(v.begin(),v.end(),10)-v.begin()<<endl;//寻找元素
}
list
list 支持高效的随机插入/删除操作，但随机访问效率低下! list 实际存储时使用 双链表结构，不连续存储，使得插入删除操作较为搞笑：
来看看list的常用API
void TestList(int length)
{
list<int> l1(2,20);
// list<list<int> > ll;//不支持二维数组
list<int> l;
for(int i=0;i<length;i++)
{
cout<<"size: "<<l.size()<<endl;//已有元素数量
l.push_front(50-i);
// l.push_back(50-i);//支持前插和后插
}
// sort(l.begin(),l.end());//自带排序算法，不提供标准排序算法
l.sort();
reverse(l.begin(),l.end());//倒置
l.merge(l1,greater<int>());//合并两个链表并使之默认升序
for(list<int>::iterator it=l.begin();it!=l.end();it++)
{
cout<<*it<<endl;
}
cout<<"location: "<<(*find(l.begin(),l.end(),49))<<endl;//寻找元素
}
deque
deque 是list和vector的结合版，在vector基础上提供2端插入的功能。 存储结构是二级数组的“分段连续存储”（索引+数组），会维护额外数组保存每段的端地址，方便前端插入！
来看看常用API
void TestDeque(int length)
{
deque<int> d1(2,20);
// deque<deque<int> > ll;//不支持二维数组
deque<int> d;
for(int i=0;i<length;i++)
{
cout<<"size: "<<d.size()<<endl;//已有元素数量
d.push_front(50-i);
// d.push_back(50-i);//支持前插和后插
}
sort(d.begin(),d.end());//提供标准排序算法
reverse(d.begin(),d.end());//倒置
// d.sort();
// d.merge(d1,greater<int>());//合并两个链表并使之默认升序
for(deque<int>::iterator it=d.begin();it!=d.end();it++)
{
cout<<*it<<endl;
}
cout<<"location: "<<(find(d.begin(),d.end(),49)-d.begin())<<endl;//寻找元素
}
set&multiset
set是集合，不允许出现重复元素！ multiset在set基础上允许出现重复，插入删除一个数都能够在O(logn)的时间内完成，并保证序列中的数是有序的。 这一特性在很多算法中都可以用到！这个时间复杂度很容易想到二叉排序树！不知道内部是怎么实现的！
来看看API
void TestSet()
{
set<int> s;
s.insert(1);
s.insert(2);
s.insert(0);
for(set<int>::iterator it=s.begin();it!=s.end();it++)
{
cout<<*it<<endl;
}
s.insert(1);
cout<<"size: "<<s.size()<<endl;
s.erase(1);
if((it = s.find(2)) != s.end())
{
cout<<*it<<endl;
}
multiset<int> s2;
s2.insert(1);
s2.insert(1);
cout<<s2.size()<<endl;
for(multiset<int>::iterator it2=s2.begin();it2!=s2.end();it2++)
{
cout<<*it2<<endl;
}
// cout<<s.find(2)-s.begin()<<endl;
}
### map&multimap
map 用于保存键值对，不允许出现重复元素； multimap 在map的基础上扩充，允许出现重复元素
来看看常用API
void TestMap()
{
//VC6.0 对map的支持不是很好，所以下面的代码注释掉了，但是已经在g++上调试通过
/*
map<string,int> m;
m.insert(pair<string,int>("111",1));
m.insert(map<string,int>::value_type("222",2));
for(map<string,int>::iterator it=m.begin();it!=m.end();it++)
{
cout<<it->first<<" "<<it->second<<endl;
}
m["333"]=3;
int a=m["444"];
cout<<"a:"<<a<<endl;
multimap<string,int> mm;
//mm不支持mm["111"]=4;
mm.insert(pair<string,int>("111",1));
mm.insert(pair<string,int>("111",2));
mm.insert(pair<string,int>("111",3));
for(map<string,int>::iterator it=mm.begin();it!=mm.end();it++)
{
cout<<"mm"<<it->first<<" "<<it->second<<endl;
}
*/
}
Map执行结果：
其他
其他用于定义数组和线性表的方法，其中array是c11标准才定义的！
const int length2=5;
void TestOther(int length)
{
int *a1 = new int[length2];
int a2[]={1,2,3,4,5};
int a3[length2];//C++可以使用const常量定义数组
// array<int,5> arr= new arrar[length];
for(int i=0;i<length;i++)
{
cout<<a2[i]<<endl;
}
}
总结
顺序容器与关联容器的内容，基本就在这了，有些不常用的API没有写， 本节只是写了一些常用数组与线性表的使用方法，并没有深挖其实现原理！ 还存在很多一知半解的地方，各位看官可以补充呀！
参考：C++容器类详解