STL有6种序列容器类型.doc

1.STL有6种序列容器类型（1）vector它提供对元素的随即访问，在尾部添加和删除元素的时间是固定的，在头部或中部插入和删除元素的复杂度为线性时间。（2）deque在文件中声明。是双端队列，支持随即访问。从deque的开始与末尾位置插入和删除元素的时间是固定的。尽管vector和deque都提供对元素的随机访问和在序列中部执行线性时间的插入和删除操作，但vector容器执行这些操作时速度更快一些。（3）list是双向链表，插入删除元素时间固定。不支持随机访问。与vector不同是，当向容器中插入或删除元素后，链表迭代器指向元素将不变。解释一下：如果一个vector有5个元素，中间插入一个，那么第五个元素包含的值将是以前第四个元素的值，因此，迭代器指向的位置不变，但是数据不同。然而，在链表中插入新元素并不会移动已有的元素，而只是修改链接信息。指向某个元素的迭代器仍然指向该元素，也就是值相同，链接的位置不同了。（4）queue在头文件中声明。queue是一个适配器类，底层类默认为deque。它不允许随机访问队列元素，甚至不允许遍历队列。可以将元素添加到队尾，查看队尾和队首的元素的值，检查元素数目和测试队列是否为空。（5）priority_queue与queue的不同是，最大的元素总是在队首，也是一个适配器类，默认的底层类是vector。可以修改用于确定哪个元素放在队首的比较方式，方法是提供一个可选的构造函数参数。（6）stack也是一个适配器类，默认的底层实现为vector。不允许随机访问堆栈元素，甚至不允许遍历堆栈。可以压入到栈顶，从栈顶弹出元素，查看栈顶元素的值，检查元素数目和测试堆栈是否为空。2.STL有4种联合容器：set，multiset,map,multimap；联合容器将值与关键字关联在一起，使用关键字来查找值。关联容器的长处在于，它提供了对元素的快速访问。与序列相似，联合容器也允许插入新元素，不过不能指定元素的插入位置。原因是联合容器通常包含用于确定数据存放位置的算法，以便能够很快检索信息。（1）set，multiset前两种是在set头文件中（以前分别为set.h和multiset.h）；值的类型与关键字相同。set删除相同的元素，multiset不会。（2）map，multimap后两种是在map头文件中（以前分别为map.h和multimap.h）。值的类型与关键字不同。map关键字唯一，multimap关键字不唯一。1.输入迭代器术语“输入”是从程序的角度说的，即来自容器的信息被视为输入，就像是来自键盘的信息对程序来说是输入一样。因此，输入迭代器可被程序用来读取容器中的信息。具体的说，对输入迭代器接触引用将使程序能读读取容器中的值，但不一定能让程序修改值。因此，需要输入迭代器的算法将不会修改容器中的值。输入迭代器必须能够访问容器中所有的值，这是通过支持+操作符来实现的。如果将输入迭代器设置为指向容器的第一个元素，并不断的将其递增，知道到达末尾位置，则它将一次指向容器中的每一个元素。另外，并不能保证输入迭代器第二次遍历容器时，顺序不变。输入迭代器并递增以后，也不能保证其先前的值仍然可以被解除引用。（个人理解这句话：想想键盘输入，缓冲区内的值，读过以后就没有了，即使你保存了已经扫描过的迭代器，仍然不能重新对这个迭代器进行解除引用操作以得到他的值）。基于输入迭代器的任何算法都应当是单通行的，不依赖于前一次遍历时的迭代器值，也不依赖于本次遍历中前面的迭代器值。2.输出迭代器输出是指用于将信息从程序传输给容器的迭代器，因此程序的输出就是容器的输入。解除引用能让程序修改容器的值，但是不能读取。发送到显示器上的输出就是如此，cout可以修改发送到显示器的字符流，却不能读取屏幕上的内容。对于单通行，只读算法，可以使用输入迭代器；对于单通行，只写算法，可以使用输出迭代器。3.正向迭代器正向迭代器只使用+操作符来遍历容器，所以它每次沿容器向前移动一个元素；不过，与输入和输出迭代器不同的是，它总是按相同的循序遍历一些列值。另外，将正向迭代器递增后，仍然可以对前面的迭代器值解除引用，并可以得到相同的值。这些特征使得多次通行算法成为可能。正向迭代器既可以似的能够读取和修改数据，也可以似的只能读取数据。4.双向迭代器它具有正向迭代器的所有特征，同时支持-操作符。5.随机访问迭代器随机访问迭代器具有双向迭代器的所有特性，同时添加了支持随机访问的操作和用于对元素进行排序的关系操作符。（就是可以比较指针的大小）注意：各种迭代器的类型并不是确定的，而只是一种概念性的描述。不能用面向对象的语言来表达迭代器的种类，迭代器的种类只是一系列的要求，而不是一种类型（类）。在STL中，用概念一词来描述这一系列要求。因此，有输入迭代器概念和双向迭代器概念，但是却