c++ STL容器总结之:vertor与list的应用

STL提供六大组件，彼此可以组合套用

1、容器（containers）：各种数据结构，如vertor，list，deque，set，map.从实现的角度来看，STL容器是一种class template

2、算法（algorithms）：各种算法如sort，search，copy，earse。STL算法是一种 function template。

3、迭代器（iterators）：扮演容器与算法之间的胶合剂，是所谓的“泛型指针”。所有STL容器都有自己的专属的迭代器。

4、仿函数（functors）：行为类似函数，可以作为算法的某些策略。从实现的角度来看，仿函数是一种重载了operator()的class或class template。

5、配接器（adapters）：一种用来修饰容器或仿函数或迭代器借口的东西。例如queue和stack

6、配置器（allocators）：负责空间的配置与管理。配置器是一个实现了动态空间分配、空间管理、空间释放的class template。

STL是建立在泛化之上的。数组泛化为容器，参数化了所包含的对象的类型。函数泛化为算法，参数化了所用的迭代器的类型。指针泛化为迭代器，参数化了所指向的对象的类型。

vector、string、deque和list被称为标准序列容器，

set、multiset、map和multimap是标准关联容器。

非标准序列容器slist和rope。slist是一个单向链表，rope本质上是一个重型字符串。

非标准关联容器hash_set、hash_multiset、hash_map和hash_multimap。

标准非STL容器，包括数组、bitset、valarray、stack、queue和priority_queue。

迭代器被分成五个种类：

输入迭代器是每个迭代位置只能被读一次的只读迭代器。

输出迭代器是每个迭代位置只能被写一次的只写迭代器。

输入和输出迭代器被塑造为读和写输入和输出流（例如，文件）。

前向迭代器有输入和输出迭代器的能力，但是它们可以反复读或写一个位置。

双向迭代器就像前向迭代器，除了它们的后退可以像前进一样容易。标准关联容器都提供双向迭代器。list也有。

连续内存容器（也叫做基于数组的容器）在一个或多个（动态分配）的内存块中保存它们的元素。如果一个新元素被查入或者已存元素被删除，其他在同一个内存块的元素就必须向上或者向下移动来为新元素提供空间或者填充原来被删除的元素所占的空间。这种移动影响了效率和异常安全。标准的连续内存容器是vector、string和deque。非标准的rope也是连续内存容器。

基于节点的容器在每个内存块（动态分配）中只保存一个元素。容器元素的插入或删除只影响指向节点的指针，而不是节点自己的内容。所以当有东西插入或删除时，元素值不需要移动。表现为链表的容器——比如list和slist——是基于节点的，所有的标准关联容器也是（它们的典型实现是平衡树）。非标准的散列容器使用不同的基于节点的实现。

1、vector

vector和数组类似，它拥有一段连续的内存空间，并且起始地址不变，因此它能非常好的支持随机存取（即使用[]操作符访问其中的元素），但由于它的内存空间是连续的，所以在中间进行插入和删除会造成内存块的拷贝（复杂度是O(n)），另外，当该数组后的内存空间不够时，需要重新申请一块足够大的内存并进行内存的拷贝。这些都大大影响了vector的效率。

vector不是一种数据类型，而只是一个类模板，可用来定义任意多种数据类型。vector类型的每一种都指定了其保存元素的类型。因此，vector<int>和vector <string>都是数据类型。

vector对象的定义和初始化

vector<int> ivec4(10, -1);     // 10 elements, each initialized to -1

vector<string> svec(10, "hi!"); // 10 strings, each initialized to "hi!"

vector的操作

向vector添加元素:

vector迭代器

每种容器都定义了一对命名为begin和end的函数，用于返回迭代器。如果容器中有元素的话，由begin返回的迭代器指向第一个元素：

前面的程序用vector::iterator改变vector中的元素值。每种容器类型还定义了一种名为const_iterator的类型，该类型只能访问容器内元素，但不能改变其值。

2、list

list是由数据结构中的双向链表实现的，因此它的内存空间可以是不连续的。因此只能通过指针来进行数据的访问，这个特点使得它的随机存取变的非常没有效率，需要遍历中间的元素，搜索复杂度O(n)，因此它没有提供[]操作符的重载。但由于链表的特点，它可以以很好的效率支持任意地方的删除和插入。

list::iterator与vector::iterator的一些不同：

vector拥有一段连续的内存空间，因此支持随机存取，如果需要高效的随即存取，而不在乎插入和删除的效率，使用vector。

list拥有一段不连续的内存空间，因此支持随机存取，如果需要大量的插入和删除，而不关心随即存取，则应使用list。当大部分插入和删除发生在序列的头或尾时可以选择deque这种数据结构。