STL第一讲

一、认识headers、版本、重要资源

1. C++ Standard Library和Standard Template Library

前者：c++标准库；后者直译为“标准模板库”

区别:

• C++标准库：是c++编译器提供的自带的头文件(不带.h后缀)
• 新版兼容C的头文件的形式cxxxx；旧版的xxxx.h也可用但不建议
• 新版c++标准库的头文件都存在于命名空间std
• STL：《源码剖析》所说的六大部件

查看自己的g++编译器：

wkm@ai303-virtual-machine:~/code/shell$ gcc -v -x c++ -E -
....
#include "..." search starts here:
#include <...> search starts here:
 /usr/include/c++/9
 /usr/include/x86_64-linux-gnu/c++/9
 /usr/include/c++/9/backward
 /usr/lib/gcc/x86_64-linux-gnu/9/include
 /usr/local/include
 /usr/include/x86_64-linux-gnu
 /usr/include
End of search list.
....

2. 一些重要网站

1. cplusplus
2. cppreference
3. gcc.gnu.org

二、STL介绍

六大部件：

前闭后开区间：
每个容器表示范围的成员：

• begin：指向首元素
• end：指向末尾元素的下一位

三、容器

容器分类与各种测试(一)

图解：

1. 无须容器属于关联容器，所以推荐将container依然分为两大类：顺序容器、关联容器
2. 顺序容器中的箭头：表示可扩充的地方；如vector只能在尾部扩充；
3. 关联容器底层实现：红黑树；无序容器：hashtable
4. 原图中的红标是c++11标准引入的

容器分类与各种测试（二）

测试代码风格：namespace、变量定义定格
在数据量很大的时候，先sort后查找，sort步骤就很耗时。

容器分类与各种测试（三）

stl全局有sort（用法是::sort，即添加作用域运算符），容器也可能有自己的sort。建议使用某种容器时，调用自身的sort。

gnu中有非c++标准库的容器：slist，头文件：ext\slist，其他的成员使用方法与forward_list相同

• deque：
  • “分段连续”，由一段段的buffer组成，每个buffer能存储若干个元素；
  • push_front和push_back用完一个buffer后，会再向前/后扩充一个buffer（一个buffer具体大小取决于stl具体实现）
  • deque没有自己的sort；

stack和queue是容器适配器；不提供iterator，否则会破坏其“先进后出”/“先进先出”的基本原则。

容器分类与各种测试（四）

对于无序容器：当元素个数大于bucket_count()，会扩充bucket；

旧代码中关于hash_set/hash_map/hash_multiset/hash_multimap，需要找到对应的头文件位置

分配器

每个容器的都有默认分配器：std::allocator

建议：尽量使用容器，因为自己直接使用分配器，手动分配和释放内存会加大工作量。