一、顺序容器vector

1.1 容器是什么

       在C++中，容器被定义为：在数据存储上，有一种对象类型，它可以持有其他对象或指向其他对象的指针，这种对象类型就叫做容器。简单理解，即容器就是保存其他对象的对象。而且，这种“对象”还有处理“其他对象”的方法。

       容器是随着面向对象语言的诞生而提出的，它甚至被认为是早期面向对象语言的基础。现在几乎所有面向对象语言中都伴随着一个容器，C++中则是标准模版库（STL）。

       C++采用基于模版的方式处理容器，STL中的容器提供了多种数据结构。

1.2 容器的优点

       1）容器类是一种对特定代码重用问题的良好的解决方案。

       2）可以自行扩展。当不知道需要存储多少对象时，就不知道应当开辟多大内存空间，而容器不需要预先设定空间长度，只需要创建一个对象并合理调用其提供的方法，其余的细节则由它自身完成，它自己申请内存或释放内存，并使用最优算法执行所有命令。

       3）容器类自动申请和释放内存，因此无需进行new和delete操作。

1.3 通用容器的分类

       STL将通用容器分为了三类：顺序性容器、关联式容器、容器适配器。

1.3.1 顺序性容器vector、list、deque

       顺序容器的各元素组成有顺序关系的线性表，它是一种线性结构的可序群集。其每个元素有各自固定的位置，使用添加或插入元素后位置顺移，位置与元素本身无关，而与操作时间和地点有关，它保存的是元素操作时的逻辑顺序。例如一次性追加多个元素，这些元素在容器中的相对位置与追加时的逻辑顺序是一致的，即与添加到容器的顺序一致。

vector：向量

       1）可以直接访问任何元素。

       2）线性顺序结构。可以指定一块连续的空间，也可以不预先指定大小，空间可自动扩展，也可以像数组一样被操作，即支持[ ]操作符和vector.at()，因此可看做动态数组，通常体现在追加数据push_back()和删除末尾数据pop_back()。

       3）当分配空间不够时，vector会申请一块更大的内存块（以2的倍数增长），然后将原来的数据拷贝到新内存块中并将原内存块中的对象销毁，最后释放原来的内存空间。因此如果vector保存的数据量很大时会很消耗性能，因此在预先知道它大小时性能最优。

       4）节省空间。因为它是连续存储，在存储数据的区域是没有浪费的，但实际上大多数时候是存不满的，因此实际上未存储的区域是浪费的。

       5）在内部进行插入和删除的操作效率低。由于vector内部按顺序表结构设计，因此这样的操作基本上是被禁止的，它被设计成只能在后端进行追加和删除操作。

//初始化
vector<int> vec //默认初始化，空
vector<int> vec2(vec); //使用vec初始化vec2
vector<int> vec3(3); //初始化3个值为0的元素
vector<int> vec4(4, 1); //初始化4个值为1的元素
vector<string> vec5(5,"null"); //初始化5个值为null的元素
vector<string> vec6(6,"hello"); //初始化6个值为hello的元素

//常用的操作方法
vec.push_back(3) //向末尾添加元素3
vec.end(); //返回指向末尾下一位置的迭代器
int size = vec.size() //一共的元素个数
bool isEmpty = vec.empty(); //判断是否为空
cout<<vec[0]<<endl; //取得第一个元素
vec.insert(vec.end(),5,3); //从末尾下一位置插入5个值为3的元素
vec.pop_back(); //删除末尾元素
vec.erase(vec.begin(),vec.end());//删除之间的元素，其他元素前移
cout<<(vec==vec2)?true:false; //判断是否相等==、！=、>=、<=...
vector<int>::iterator iter = vec.begin(); //获取迭代器首地址
vector<int>::const_iterator c_iter = vec.begin(); //获取const类型迭代器
vec.clear(); //清空元素

//遍历方法
//下标法(vector的特有访问方法，一般容器只能通过迭代器访问)
int length = vec1.size();
for(int i=0;i<length;i++)
{
   cout<<vec1[i];
}
cout<<endl<<endl;
//迭代器法
vector<int>::const_iterator iterator = vec1.begin();
for(; iterator != vec1.end(); iterator++)
{
   cout<<*iterator；
}

//赋值与swap
vector<string> vs1(3); // vs1有3个元素
vector<string> vs2(5); // vs2有5个元素
vs1.swap(vs2); //执行后,vs1中5个元素，而vs2则存3个元素

 

