cpp标准库体系结构与内核分析

发表于 分类于

STL体系结构与内核分析——侯捷

一 第一讲 STL与泛型编程

  1. 泛型编程：使用模板作为主要工具来编写程序。而STL就是使用泛型编程最好的例子。所以讨论的也就是STL
  2. 一些重要的网站
  3. STL的六大部件
    • 容器(container)
    • 分配器(allocator)
    • 算法(algorithm)
    • 迭代器(iterator)
    • 适配器(adapter)
    • 仿函数(functor)
  4. 在面向对象的时候，我们要求做成一个类，将数据和对它的操作放在一起。但是STL却是要求使用容器放数据，使用算法来操作数据，这是泛型编程的想法。上面的两种其实就是两种路子，他们是不一样的。
  5. 迭代器就相当于一种泛化的指针。仿函数就是一个类像一个函数。
  6. 分配器的分配类型和容器的内容类型一定要匹配。vector<int, allocator>;
  7. 前闭后开空间，所有的容器的begin指向的第一个元素，end指向的最后一个元素的下一个位置。
  8. 容器可以有两种次序，一种是顺序结构，一种是树状结构（内部是红黑树实现的）
  9. 对于测试程序，可以单独定义一个变量空间，然后对于变量可以在使用的地方进行定义，不同缩进
  10. 容器的增长是按照两倍两倍的增加，而不是一个一个增加。双端队列deque是一个一个的增加
  11. auto pItem = ::find(c.begin(), c.end(), target); 中的::表示全局范围内的find函数
  12. multiset，set和multimap，map是使用红黑树进行实现的。unordered_multiset和unordered_multimap都是使用哈希表进行的，使用hash表的时候，元素的个数大于篮子的个数的时候，就应该扩大篮子的数量了，所以篮子的个数一定大于元素的个数。这都是关联数据
  13. set中的元素是不可以重复的，因为值就是key，但是map的value和key是不一样的。
  14. 容器的背后需要一个东西支持容器对于内存的使用，这个东西就是分配器。
  15. 应该在程序中使用容器，而不是直接去使用分配器，对于需要较小的内存，可以使用new和free。

