c++标准库

发表于 | 分类于 | 浏览 次

几个可以参考的网站：
http://www.cplusplus.com
https://en.cppreference.com/w
https://gcc.gnu.org

如何学习标准库．

标准库源码：gnu c++ 2.9.1版本．如何找到gnu c++2.9.1版本代码？

OOP: 将data和methods关联起来；
GP: 将data和methods分开来．

模板分为：

分配器

先谈一谈operator new()和malloc()
标准库中allocator的实现往往是使用operator new和operator delete，而operator new和operator delete又调用malloc和free来分配和释放内存．
SGI主要使用的是alloc．尽量减少调用malloc的次数．当使用自由链表来保存内存空间的大小时，不再需要在

set和map中都有一个rb_tree，set和rb_tree之间的关系是composition.

iterator

Iterator需要遵循的原则

  • value_type: Iterator所指向的元素的类型
  • difference_type: 两个Iterator之间的距离
  • iterator_category: Iterator有5种类型：输入迭代器，输出迭代器，单向迭代器，双向迭代器(bidirectional_iterator_tag)，随机迭代器(random_access_iterator_tag)

后面两种很少被用到．

  • reference
  • pointer

traits机制

如果Iterator是类类型，可以在类中定义value_type等，但若Iterator不是类类型，而是native pointer(native pointer也是一种迭代器).
特性萃取机必须有能力分辨它所获取的iterator是class Iterator T还是native pointer to T．

type traits <c++/type_traits>

type_traits不属于stl，但属于标准库．

iterator traits <c++/bits/stl_iterator.h>

属于stl．

char traits <c++/bits/char_traits.h>
allocator traits <c++/bits/alloc_traits.h>
pointer traits <c++/bits/ptr_traits.h>
array traits <c++/array>

容器 迭代器类型
array random_access_iterator
vector random_access_iterator
deque random_access_iterator
list bidirectional_iterator
forward list forward_iterator
rb tree bidirectional_iterator
unordered containers 取决于底层的链表是单向还是双向的

istream_iterator的iterator_category
某些类之间的继承关系是为了继承typedef

outstream_iterator的iterator_category

算法分类（iterator category）和type traits对算法效率的影响：

  • distance
  • advance
  • copy
  • copy_unique

容器

vector

vector和array的区别是：array的空间固定，一旦用尽，如果用户还希望使用更多空间，需要自己分配一个更大容量的array，并把旧的元素搬到新的array中，然后将旧的array的内存空间还给系统．而vector是动态空间，随着元素的加入，它的内部机制会自行扩充空间以容纳新元素．
vector每次扩充空间都分配当前容量两倍的空间．

array

array没有ctor，dtor
array与其他容器的区别在于，它需要一个size_t类型参数，表示数组的大小．
array的迭代器就是指针T*

deque

扩充：分配一个缓冲区．

reallocate_map

情形1: map_size = 14, old_num_nodes = 4, nodes_to_add = 2, add_at_front = true
new_num_nodes = 6;
map_size > 2 * new_num_nodes

如下图1所示：

1568792176139

接下来我们计算，new_start = map + (14-6)/2 + 2 = map + 6

1568792151484

之后，移动元素，修改start和finish迭代器所在的位置．蓝色部分是新配置的两个map_node.

1568792347185

情形2: map_size = 6, old_num_nodes = 3, nodes_to_add = 1, add_at_front = true
new_num_nodes = 4;
map_size < 2 * new_num_nodes
new_map_size = 6 + 6 + 1 = 13
new_start = new_map + (13 - 4) / 2 + 2 = new_map + 6

1568793668051

蓝色部分是新配置的map_node

1568793713183

hashtable

seperate chaing
当bucket中的链表过长时，就说明冲突的可能性很大了，需要扩容．
扩容过程：首先分配一块更大的内存，新内存的容量是大于旧的内存的两倍的一个质数．stl源码中准备了28个质数备用．
然后将旧内存中的每一个元素搬到新内存中去．这个过程中需要为每一个元素重新计算位置．
最后，释放旧的内存．

bucket所在的内存是连续的吗？底层使用的是什么结构？
buckets聚合体底层使用的是vector，

一个万能的hash Function

Algorithm

functor

为算法服务．

自己写functor并继承标准库的binary_function和unary_function.
functor要被Adapter改造时，Adapter可能会问functor一些问题，所以，自定义的functor应该继承unary_function, binary_function等．

1
2
3
4
5
6
7
8
9
10
11
12
template<class Arg, class Result>
struct unary_function {
    typedef Arg argument_type;
    typedef Result result_type;
};

template<class Arg1, class Arg2, class Result>
    struct binary_function {
    typedef Arg1 first_argument_type;
    typedef Arg2 second_argument_type;
    typedef Result result_type;
};

自定义的仿函数要能够被适配器改造，应该继承unary_function或者binary_function．

Adapter

通过内含的方式实现．

container adapter：stack，queue

functor adapter
iterator adapter

function Adaptable的条件是：继承unary_function或者binary_function．

<c++\backward\backward_warning.h>
reverse_iterator

inserter

ostream_iterator

istream_iterator