C++容器和迭代器实例讲解

一、顺序容器vector

1.1容器是什么

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

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

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

1.2 容器的优点

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

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

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内部按顺序表结构设计，因此这样的操作基本上是被禁止的，它被设计成只能在后端进行追加和删除操作。

list：双链表

1）线性链表结构。

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

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

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

deque：双端队列

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

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

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

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

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

关联容器是二叉树结构，它根据元素特点排序，迭代器能以元素的特点“顺序地”获取元素。它是以键值的方式来保存数据，即把关键字和值关联起来保存，而顺序容器只能保存一种（可以认为它只保存关键字，也可以认为它只保存值）。

set：快速查找，不允许重复值。

multiset：快速查找，允许重复值。

map：一对多映射，基于关键字快速查找，不允许重复值。

multimap：一对多映射，基于关键字快速查找，允许重复值。

1.3.3 容器适配器stack、queue、priority_queue

这是一个比较抽象的概念，c++的解释是：适配器是使一事物的行为类似于另一事物的行为的一种机制。容器适配器是让一种已经存在的容器类型采用另一种不同的抽象类型的工作方式来实现的一种机制。其实仅仅是发生了接口转换。可以将之理解为容器的容器，所以它实质上是一个容器，只是不依赖于具体的标准容器类型，可以理解为容器的模板，也可以将之理解为容器的接口，而适配器具体采用哪种容器类型去实现，在定义适配器的时候可以由程序员自己决定。

stack：后进先出。

queue：先进后出。

priority_queue：最高优先级元素总是第一个处理。

二、迭代器iterator

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

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