STL学习笔记
前言
STL是GP编程的典范，使用容器涉及六大模块：
- 容器
- 分配器
- 算法
- 迭代器
- 适配器
- 仿函数
分配器为容器分配内存，迭代器用来访问容器数据，算法通过迭代器操作容器内的数据，算法使用仿函数改变算法过程。适配器是各部分的粘合剂。
这其中，除了算法是模板函数外，其他都是模板类。
容器
list实现
Sequence Container
有头节点的 双向 循环 链表。
deque实现
Sequence Container
deque是分段连续的。有很多个小段连续空间（buffer），外部一个数组用来存放buffer指针。通过iterator模拟连续。 外部buffer指针数组会类似vector扩容。这意味着可以不改变元素扩容，不像vector那样真正的连续。
容器适配器：stack queue
stack和queue默认的Seqence是deque，stack和queue可以默认是deque的适配器。 二者还可以选用list作为底层容器。
array和vector实现
Sequence Container
vector动态连续数组，空间不足时会两倍扩充。
array，底层数组直接封装。
_Rb_tree 容器
Associative Container
如名，红黑树，节点是双向链表形式的树。模板参数提供至少前四个，分别是Key，Value（Key和Data的结合体），GetKey（仿函数，如何从Value里拿到Key），Compare（仿函数，如何比较Key）
#include <bits/stl_tree.h>
int main() {
struct MyS {
int a;
int b;
};
struct GetKey {
int operator()(const MyS &s) const {
return s.a;
}
};
//key, key and data = value, how to get key from value, compare, allocator(default)
std::_Rb_tree<int, MyS, GetKey, std::less<int>> rbTree;
rbTree._M_insert_unique(MyS{1, 2});
rbTree._M_insert_unique(MyS{3, 4});
rbTree._M_insert_equal(MyS{1, 6});
}
容器适配器：map set multimap multiset
- map
- set
- multimap
- multiset
#include <map>
#include <set>
int main() {
//key type, data type, compare function, allocator
std::map<int, int> m;
//key type, data type, compare function, allocator
std::multimap<int, int> mm;
//key type, compare function, allocator
std::set<int> s;
//key type, compare function, allocator
std::multiset<int> ms;
}
_HashTable 容器
Associative Container
哈希表，内部是vector，每个vector元素称作bucket，每个vector元素是一个节点的指针，这个节点是一个链表的首个节点，这个链表用来解决hash冲突。
vector的size为质数，每次扩容扩容到容量最接近2倍的质数，扩容后重新分配所有bucket。
注意哦，直接使用hash table的话，要写全模板参数，尤其是它没有默认构造函数，要手动指定至少bucket大小、hash函数、key比较函数这三个参数。
#include <iostream>
#include <hashtable.h>
#include <cstring>
int main() {
struct StrCmp {
bool operator()(const char *a, const char *b) const {
return strcmp(a, b) == 0;
}
};
__gnu_cxx::hashtable<
const char *, //value(data+key),
const char *, //key
std::hash<const char *>, //hash function,
std::_Identity<const char *>, //how to get key
StrCmp, //key equal function
std::allocator<const char *>> //allocator
myHashTable(100, std::hash<const char *>(), StrCmp());
myHashTable.insert_equal("hello");
myHashTable.insert_equal("world");
auto it = myHashTable.find("hello");
std::cout << *it; //输出hello
}
GNU C++的内置的hash函数
std::hash就是传入一个类型返回一个size_t的函数。
STL的size_t hash(Ty t);使用模板偏特化对不同类型做不同处理：
-
对于整数类型（有符号和无符号整数如int char enum），使用static_cast做类型强转为size_t。
-
对于浮点数类型（float double），是使用
std::_Hash_bytes(const void* __ptr, size_t __len, size_t __seed);。 -
对于指针类型*T，则是使用reinterpret_cast重新解释为size_t。
-
对于字符串对象类型（std::string），也是使用
std::_Hash_bytes(const void* __ptr, size_t __len, size_t __seed);。
实际放到bucket数组时要对存放bucket的vector大小取模的。
以下代码是指针类型偏特化 和 数值类型偏特化。
/// Partial specializations for pointer types.
template<typename _Tp>
struct hash<_Tp*> : public __hash_base<size_t, _Tp*>
{
size_t
operator()(_Tp* __p) const noexcept
//指针类型，重新解释为size_t
{ return reinterpret_cast<size_t>(__p); }
};
// Explicit specializations for integer types.
#define _Cxx_hashtable_define_trivial_hash(_Tp) \
template<> \
struct hash<_Tp> : public __hash_base<size_t, _Tp> \
{ \
size_t \
operator()(_Tp __val) const noexcept \
// 数值类型直接转化
{ return static_cast<size_t>(__val); } \
};
/// Explicit specialization for bool.
_Cxx_hashtable_define_trivial_hash(bool)
适配器：unordered_ 容器
unordered容器内部实现是
- 一个存放单链表首个地址的动态数组
- 一个单链表存放实际数据
注意他们是两个数据结构，而不是一个数组，然后数组各自存放自己的单链表，推测是为了添加第0个元素时提高效率并且为了迭代时直接跳过空bucket。
数组有很多bucket（实际上就是存放链表首个指针的数组元素），每个bucket存放链表用于解决冲突。bucket数量是固定的且大于元素个数，每次当元素数量等于bucket数量时，会重新分配下一个数量的bucket（一般是最接近之前数量二倍的质数），同时会rehash之前的所有元素到新的bucket数组。
- unordered_map
- unordered_set
- unordered_multimap
- unordered_multiset
#include <unordered_map>
#include <unordered_set>
int main() {
//key type, data type, hash function, compare function, allocator
std::unordered_map<int, int> m;
//key type, data type, hash function, compare function, allocator
std::unordered_multimap<int,int> mm;
//key type, hash function, compare function, allocator
std::unordered_set<int> s;
//key type, compare function, compare function, allocator
std::unordered_multiset<int> ms;
}
迭代器
迭代器类型
迭代器是用来访问容器的。容器对外提供迭代器。
访问容器是有规则的：是否能随机访问？是否能双向访问？那么迭代器应该有自己的属性，以便让外部调用时注意到。
这个规则在迭代器里是怎样的表现形式？首先想到使用enum指定标签，实际上STL使用struct xx_tag{}，使用一个类作为一个属性。
具体有这5种属性
iterator_category 是什么类型的,比如说双向遍历类型
value_type 容器内装的值是什么类型的,比如说int
difference_type 容器内距离的类型,比如说long int
pointer 指针类型是什么,比如说int*
reference 引用类型是什么,比如说int&
不同的属性组合成迭代器不同的类型。
迭代器类型萃取器 iterator_traits
什么是类型萃取
在编译期就知道一个变量/类的类型，比如重载就可以看作类型萃取的一个应用。
为什么需要类型萃取
在编译期知道类型，就可以根据类型做出一些事情咯，比如类型萃取知道这个变量是指针还是引用，然后定义typedef isPointer OK，之后程序运行期就可以直接知道isPointer()==OK()，就设置不改变这个变量的内容。
为什么需要迭代器类型萃取
算法需要通过iterator操作容器内数据，一个算法需要得知iterator的属性（需要知道这些属性来做最佳的算法处理），具体来说，是需要上一节提到的五种属性。
怎么实现呢？
具体而言，如何知道根据模板传入的类型参数做出判断。
一个错误的想法：使用运行期程序判断
c++11提供了decltype()做类型推断，可以用decltype(_Ty)==decltype(int*)做判断然后具体赋值吗？显然不可能，c++不提供类型间的操作。不能比较int==int，必须要实例化比如int()==int()，而==的前提是左右对象类型相同，不相同的情况下会编译报错。
这里要和golang的类型推断语法比较一下，golang的类型推断 switch val.type，然后就可以判断类型是否符合了。
还有一种方法，c++为了能够根据传入类型做操作，天然支持了重载，自动根据类型调用不同的函数。难道说要在容器里定义重载函数，然后让外部调用函数获取属性吗？好像也可以，但是一方面这样还需要调用函数，会降低性能。另一方面，不符合泛型编程数据和方法分开的准则。接下来看看STL是怎样实现的。
STL是这样实现的：使用编译期的类型萃取
- 每个容器自己有一个
_xx_iterator模板类，使用typedef，把自己的属性写死，比如下面是stl_list的源码，把自己的iterator_category写死为bidirectional_iterator_tag。
template<typename _Tp>
struct _List_iterator
{
...
typedef ptrdiff_t difference_type; //ptrdiff_t 到最后就是long int
typedef std::bidirectional_iterator_tag iterator_category;
//std::bidirectional_iterator_tag到最后就是 struct input_iterator_tag { };
typedef _Tp value_type;
typedef _Tp* pointer;
typedef _Tp& reference;
...
};
这样外部就可以直接从容器里获取到属性，获得这个属性的对象。
//获取到属性对象
list<int>::iterator::iterator_category listCat;
vector<int>::iterator::iterator_category vectorCat;
至此，完成了属性类型typename到一个属性对象object的转换。
-
还有一个问题，不是所有iterator都是模板，比如指针，引用。这时候也想获得他们的属性，他们没有模板类，怎么办呢。很自然的想到使用适配器模式。若传入的是指针或者引用，则进行一个partial specialization。若是普通类型，则读取他内置的属性。
这个适配器是
std::traits<iterator _It>，看看他是怎样进行偏特化的。传入普通类型
template<typename _Iterator>
struct __iterator_traits<_Iterator,
__void_t<typename _Iterator::iterator_category,
typename _Iterator::value_type,
typename _Iterator::difference_type,
typename _Iterator::pointer,
typename _Iterator::reference>>
{
typedef typename _Iterator::iterator_category iterator_category;
typedef typename _Iterator::value_type value_type;
typedef typename _Iterator::difference_type difference_type;
typedef typename _Iterator::pointer pointer;
typedef typename _Iterator::reference reference;
};
template<typename _Iterator>
struct iterator_traits //从这里实例化，父类接到并读取传入iterator内置的
: public __iterator_traits<_Iterator> { };
传入指针/引用类型
template<typename _Tp>
struct iterator_traits<_Tp*>
{
typedef random_access_iterator_tag iterator_category;
typedef _Tp value_type;
typedef ptrdiff_t difference_type;
typedef _Tp* pointer;
typedef _Tp& reference;
};
/// Partial specialization for const pointer types.
template<typename _Tp>
struct iterator_traits<const _Tp*>
{
typedef random_access_iterator_tag iterator_category;
typedef _Tp value_type;
typedef ptrdiff_t difference_type;
typedef const _Tp* pointer;
typedef const _Tp& reference;
};
外部怎样通过适配器获得属性的对象呢?
//使用适配器
iterator_traits<list<int>::iterator>::iterator_category listItAdapter;
iterator_traits<int*>::iterator_category intItAdapter;
//不使用适配器
list<int>::iterator::iterator_category listIt; //和前者都是std::bidirectional_iterator_tag对象
算法
算法是什么
通过迭代器对容器内的数据信息进行操作。
迭代器类型对算法的影响
之前提到迭代器类型，其中有个属性是iterator_category，前面提到它其实是一个类。它有这些类型，继承关系如下：
其中input_iterator_tag和output_iterator_tag是最Base的。
//@{
/// Marking input iterators.
struct input_iterator_tag { };
/// Marking output iterators.
struct output_iterator_tag { };
/// Forward iterators support a superset of input iterator operations.
struct forward_iterator_tag : public input_iterator_tag { };
/// Bidirectional iterators support a superset of forward iterator
/// operations.
struct bidirectional_iterator_tag : public forward_iterator_tag { };
/// Random-access iterators support a superset of bidirectional
/// iterator operations.
struct random_access_iterator_tag : public bidirectional_iterator_tag { };
//@}
iterator type决定了算法将怎么运作来获得最佳性能。如下，距离函数distance用来算两个迭代器间的距离，对于随机的（random_access_iterator_tag）直接相减就可以了，而对于广泛的，则是使用迭代器++，计数得到。
template<typename _InputIterator>
//使用迭代器类型萃取 获得长度类型 difference_type,不能随意返回int哦
inline typename iterator_traits<_InputIterator>::difference_type
__distance(_InputIterator __first, _InputIterator __last,
input_iterator_tag)//广泛型
{
...
}
//使用重载根据random_access_iterator_tag定位到函数
template<typename _RandomAccessIterator>
inline typename iterator_traits<_RandomAccessIterator>::difference_type
__distance(_RandomAccessIterator __first, _RandomAccessIterator __last,
random_access_iterator_tag)//随机访问型
{
...
}
仿函数
为什么需要仿函数
在某些算法需要传入函数的时候，在C语言里是传入函数指针。
C++可以传入一个重载了operator()的class，算法使用时会实例化这个class，然后调用operator()，这个class里的还可以重载operator()，就很方便。使用仿函数+模板，削弱了类型限制，毕竟运行时才知道传入的仿函数是不是正确的。
一个简单的例子：
template<typename ty1, typename ty2, typename op>
class Show {
public:
ty1 show(ty1 t1, ty2 t2) {
op()(t1);
op()(t1, t2);
// op()(t1, t2, t2); 编译不出错，运行时出错
}
};
struct op {
int operator()(int a, int b) {
std::cout << a + b << std::endl;
}
int operator()(int a) {
std::cout << a << std::endl;
}
};
int main() {
Show<int, int, op> s;
s.show(1, 2);
};
注意，为了让自己的仿函数具有更好的兼容性，要继承unary_function 或binary_function等（一元函数，二元函数），这里继承了里面的typedef，做到类似iterator type的效果。
STL可以传入的函数
当然可以传入算法的不是只有仿函数。
如下展示了可以传入：函数、仿函数、lambda函数、STL仿函数
struct MyLessObj
: public std::binary_function<int, int, bool> {
bool operator()(int a, int b) const {
return a < b;
}
};
bool MyLessFunc(int a, int b) {
return a < b;
}
int main() {
std::vector<int> v;
std::sort(v.begin(), v.end(), MyLessObj());
std::sort(v.begin(), v.end(), MyLessFunc);
std::sort(v.begin(), v.end(), [](int a, int b) { return a < b; });
std::sort(v.begin(), v.end(), std::less<int>());
};
STL提供的一些仿函数
比如，std::plus<T>，就是简单包装了operator+。在有些必须传简单仿函数时，可以直接传入。
仿函数的适配器
为什么需要仿函数适配器?
我们试图改变某个std函数或者自己写的函数里面的某个选项。
以std::bind2nd为例
std::less，我们可以指定比某个数值小，这时使用适配器std::bind2nd，将某个值绑定到第二个参数上。
本质上就是封装了一层，粗糙版见下：
struct MyLess {
bool operator()(int a, int b) const {
return a < b;
}
};
struct AdapterMyLess {
AdapterMyLess(int b) : b(b) {}
//重载()
bool operator()(int a) const {
return MyLess()(a, b);
}
int b;
};
//调用
//AdapterMyLess(1)(2);//2<1 false
而详细版需要考虑类型通用（泛型），类型检查（类型强转operatorT()）。
template<typename _Operation>
class binder2nd
/* unary_function 转换成一元函数，将属性传承下去
template<typename _Arg, typename _Result>
struct unary_function
{
typedef _Arg argument_type;
typedef _Result result_type;
};
*/
: public unary_function<typename _Operation::first_argument_type, typename _Operation::result_type>
{
protected:
//暂存，为了重载调用运算符
_Operation op;
typename _Operation::second_argument_type value;
public:
//构造函数
binder2nd(const _Operation& __x, const typename _Operation::second_argument_type& __y)
: op(__x), value(__y) { }
//重载调用运算符，真正起作用的部分
typename _Operation::result_type operator()(const typename _Operation::first_argument_type& __x) const
{ return op(__x, value);}
typename _Operation::result_type operator()(typename _Operation::first_argument_type& __x) const
{ return op(__x, value);}
};
//对外使用这个模板函数，对class binder2nd做了一层封装，返回了一个binder2nd对象
//目的是使用模板函数可以自动推导类型，不用像类模板那样必须指明类型，顺便把类型检查也做了
template<typename _Operation, typename _Tp>
inline binder2nd<_Operation> bind2nd(const _Operation& __fn, const _Tp& __x)
{
typedef typename _Operation::second_argument_type _Arg2_type;
//_Arg2_type(__x) 此处做编译期类型检查，是否可以转换成_Arg2_type类型
return binder2nd<_Operation>(__fn, _Arg2_type(__x));
}
//调用
std::bind2nd(std::less<int>(), 1)(2); //2<1 false
//或者直接调用对象
binder2nd<less<int>> b(less<int>(), 1);
b(2); //2<1 false
仿函数适配器都是这个套路，首先向上传递参数类型（为了可能被别人adapter），以便将来算法使用这些类型。然后重载()运算符，在这个重载函数里面做一些操作，再调用传入的仿函数对象的operator()。