第二讲

  1. 模版分为类模板和函数模板，成员模板。标准库主要涉及前两个
  2. 面向对象编程将数据和模版合在一起，模板编程想要把数据和方法分开，那么算法是怎么得到数据的呢，通过的是迭代器将数据传递给算法，这样做的好处是容器和迭代器可以自己开发。
  3. 为什么sort可以放在vector等容器中，但是却不能放在list中，因为全局sort的实现中使用了随机的迭代器，而list不支持随机的迭代器。也就是说如果有一些容器自己带着sort的话，那么就使用自己带的sort，否则就使用全局的sort进行排序
  4. 所有的算法，内部的最终的涉及元素本身的操作，无非就是比大小。
  5. 类模板的泛化与特化。定义一个类的模板之后，我们对于绑定的特殊的值有一个更好的或独特的实现版本，这个时候就是类模板的特化。
  6. 类模板偏特化
    • 类模板接受两个或以上模板参数，其中部分进行绑定的时候，就会有一个特定的实现版本。这叫个数的偏特化
    • 对于一个泛化的类模板，如果绑定的是一个指针，就可以叫做范围的偏特化
  7. 分配器的效率影响容器的效率，所有的分配过程最底层最终都是malloc。
  8. 分配空间的时候，你需要的内存小，那么多加的那个部分的比例就大，如果你需要的内存大，那么多加的那个部分的比例就小。
  9. vc6+和BC++的allocator只是以::operator new 和operator delete完成allocate()和deallocate(),没有任何特殊设计。那么我们在给很多的数据分配内存的时候，就有可能实际数据的占据部分还没有额外添加的内容多。
  10. gnu c2.9自带了一个分配器，但是它的文档中说明了，不要使用它的分配器，它由一个更好的实现alloc，在stl_alloc.h中。这个分配器最主要的诉求就是减少malloc的次数，因为每一次malloc的时候，都有额外的开销cookie。这个更好的设计就是设计16条链表，每一条链表记录不同大小的内存，第一条就是8字节，第二条16字节，以此类推。当需要分配内存的时候，就找到最接近的大小，进行分配，这样就不需要记录分配的时候记录的cookie了，假设需要分配1000000个字节，那么这种方法就会减少大约800000字节的分配开销，这是极大的进步。真的是精妙！！！
  11. gnu c4.9又变成了原来的不使用特殊设计的那一种。
  12. c++可以前置的++两次，但是不允许后置的++两次，所以后置的++的操作符重载定义为 self operator++(int){}, 也就是返回值; 而前置的++的操作符重载为self& operator++(){} 返回的是引用。
  13. 算法需要向迭代器提问，迭代器的分类，值的类型，以及类型的距离，还有两种一共五种
  14. 为什么需要设计一个traits，因为如果迭代器退化为一个指针，那么算法就没有办法得到上面的几个回答，这个时候就需要traits了。解决计算机问题的尚方宝剑，加一个中间层。也就是说让算法去问traits。
  15. vector的增长方式是两倍两倍的增长，如果找不到，vector就不能增加了。也就是原来的尺寸乘以2。vector扩充的时候，找到两倍的空间，将原来的数据复制过来，并把安插点之后的数据也赋值过来，不光只是赋值安插点的数据，因为别的函数可能也会调用这个函数。这一过程会涉及到析构和拷贝构造函数，所以在速度上会慢一点。
  16. 所有的容器，只要是在连续空间内的就都要提供[]的运算符
  17. vector既然空间是连续的，那么它的迭代器只是需要指针就行了。
  18. array没有构造和析构函数，它是一个连续的空间，使用指针就可以作为迭代器。
  19. deque双向开口的队列，对外号称连续，实际上是分段连续的。每一个deque的大小是16*2 + 4*2 = 40字节。它在设置安插点的位置的时候，会判断安插点的位置，是离前面较近还是后面较近，也就是安插点和头尾的一般进行比较，如果离前面较近，就把前面的往前移动，否则就把后面的往后移动。
  20. 如何进行模拟连续的空间呢？都是deque iterators的功劳
  21. 使用后++来调用前++，使用后——来调用前——，这样的写法是有大家风范的。-=可以直接调用+=来进行实现。
  22. queue和stack可以看做是deque限制一部分得到的。也就是说是使用deque作为底层的服务。当然也可以使用list作为底层来作为服务。stack和queue都不允许遍历，也不提供iterator
  23. 关联式容器使用红黑树和哈希表进行底部的支持，这种关联式的容器，也可以看做是一种数据库，就是根据值去进行查找。
  24. 红黑树是高度平衡的二分查找树。
  25. set/multiset以rb_tree为底层结构，因此有自动排序的特性。排序的依据的key，而set/multiset的value和key合二为一，value就是key。我们无法使用set/multiset的iterators改变元素值，它的底层是红黑树的const iterator，就是为了禁止使用者对元素的赋值。
  26. 注意
  • set元素的key必须独一无二，因此其insert使用的红黑树的insert_unique().
  • multiset元素的key可以重复，因此其insert使用的是红黑树的insert_equal().
  1. 自己都不做事情，把所有的事情都转给其他人去做，比如，stack，queue，set等，这种设计也可以叫做适配器。
  2. map/multimap是以红黑树为底层结构，也可以自动排序，排序的依据是key。无法使用map/multimap的iterator来改变key，但是可以改变data。value=key+data。因此map/multimap内部自动将user指定key type为const，这样就可以禁止user对元素key的赋值。
  3. 注意
  • map元素的key必须独一无二，因此其insert使用的红黑树的insert_unique().
  • multimap元素的key可以重复，因此其insert使用的是红黑树的insert_equal().
  1. 对于哈希表，如果数据的个数多于篮子的个数，那么就需要增加篮子的个数，增加两倍的篮子的数量，一般是两倍的篮子的熟练旁边的质数。并且进行重新的rehashing。比如，53, 97, …
  2. 怎么将hash表中的元素变成数值，是一种经验的方法，最好是生成的数字更乱一些。标准库提供的是c风格的字符串变成数值。