list：双链表

 

       1）线性链表结构。

       2）其数据由若干个节点构成，每个节点包括一个信息块（即实际存储的数据）、一个前驱指针和一个后驱指针。无需分配指定的内存大小且可任意伸缩，因此它存储在非连续的内存空间中，并且由指针将有序的元素链接起来。因而相比vector它也占更多的内存。

       3）根据其结构可知随机检索的性能很差，vector是直接找到元素的地址，而它需要从头开始按顺序依次查找，因此检索靠后的元素时非常耗时。即不支持[ ]操作符和.at()。

       4）由于list每个节点保存着它在链表中的位置，插入或删除一个元素仅对最多三个元素有所影响，因此它可以迅速在任何节点进行插入和删除操作。

//初始化
list<int> lst1; //创建空list
list<int> lst2(3); //创建含有三个元素的list
list<int> lst3(3,2); //创建含有三个元素的值为2的list
list<int> lst4(lst2); //使用lst2初始化lst4

//常用的操作方法
lst1.assign(lst2.begin(),lst2.end()); //分配值
lst1.push_back(10); //添加值
lst1.pop_back(); //删除末尾值
lst1.begin(); //返回首值的迭代器
lst1.end(); //返回末尾位置下一位的迭代器
lst1.clear();//清空值
bool isEmpty1 = lst1.empty(); //判断为空
lst1.erase(lst1.begin(),lst1.end()); //删除元素
lst1.front(); //返回第一个元素的引用
lst1.back(); //返回最后一个元素的引用
lst1.insert(lst1.begin(),3,2); //从指定位置插入3个值为2的元素
lst1.rbegin(); //返回第一个元素的前向指针
lst1.remove(2); //相同的元素全部删除
lst1.reverse(); //反转
lst1.size(); //含有元素个数
lst1.sort(); //排序
lst1.unique(); //删除相邻重复元素

//遍历方法
//迭代器法
for(list<int>::const_iterator iter = lst1.begin();iter != lst1.end();iter++)
{
   cout<<*iter;
}
cout<<endl;

//赋值与swap
list<string> sl1,sl2;
for(int i=0;i<10;i++)sl2.push_back("a");
sl1.assign(10, "A"); //s1被重新赋值，拥有十个元素，都为A

 

deque：双端队列

 

       1）是一种优化了的、对序列两端进行添加和删除操作、较快速地随机访问的基本序列容器。

       2）采用多个连续的存储块保存对象，并在一个映射结构中保存对这些块及其顺序的跟踪。由于不需要重新分配空间，因此追加元素时比vector更有效。实际上内部有一个map指针。

       3）支持随机访问，即支持[ ]操作符和.at()，但性能不如vector。

       4）可以进行内部随机插入和删除，但性能不如list。

1.3.2 关联容器set、multiset、map、multimap

       关联容器是二叉树结构，它根据元素特点排序，迭代器能以元素的特点“顺序地”获取元素。它是以键值的方式来保存数据，即把关键字和值关联起来保存，而顺序容器只能保存一种（可以认为它只保存关键字，也可以认为它只保存值）。具体来说，它采用的是一种比较高效的特殊的平衡检索的二叉树——红黑树结构（不了解）。

集合set：

       1）快速查找，不允许重复值。

       2）按一定顺序排列，集合中的每个元素被称作集合中的实例。

       3）内部通过链表的方式组织，因此插入的时候比vector快，但在查找和末尾追加比vector慢。

map：

       1）提供一种“键-值”关系的一对一的数据存储能力。键按一定顺序排列且不可重复（set也可以看成没有键只有值的特殊map形式）。

       2）链表方式存储，继承了链表的优缺点。

       3）一对多映射，基于关键字快速查找。

multiset和multimap：不要求元素唯一，其他同上。

关联容器特点：

       1）红黑树的结构原理。

       2）set和map保证了元素的唯一性，mulset和mulmap扩展了这一属性，可以允许元素不唯一。

       3）元素是有序的集合，默认在插入的时候按升序排列。

       4）插入和删除操作比vector快，比list慢。因为vector是顺序存储，而关联容器是链式存储；而同为链式结构，list是线性，而关联容器是排序的二叉树结构，因此每次都需要对元素重新排序，涉及到的元素变动更多。

       5）对元素的检索操作比vector慢，比list快很多。vector是顺序的连续存储，这是最快的速度；而list需要逐个搜索，搜索时间与容器大小成正比，关联容器查找的复杂度log(n)，因此容器越大，关联容器相对list越能体现其优越性。

       6）在使用上set区别于顺序容器的是查询上虽然慢于vector，但却强于list。

       7）在使用上map的功能是不可取代的，它保存了“键-值”关系的数据，而这种键值关系采用了类数组的方式。数组是用数字类型的下标来索引元素的位置，而map是用字符型关键字来索引元素的位置。在使用上map也提供了一种类数组操作的方式，即它可以通过下标来检索数据。在STL中只有vector和map可以通过类数组的方式操作元素。

