Boolan C++ STL与泛型编程_1

c++标准库--体系结构与内核分析

主要内容：

本节主要对c++标准库学习的4个阶段，c++标准库和新旧式C的头文件，以及stl进行讲解。stl是泛型编程最成功的作品。stl属于c++标准库的一部分，它具有容器、算法、适配器、分配器、迭代器、泛函数等六大部件。

使用一个东西，却不明白它的道理，不高明。--林语堂

1. c++标准库概述

1.1 c++标准库学习4个阶段

• 使用-->认识（心中自有丘壑）-->良好使用-->扩充
• 重要的网站：
  www.cplusplus.com
  en.cppreference.com
  gcc.gnu.org
• 推荐的书：c++标准库，stl源码剖析（用旧的版本guc 2.91 source code写的，更好理解。新版的gcc要复杂的多。）

1.2 头文件

• c++标准库的头文件不带.h。新式的C的头文件也没有.h，旧式C带有.h，仍然可以使用。新式头文件内的组件都封装在namespace std中。所以在使用c++标准库中的内容时，最好前面写上using namespace std; 就不用在每个前面加std::了。或是不想包含全部std，eg. 可以写using std::cout; 这样这个文件中再次使用cout时前面不用加std::了。旧式头文件的组件没有封装在std。
• 不同的编译器下使用c++标准库绝大部分是相同的。

2. STL

• stl 6大部件
  容器：存放数据。
  算法：排序，查找... 利用迭代器处理容器的数据
  分配器：支持容器分配内存。
  迭代器：一种泛化的指针。
  适配器：可以转换容器、泛函数、迭代器
  泛函数
• 用到哪个容器，就要引用哪个头文件。
• 使用范例：

     bind2nd(less<int>(), 40)绑定第二参数为40.
     not1 >=40.

• 在使用容器和算法时要根据使用场景，考虑复杂度。
• 两种遍历容器的方法：普通for，基于范围的for+auto.

3. 容器分类

分为三类：顺序容器，关联容器(key和value关联)，无序容器（c++II）。

• 顺序容器：array（不能扩展，其中元素数量从定义起就固定了），vector，deque，list，forward_list（c++II）带有单向指针，list是带有双向指针，所以list占用内存多。
• 关联容器(key和value关联)：set/multiset，map/multimap 用的是红黑树，一种高度平衡二叉树，自动调节，这样查找时的效率会更高，能够避免向一个分支深入查找下去。
• 无序容器（c++II）：unordered set/multiset，unordered map/multimap.利用的是hash table separate chaining 链表的长度最好不是很长，否则影响查找效率。

qsort()和bsearch()（二分查找，这个查找前必须先排序）它们的头文件是<cstdlib>。
::find(): 是函数模板，是c++提供的算法，头文件<algorithm>。
直接查找可能比先::sort()，再bsearch()速度快，因为排序可能耗时长。

（1）array，array.size(), array.front(), array.back(), array.data() (返回array首元素的地址。)
（2）vector, capacity() 容量每次扩展是上次的二倍, size()，data()，front(), back(), push_back()时，内存不够会抛出异常 std::bad_alloc， 抛出异常时要abort()退出程序？。
（3）list, max_size()? ，list.sort() list自己提供了sort()，用容器自己提供sort比用::sort()要好，效率更高。
（4）forward_list，本身也有sort(), 没有size()和back().
（5）slist 单向链表，是非标准库中的，gnc中的。<ext\slist>
（6）deque 双向队列，分段连续（由一个个段组成，每段是连续的内存空间。用一个map存放每个段的指针。以段（512字节？）为单位分配连续内存空间）
max_size()， 排序只能用::sort().
（7）stack和queue是容器适配器，是利用deque实现的。stack先进后出。queue先进先出。push(), pop().
（8）set/multiset，insert(), size(), max_size(). 容器自己的find()比用全局的find()快。
（9）map/multimap，insert(),find()，map可以用[]赋值，multimap不能使用[].
（10）unordered_multiset，insert(),size(),max_size(),bucket_count()(篮子一定比元素要多，因为有些篮子可能是空的)，bucket_size(i)（第i个篮子中元素的数量）当元素数量和篮子数量一致时，会分配原有的篮子数量的二倍的空间，之后重新分配元素的放置位置。load_factor()载重因子，max_load_factor(). max_bucket_count()。有自己的find()，也比全局的find快。
（11）unordered_multimap，insert().
（12）hash开头的4个（hash_set, hash_map,hash_multiset,hash_multimap），是unordered的旧版本。

4. 分配器

不建议使用，因为allocate分配了多少元素的内存，在释放的时候也要指定元素个数删除。