@(boolan C++)[STL]
2017-11-20 12:10:37 / herohlc
使用一个东西不明白它的道理不高明。
item1. 认识headers/版本
1. 泛型编程
泛型编程 - GP/Generic Programming，使用template 为主要工具来编写程序。
STL是GP的一个成功的实践。
2. C++标准库学习
标准库学习层级：
- level 0: 使用标准库
- level 1: 认识标准库
- level 2: 良好使用标准库
- level 3:扩展标准库
3. C++标准库 vs. STL
C++ 标准库/C++ Standard Library
标准模版库/STL/Standard Template Library
STL是标准库的子集，标准库包含STL之外的其他部件。
4. 标准库头文件
- 标准库的header files 不带”.h”， 例如 ：
#include <vector> - 新式的C header files 不带”.h”， 例如：
#include <cstdio> - 旧式的C header files 仍然可用，例如：
#include <stdio.h> - 新式的header files内的组件封装在 namespace std下
- 旧式的header files内的组件未封装在 namespace std下
头文件用新不用旧。
5. 有用的网站
cppreference.com
cplusplus.com - The C++ Resources Network
https://gcc.gnu.org/
item2. STL体系结构基础介绍
1. STL六大部件
注意上图各组件之间的关系。
- STL中的GP区别OOP，数据结构在容器中实现，处理容器的部分功能在算法中实现（容器的基本操作仍然在容器中实现，有的容器有实现自己的find等算法）。
- 迭代器是泛化的指针。
2. Example: 一些部件
count_if
http://www.cplusplus.com/reference/algorithm/count_if/?kw=count_if
header
#include <algorithm>
not1
header
#include <functional>
bind2nd
header
#include <functional>
less
header
#include <functional>
3. 前闭后开区间 [)
- 引用container.end() 很危险。
item3. 容器分类与测试/array
1. 容器 - 结构与分类
容器分类： sequence containers / associative containers
sequence containers
- vector
- deque
- list
- array (C++11)
- forward_list(C++11)
associative containers
- map/ multimap / unordered_map(C++11) / unordered_multimap(C++11)
- set /multiset /unordered_set(C++11) / unordered_multiset(C++11)
containers 比较
- array 存储固定数量的元素。
- forward_list只保存一个指针所以比list更节省内存。
- sequence 与associative的差别在于，sequence 存放数据时是有序的存储(逻辑上有序，非内存存储上有序)
- set/map实现的数据结构为红黑树-高度平衡二叉树。
一种被广泛采用的hash-table实现：separate chaining
2. std::array
array存储结构
array info
clock/qsort/bsearch
clock - C++ Reference
http://www.cplusplus.com/reference/cstdlib/qsort/?kw=qsort
http://www.cplusplus.com/reference/cstdlib/bsearch/?kw=bsearch
item4. 容器分类与测试/vector
1. vector存储结构
- vector向后增长所以只有push_back操作
- vector的扩容方式：两倍增长，renew 2倍新内存，拷贝旧数据到新内存
item5. 容器分类与测试/list/forward_list
1. std::list
list存储结构
如果容器提供了自己的sort/find，请采用容器提供的sort/find。
2. std::forward_list
forward_list存储结构
- forward_list 仅能提供对front元素的操作
3. gnu::slist
4. std::deque
deque存储结构
5. std::stack/queue
- stack/queue是deque的适配器(container adapter)，容器适配器
- stack/queue仅提供push/pop方法
- 限于stack/queue的数据处理方式，stack/queue不提供迭代器操作，算法当然也不支持。
stack/queue存储结构
item6. 容器分类与测试/ map/set/multimap/multiset/unordered_map/unordered_set/unordered_multimap/unordered_multiset
1. std::multiset
multiset存储结构
2. std::multimap
multimap存储结构
3. std::unordered_multiset
hash-table存储结构
hash table 中bucket一定要比元素个数多。如果元素个数>=bucket个数则扩充bucket个数。
4. std::unordered_multimap
5. std::unordered_set
6. std::unordered_map
7. std::set
8. std::map
item 7. 分配器/allocator
分配器负责容器内存管理。的容器大多数情况下使用默认的分配器。
container 的allocator 参数
template <typename _TP, typename _Alloc = std::allocator<_TP>>
class vector : protected _Vector_base<_TP,_Alloc>
template <typename _TP, typename _Alloc = std::allocator<_TP>>
class list : protected _List_base<_TP,_Alloc>
template <typename _TP, typename _Alloc = std::allocator<_TP>>
class deque : protected _Deque_base<_TP,_Alloc>
1. __gnu::_cxx:: allocator
头文件与用法
#include <ext/array_allocator.h>
#include <ext/mt_allocator.h>
#include <ext/debug_allocator.h>
#include <ext/pool_allocator.h>
#include <ext/bitmap_allocator.h>
#include <ext/malloc_allocator.h>
#include <ext/new_allocator.h>
list<string, __gnu_cxx::array_allocator<string>> c1;
list<string, __gnu_cxx::mt_allocator<string>> c1;
list<string, __gnu_cxx::debug_allocator<string>> c1;
list<string, __gnu_cxx::pool_allocator<string>> c1;
list<string, __gnu_cxx::bitmap_allocator<string>> c1;
list<string, __gnu_cxx::malloc_allocator<string>> c1;
list<string, __gnu_cxx::new_allocator<string>> c1;
不建议直接使用allocator分配内存。