1.3.3 容器适配器stack、queue、priority_queue

       这是一个比较抽象的概念，C++的解释是：适配器是使一事物的行为类似于另一事物的行为的一种机制。容器适配器是让一种已经存在的容器类型采用另一种不同的抽象类型的工作方式来实现的一种机制。其实仅仅是发生了接口转换。可以将之理解为容器的容器，只是不依赖于具体的标准容器类型，可以理解为容器的模板，也可以将之理解为容器的接口。因此，适配器本身不能保存元素，而是“它保存一个容器，容器再保存元素”，所以它是通过调用另一种容器去实现保存功能。

       STL中提供的三种适配器可以由一种顺序容器去实现，默认下stack和queue基于deque容器实现，priority_queue基于vector容器实现，也可以在创建时可以自己指定具体的实现容器。但由于适配器的特点，并不是任何顺序容器都可以实现这些适配器。

       栈stack：后进先出。关联容器可以是任意一种顺序容器。因为顺序容器都可以提供栈的操作要求：push_back、pop_back、back。

       队列queue：先进后出。关联容器必须提供pop_front操作，因此vector不适用。

       优先级priority_queue：最高优先级元素总是第一个处理。则需要提供随机访问功能，因此list不适用。

 

二、迭代器iterator

迭代器iterator     

       迭代器是为了表示容器中某个元素位置这个概念而产生的，是一种检查容器内元素并遍历元素的数据类型。C++更趋向于使用迭代器而非下标进行操作，因为标准库（STL）为每一种标准容器定义了一种迭代器类型，而只有少数容器支持下标操作访问容器元素。

       因此，每种容器都定义了自己的迭代器类型，以vector为例：

//定义和初始化
vector<int>::iterator iter; //定义一个名为iter的变量

vector<int> ivec;
vector<int>::iterator iter1=ivec.bengin(); //将迭代器iter1初始化为指向ivec容器的第一个元素
vector<int>::iterator iter2=ivec.end(); //将迭代器iter2初始化为指向ivec容器的最后一个元素的下一个位置

//常用操作
*iter //对iter进行解引用，返回迭代器iter指向的元素的引用
iter->men //对iter进行解引用，获取指定元素中名为men的成员。等效于(*iter).men
++iter //给iter加1，使其指向容器的下一个元素
iter++
--iter //给iter减1，使其指向容器的前一个元素
iter--
iter1==iter2 //比较两个迭代器是否相等，当它们指向同一个容器的同一个元素或者都指向同同一个容器的超出末端的下一个位置时，它们相等
iter1!=iter2
//用迭代器来遍历ivec容器，把其每个元素重置为0
for(vector<int>::iterator iter=ivec.begin();iter!=ivec.end();++iter)
    *iter=0;

//只有vector和queue容器提供迭代器算数运算和除!=和==之外的关系运算
iter+n //在迭代器上加（减）整数n，将产生指向容器中钱前面（后面）第n个元素的迭代器。新计算出来的迭代器必须指向容器中的元素或超出容器末端的下一个元素
iter-n
iter1+=iter2 //将iter1加上或减去iter2的运算结果赋给iter1。两个迭代器必须指向容器中的元素或超出容器末端的下一个元素
iter1-=iter2
iter1-iter2 //两个迭代器的减法，得出两个迭代器的距离。两个迭代器必须指向容器中的元素或超出容器末端的下一个元素
>,>=,<,<= //元素靠后的迭代器大于靠前的迭代器。两个迭代器必须指向容器中的元素或超出容器末端的下一个元素
vector<int>::iterator mid=v.begin()+v.size()/2; //初始化mid迭代器，使其指向v中最靠近正中间的元素

迭代器const_iterator

       每种容器还定义了一种名为const_iterator的类型，该类型的迭代器只能进行读操作，不能进行写操作。

for(vector<int>::const_iterator iter=ivec.begin();iter!=ivec.end();++iter)
     cout<<*iter<<endl;   //合法，读取容器中元素值
     *iter=0;             //不合法，不能进行写操作

       并且const iterator与const_iterator是不同的，前者在对迭代器进行声明时必须进行初始化，并且一旦初始化后及不能修改其值。

vector<int> ivec(10);
const vector<int>::iterator iter=ivec.begin();
*iter=0;    //合法，可以改变其指向的元素的值
++iter;    //不合法，无法改变其指向的位置

       由于删除元素或移动元素等操作会修改容器的内在状态，从而使原本指向被移动元素的迭代器失效，也可能同时使其他迭代器失效。而失效的迭代器是没有意义，且使用无效迭代器会导致严重的运行时错误，因此一定要特别留意哪些操作会导致迭代器失效。

 

本文参考资料：

C++容器类 该文为转载，但该博主未提供转载来源。

C++ STL中容器的使用全面总结

C++迭代器的使用和操作

C++11 你真的会用迭代器（iterator）么？

C/C++迭代器使用详解