不会用标准库与其他语言没什么区别

C++11的标准库的体系结构与内核分析

C++标准库

C++标准模板库

先明白头文件引用

新式headers

无.h后缀名

旧式headers

带.h后缀名

而新式的headers内的组件都封装与namespace “std”中

旧式的std就不被封装于namespace “std”

标准库属于新式的headres中

STL的六大部件

  • 容器Container
  • 分配器Allocators
  • 算法Algorithms
  • 迭代器Iterators
    • 泛化的指针
  • 适配器Adapters（转换器）
    • 容器的适配器
    • 迭代器的适配器
    • 仿函数的适配器等等
  • 仿函数Functors

可以发现OOP的思想跟STL的设计思想是不大一样的

算法的复杂度

当前的常见的Big-oh

  • $O(1)$
  • $O(n)$
  • $O(log_2n)$
  • $O(n^2)$
  • $O(n^3)$
  • $O(2^n)$
  • $O(nlog_2n)$

容器大部分都是前闭后开区间，而且不一定是连续空间

一般分三类

  • Sequence Container

    • 顺序容器

  • Associative Container

    • 关联式容器

  • unordered Container

    • 无序容器

HashTable

Separate Chaining

Array

vector

list

Chainingdeque

queue

stack

multiset

multimap

unordered_multimap

unordered_set

非STL

hash_map

hash_set

源码面前，了无秘密

OOP(object oreinted)与GP（generic )的对比

datas 和 methods 结合

datas 与 methods 分离

Allocators

支持容器的内存分配的模块

在不同编译器下不同的分配器得实现源码都是有略微不同的

默认的分配器实际上就只是malloc和free的封装

如果有特殊需求。比如说当实现很多的量，在分配的时候，当我们的值只是一个很小的东西，分配器分配的内存开销相应的就会很大，我们可以指定使用其他的分配器

Container的设计实际上还是根据需求特性来，比如链表的设计核心，结点，数据。需要围绕着其来进行代码上的设计，观察STL库的源码可以发现，C++11看起来似乎糅合了许多OOP的思想（只是似乎），看起来会有些复杂，比如考虑到了对有状态的分配器的支持等等

iterator的设计原则，必须要有五个类型作为特征，并且根据要达到的功能进行各种的重载函数，虽然大体思想还是GP编程

而算法要怎么判断迭代器的类型，并且使用调用达到算法的效果，需要iterator traits来进行甄别。

一般traits 有两个通道，一个是迭代器通道，一个是普通指针通道

deque

双向开口“连续”容器

是一个vector管理着N个array

利用deque做底层结构可以衍生出queue和stack

RB_Tree

RB_Tree的简单理解

红黑结点与root

利用RB_Tree底层结构衍生实现map和set

两者区别在于set 的RBTree 的key = value

而map key = key value = value `

而multiset or multimap 就在RBtree的insert_unique与iinsert_equal区别调用

hashtable

简单理解：多个（有上限）不同规格的桶的连续结合（vector)

桶实际的底层结构是有上限的链表上限一般取决于桶的总个数

超过上限就要增加桶

桶的个数呢一般选择的是质数（1是最小公因数）

增加桶一般是乘2后取左右的质数，所有的桶内的元素都要重新进行分配

所以hashtable也被称作 Separate Chaining

需要知道的是 放入的元素不同，需要指定不同的规则，在设计hashtable的时候需要指定符合规则的行为(谓词)

  • HashFcn

    • 元素映射hash code
    • 元素放置规则，注意设计的越杂乱容易不发生元素碰撞

  • EqualKey

    • 元素相等判断

  • ExtractKey

    • key and value区分，为map和set区分服务

c++11后一半都选用unordered_set而不是hash_set，这个名字一开始是民间名字，加入了标准库后，改名哩，虽然hash_set也能用

算法

algorithms

从语言层面讲，是个function template

迭代器的分类

  • input_iterator_tag
    • farward_iterator_tag
      • bidirectional_iterator_tag
        • random_access_iterator_tag
  • output_iterator_tag

表继承方式

源码是这样的继承关系

迭代器分类和type traits对算法的影响

pred

返回值都是bool

根据参数的多少被称为N元谓词

标准库中的二分查找（binary_search)基于两个函数

  • lower_bound()
  • upper_bound()

标准库源代码示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
template<class ForwardIterator, class T>
    ForwardIterator
    lower_bound(ForwardIterartor first, ForwardIterator last, const T& val)
{
    ForwardIterator it;
    iteratoor_traits<ForwardIterator>::difference_type count, step;
    count = distance(first, last);
    while(count > 0) {
		it = first; step = count / 2; advance9it, step);
        if(*it , val){
            first = ++it;
            count -= step + 1;
        }
        else count = step;
    }
    return first;
}

functors 仿函数

这个东西基本只为算法服务

标准库中基本又主要的三大类，实际上不止3个

  • Arithmetic
  • Logical
  • Relational

而每一个STL的functors 都需要选择适当的适配分类（adaptable）继承

Adapters适配器

（类似转换头）

container adapters 容器适配器

  • stack
  • queue

iterator adapters 迭代器适配器

functor adapters 函数适配器

bind2nd是个用来辅助binder2nd函数适配器的辅助函数,帮助记录第一个参数和第二参数的类型，binder2nd再通过知道的类型定义内部成员。俗称，实参类型推导

实际上在C++11中bind2nd 实际使用的是 std::bind 新型适配器

include\

可以绑定函数，仿函数（函数对象），成员函数，成员变量

设计模式adapter