effective STL-1 仔细选择你的容器

标准STL序列容器：vector, string, deque, list; 标准STL关联容器：set, multiset, map, multimap; 非标准序列容器: slist(单向链表)， rope(重型字符串)； 非标准关联容器hash_set, hash_multiset, hash_map, hash_multimap； vector<char>可以作为string的替代品； vector作为标准关联容器的替代品； 几种标准非STL容器：数组、bitset、valarray、stakc、queue、priority_queue； vectors是一种可以默认使用的序列类型； 频繁的对序列中部进行插入、删除时应该用list； 大部分插入和删除发生在序列的头或尾时可用选择deque；

vector、string和deque是标准的连续内存容器（在一个或多个（动态分配）的内存块中保存它们的元素），当新元素插入或删除原有元素时，其他同一个内存块的元素必须向上、下移动来为新元素提供空间或填充被删除元素所占的空间。 list是基于节点的容器，容器元素的插入和删除只影响节点的指针，而不是节点之间的内容，所以插入、删除时元素值不需要移动。（使用平衡术实现） 选择分类： 1）需要在容器的任意位置插入一个新元素？ 是的——序列容器； 2）关心元素在容器中的位置？否——散列容器；否则——避免使用散列容器； 3）必须使用C++中的容器吗？ 是——取出散列容器、slist和rope； 4）必须是随机访问迭代器？ 是——vector、deque、string； 双向迭代器？ 是——不能用slist和散列容器的一些实现； 5）但插入或者是删除数据时，是否非常在意容器内现有元素的移动？ 是——放弃连续内存存储容器； 6）容器中的数据的内存布局需要兼容C吗？ 是——vector； 7）查找速度重要吗？ 是——散列容器、排序的vector和标准的关联容器（性能排序优） 8）介意容器的底层使用引用计数吗？ 是——避开string（很多string的实现是用引用计数的），不能用rope；考虑用vector<char>; 9）需要插入和删除的事务性语义吗？需要有可靠地回退插入和删除的能力吗？ 是——使用基于节点的容器； 需要多元素插入（比如以范围的方式）——选择list（唯一提供多元素插入事务性语义的标准容器）； 10）需要把迭代器、指针和引用的失效次数减到最少吗？是——使用基于节点的容器；因为这些容器上进行插入、删除不会使迭代器、指针或引用失效（除非它们指向删除的元素）；在连续内存容器上插入、删除会使所有指向容器的迭代器、指针和引用失效； 11）可以使用随机访问迭代器&&只要没有删除而且插入只发生在容器结尾，指针和引用的数据不会失效——是，deque是梦想的容器。（当插入deque结尾时，deque的迭代器也可能会失效）