effective STL

基于接口和实现分离的原则。了解stl的接口和stl的实现。

STL中有迭代器(iterator)、算法(algorithm)和函数对象(function object)。但是对于大多数C++程序员来说，最值得注意的还是容器。容器比数组功能更强大、更灵活。它们可以动态增长(和缩减)，可以自己管理内存，可以记住自己包含了多少对象。它们限定了自己所支持的操作的复杂性。

序列容器：vector、string、deque、list、forward_list(C++11)、array(C++11)。

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

哈希容器：hash_set、hash_multiset、hash_map、hash_multimap、 unordered_set(C++11)、unordered_multiset(C++11)、unordered_map(C++11)、unordered_multimap(C++11)。

标准的非STL容器，包括：bitset(include )、valarray(include )。其它STL容器：stack(include )、queue(include )和priority_queue((include ))。

vector可以作为string的替代。vector作为标准关联容器的替代。有时vector在运行时间和空间上都要优于标准关联容器。

vector是默认应使用的序列类型，当需要频繁地在序列中间做插入和删除操作时，应使用list；当大部分插入和删除操作发生在序列的头部和尾部时， deque是应考虑的数据结构。
STL容器的一种分类方法：连续内存容器(contiguous memory container)和基于节点的容器(node-based container)。

 连续内存容器：vector、string、deque

基于节点的容器：list、关联容器、哈希容器

选择容器时最重要的一些问题：

(1). 你是否需要在容器的任意位置插入新元素？如果需要，就选择序列容器；关联容器是不行的。

(2). 你是否关心容器中的元素是如何排序的？如果不关心，则哈希容器是一个可行的选择方案；否则，你要避免哈希容器。

(3). 你选择的容器必须是标准C++的一部分吗？如果必须是，就排除了slist和rope。

(4). 你需要哪种类型的迭代器？如果它们必须是随机访问迭代器，则对容器的选择就被限定为vector、deque和string。或许你也可以考虑rope。如果要求使用双向迭代器，那么你必须避免slist以及哈希容器的一个常见实现。

(5). 当发生元素的插入或删除操作时，避免移动容器中原来的元素是否很重要？如果是，就要避免连续内存的容器。

(6). 容器中数据的布局是否需要和C兼容？如果需要兼容，就只能选择vector。

(7). 元素的查找速度是否是关键的考虑因素？如果是，就要考虑哈希容器、排序的vector和标准关联容器----或许这就是优先顺序。

(8). 如果容器内部使用了引用计数技术(reference counting)，你是否介意？如果是，就要避免使用string，因为许多string的实现都使用了引用计数。rope也需要避免，因为权威的rope实现是基于引用计数的。当然，你需要某种表示字符串的方法，这时你可以考虑vector。

(9). 对插入和删除操作，你需要事务语义(transactional semantics)吗？也就是说，在插入和删除操作失败时，你需要回滚的能力吗？如果需要，你就要使用基于节点的容器。如果对多个元素的插入操作(即针对一个区间的形式)需要事务语义，则你需要选择list，因为在标准容器中，只有list对多个元素的插入操作提供了事务语义。对那些希望编写异常安全(exception-safe)代码的程序员，事务语义显得尤为重要。(使用连续内存的容器也可以获得事务语义，但是要付出性能上的代价，而且代码也显得不那么直截了当。)

(10). 你需要使迭代器、指针和引用变为无效的次数最少吗？如果是这样，就要使用基于节点的容器，因为对这类容器的插入和删除操作从来不会使迭代器、指针和引用变得无效(除非它们指向了一个你正在删除的元素)。而针对连续内存容器的插入和删除操作一般会使指向该容器的迭代器、指针和引用变得无效。

(11). 如果序列容器的迭代器是随机访问类型，而且只要没有删除操作发生，且插入操作只发生在容器的末尾，则指向数据的指针和引用就不会变为无效，这样的容器是否对你有帮助？这是非常特殊的情形，但如果你面对的情形正是如此，则deque是你所希望的容器。(当插入操作仅在容器末尾发生时，deque的迭代器有可能会变为无效。deque是唯一的、迭代器可能会变为无效而指针和引用不会变为无效的STL标准容器。)

STL是以泛化(generalization)原则为基础的：数组被泛化为”以其包含的对象的类型为参数”的容器，函数被泛化为”以其使用的迭代器的类型为参数”的算法，指针被泛化为”以其指向的对象的类型为参数”的迭代器。

容器类型被泛化为序列和关联容器，类似的容器被赋予相似的功能。标准的连续内存容器提供了随机访问迭代器，而标准的基于节点的容器提供了双向迭代器。序列容器支持push_front和/或push _back操作，而关联容器则不然。关联容器提供了对数时间的lower_bound、upper_bound和equal_range成员函数，但序列容器却没有提供。

当(通过如insert或push_back之类的操作)向容器中加入对象时，存入容器的是你所指定的对象的拷贝。当(通过如front或back之类的操作)从容器中取出一个对象时，你所得到的是容器中所保存的对象的拷贝。进去的是拷贝，出来的也是拷贝(copy in, copy out)。

在存在继承关系的情况下，拷贝动作会导致剥离(slicing)。也就是说，如果你创建了一个存放基类对象的容器，却向其中插入派生类的对象，那么在派生类对象(通过基类的拷贝构造函数)被拷贝进容器时，它所特有的部分(即派生类中的信息)将会丢失。”剥离”问题意味着向基类对象的容器中插入派生类对象几乎总是错误的。使拷贝动作高效、正确，并防止剥离问题发生的一个简单办法是使容器包含指针而不是对象。

class Widget {};
class SpecialWidget : public Widget {};
 
int test_item_3()
{
	std::vector vw;
	SpecialWidget sw;
	vw.push_back(sw); // sw作为基类对象被拷贝进vw中，它的派生类特有部分在拷贝时被丢掉了
 
	return 0;
}

empty对所有的标准容器都是常数时间操作，而对一些list实现，size耗费线性时间。