引言

C++语言是其实是一个语言的联邦，它既有C语言的强大，又提供了面向对象的方法，方法的灵活实现与复用又是可以通过STL来实现。STL是一个集合，它包含了迭代器、算法、容器等，但最为人所熟知是主要是容器。容器具有着极强的扩展性与适配性，因此学习STL就是对容器的掌握与理解。

容器

STL中提供了多种类型的容器:

标准化STL序列容器: vector、deque、list
标准化STL关联容器: set、multiset、map、multimap
非标准化STL容器: rope(重型string)、slist(single list)
非标准化STL关联容器: hash_set、hash_multiset、hash_map、hash_multimap
这些个容器之中，平常使用较多的容器是: vector、list、set、map。

内存布局

STL中容器的分类不仅仅可以通过序列化与关联化来区分，还可以通过内存地址的布局来区分。在STL中主要可以分为两种布局:

连续内存
基于节点

STL中内存布局为连续内存的有: vector、deque、string。即与数组的内存分布一致。而基于节点的容器，一个内存之中只会存在一个元素，通过指针来连接每个节点，STL之中的容器有: set、multiset、map、multimap、list。

速度衡量

相对而言非序列化的关联容器，即哈希容器。它可以根据哈希表，快速定位数据的地址，时间复杂为O(1)。若是要使用标准的STL库，则就是使用vector容器，其内存地址连续且支持随机迭代器访问，查询效率高。最后，就是关联容器，基于底层的红黑树，它们也有着极为高效的查询效率。

迭代器失效

若是关联式容器则不存在迭代器失效问题，原因是关联式容器是基于节点式的，因为在插入与删除时，它们从不会使用迭代器。而关联式容器则不同，它们是一段连续内存地址，若是删除某个元素，则会导致此元素之后的元素迭代器失效。

容器泛化

不要这样做，原因有如下几点:

若是泛化，则是提供一个所有迭代皆通用的容器，那么这个容器，则只能使用所有容器的通用功能，极大减少了容器的丰富的拓展功能
不同的迭代之间，迭代器的失效情况是不同的(连续内存与基于节点的容器)

使用容器过程之中，若是出现了需要更改容器的需要。那么将容器封装进类中，则是极为明智的。对容器功能封装，对外提供相应的接口暴露。

empty() vs size()

代码之中常常会写出这样的代码:

1 2	if (obj.size() == 0) {...} if (obj.empty()) {}

一般而言，这没有什么区别，它们似乎可以被划上等号。但是STL中List容器却是这个等号之中的意外情况。list之中提供了函数splice(),它可以将一个list链接到另一个list上。若是使用splice()函数之后，list之中元素个数size()就需要重新计算。因此list在设计时，使size()作为了让步，最终结果是splice()操作为O(1),而size()则是O(n)。
成员函数empty()，它的操作时间复杂度总是O(1),因此empty()的使用具有更大的时间效率保证。

区间元素

若是将vector A赋值给vector B，你大概会有如下两种操作:

循环对每个元素进行赋值
使用STL提供了copy函数

对方法一进行分析，它这样做会有哪些操作产生:

每个元素都进行赋值，使用拷贝构造函数，产生临时空间
需要循环n次，时间复杂度O(n)
显然个元素的循环赋值，成本极高。

方法二分析:

调用copy函数
没有使用for循环，但是copy的时间复杂度就是O(n)

综合以上两种方法的分析，显然这两个方法并不是多么的优秀。而STL之中提供了一个函数，则正好为其服务: assign()，可以将另一个vector某区间上的元素一次性复制到指定的list上。

区间成员对于单个元素的处理函数，优点也是十分明显的:

使用区间成员处理函数，少写循环代码
使用区间成员函数，代码用意更加清晰

STL的对于插入删除等操作的方法如下所示:

/**区间创建**/
container::container(InputIterator begin, InputIterator end);

/**区间插入**/
void container::insert(iterator postion, InputIterator begin, InputIterator end);

/**区间删除**/
// 序列化容器
iterator container::erase(iterator begin, iterator end);
// 关联式容器
void container::erase(iterator begin, iterator end);

/**区间赋值**/
void container::assign(InputIterator begin, InputIterator end);

容器资源安全

若是容器包含了一个由new创建的指针，那么它需要在结束时，使用delete去释放掉。若是程序出现异常则会导致，资源的泄漏。因此若是想要避免此情况的发生，我们需要使用智能指针去管理容器中的所有对象，从而保证了安全性。

结语

STL容器有着许多的应用与变化，若是正确使用与规范化，我们就需要遵守STL的游戏规则。

Rabbet

Effective_STL 阅读笔记(一)

引言

容器