第三讲 算法

  1. 六大部件中只有算法是函数模版，其他的都是类模板
  2. 算法是用来处理容器之中的数据的，算法中的前两个输入一定是迭代器，算法可以通过问答的形式来获得迭代器数据中的一些信息，这里的信息一般指的是数据怎么走。
  3. 容器所提供的迭代器的分类，不是1，2，3，4，5这种，而是类。这种类可以使用重载，代码更加简洁。
  4. 迭代器的分类分为5种，分别为输入迭代器，输出迭代器，前向迭代器，双向迭代器和随机访问迭代器。除了输出迭代器以外，后面的迭代器都继承自前面。这样就可以使用类来进行实现。
  5. copy在实际实现的时候，它在无所不用其极的找到一条效率最高的路线进行，这个判断的依据就可以根据迭代器的分类。算法的效率和它能不能判断出迭代器的分类由很大的关系。
  6. 算法没有办法要求迭代器的种类，但是可以通过命名对其种类进行暗示。
  7. 算法源码，c++的算法输入一定是前两个是两个迭代器，用来和容器进行沟通，如果不是这样的接口，那就是c++的接口
    • accumulate, accumulate(first, last, init)或accumulate(first, last, init, myfunc); 其中myfunc是这样的，init = binary_op(init, *first); 只要能够被()作用就行。可以是函数，也可以是一个类中对()进行重载，也就是仿函数。
    • for_each, for_each(first, last, myfunc());对容器中的每一个元素进行操作。另外，for(auto& elem : {1, 2, 3}); 这里的1, 2, 3是每一个元素的引用
    • replace， replace_if, replace_copy, replace(first, last, const T& old_value, const T& new_value);
    • count, count_if, 这是全局的,如果自己带有count，就直接使用自己的，可以更快，带成员函数的这8个都是关联式容器，可以通过key来进行查找，实现的时候可以更快，内部是红黑树和hash表进行实现的
      • 不带成员函数count(), array, vector, list, forward_list, deque
      • 带成员函数count(),set/multiset, map/multimap, unordered_set/unordered_multiset, unordered_map/unordered_multimap
    • find， find_if
      • 不带成员函数find(), array, vector, list, forward_list, deque
      • 带成员函数find(),set/multiset, map/multimap, unordered_set/unordered_multiset, unordered_map/unordered_multimap
    • sort默认由小到大进行排序，当然，如果传进sort的两个迭代器是my.rbegin(),my.rend(),也就是逆向的序列，这样的结果就是反向的排序，由大到小的排序
      • rbegin(){return reverse_iterator(end());} 也就是去取最后一个迭代器，当然取的方式翻转一下，也就是改变行为去取指针前面的元素
      • 不带成员函数sort()的有 array, vector, deque
      • 不带成员函数，但是因为内部的实现自然形成有序状态的有set/multiset, map/multimap, unordered_set/unordered_multiset, unordered_map/unordered_multimap
      • 容器带有成员函数sort()有list， forward_list, 全局算法要求的迭代器可以跳转，但是，list的迭代器不能跳转
    • binary_search, 一定要先排序，内部是使用lower_bound()实现的
  8. 仿函数，只为算法服务。也就是重载class中的()，这样的class所创建出来的对象，就叫函数对象，或者仿函数，因为它叫一个对象，实际上却像一个对象。你自己写的仿函数没有继承也可以运作，但是却没有融入STL。你的仿函数必须要继承unary_function或者binary_function中的一个，这两个父类的数据大小都是0，继承了也没有增加大小，但是，你的仿函数需要让适配器可以改造，适配器可能会问一些参数，这个参数都是来自于你写的仿函数继承的父类。
  9. 适配器，改一下函数名称，或者改一下参数个数等，都是一些比较小的改造。一般这种就是通过复合来进行实现的
  10. 适配器可以通过类适配器和对象适配器两种方式进行实现。
  11. bind是一种适配器，它可以绑定的类型
  • functions
  • function objects
  • member functions _必须是某个object的地址
  • data members _必须是某个object的地址
  1. 适配器就是把所要修饰的东西记下来，然后再看看怎么进行改造。
  2. 对于已经写好的行为，我们如何进行重新改变它的行为呢？通过的就是操作符号重载。
  3. 函数的适配器，容器的适配器，迭代器的适配器，还有X的适配器。X表示的是未知的
  4. 使用一个东西，却不明白它的道理，不高明！！！

第四讲

  1. 一个万用的hash function。讲一个复杂的结构拆分为简单的结构，然后使用单独的hash结果，再加起来，这样的方法，碰撞太严重。
  2. 0x9e3779b9这个数是一个黄金比例，单独计算每个项的hashcode的时候，可以加上这个值。这个万用的hash function整体上使用的可变的模版参数实现的。
  3. tuple 将一堆东西放在一起。将模版和元组和继承联系在一起。就可以递归的继承，这就是tuple的实现。
  4. 一个类要是包含了一个指针就一定需要写析构函数。
  5. c++没有规定，一个指针被delete两次会怎么样，所以可以判断一下

​