精华内容
下载资源
问答
  • 2018-12-11 20:24:43

    前言

    本专栏主要以STL源码剖析分析路线来分析SIGSTL3.0源码.

    整个模块准备对学习STL源码剖析之后做一个系统的总结, 这些都是我个人的理解, 如果分析有什么问题欢迎各位大佬们指出. 也很感谢作者以及网络中各个大佬的总结, 让我也能更容易更深刻的理解到STL强大和方便, 也让我对template感受深刻.

    以下是我自己对STL版块进行分析.

    总共分为六个版块 : 空间配置器, 迭代器, 容器(序列容器, 关联容器), 算法, 仿函数, 配接器.


    STL前期准备

    在学习STL源码之前需要对template有一个认识或者回忆.

    template(一)

    template(二)

    template(三)

    STL分析


    空间配置器

    c/c++都需要手动的管理内存, 而封装实现一个能申请空间又能自己释放空间不再让我们自己管理. 而STL就实现了这样的一个功能, 它就是空间配置器. 而空间配置器一般是隐藏在各个版块的组件, 实现中我们都看不到它的存在, 但是它确实是非常重要的部分, 因为它, 所有的版块操作内存时都直接调用它就行了, 而不需要再实现内存的分配.

    0. new实现

    1. 空间配置器

    2. 第一级配置器

    3. 第二级配置器

    4. 内存池


    迭代器

    每个组件都可能会涉及到对元素的简单操作, 比如 : 访问, 自增, 自减等. 每个组件都的数据类型可能不同, 所以每个组件可能都要自己设计对自己的操作. 但将每个组件的实现成统一的接口就是迭代器,

    它的优点也很明显:

    1. 它是能屏蔽掉底层数据类型差异的.
    2. 迭代器将容器和算法粘合在一起, 使版块之间更加的紧凑, 同时提高了执行效率, 让算法更加的得到优化.

    这些实现大都通过traits编程实现的. 它的定义了一个类型名规则, 满足traits编程规则就可以自己实现对STL的扩展, 也体现了STL的灵活性. 同时straits编程让程序根据不同的参数类型选择执行更加合适参数类型的处理函数, 也就提高了STL的执行效率. 可见迭代器对STL的重要性.

    1. 迭代器

    2. template(四)

    3. traits萃取剂

    4. template(五)

    5. __type_traits型别


    容器

    容器是封装了大量常用的数据结构, 因为容器, 凸显出STL的方便, 操作简单. 毕竟它将常用的但是实现比较麻烦的数据结构封装之后就可以直接的调用, 不再让用户重写一长串的代码实现.

    容器根据排列分为了序列式和关联式.

    1. 序列式包括vector, list, deque等. 序列容器有头或尾, 甚至有头有尾.
    2. 关联式包括map, set, hashtable等. 关联容器没有所谓的头尾, 只有最大值, 最小值.

    学习容器的时候要注意end返回的是最后一元素的后一个地址, 这个地址并没有储存实际的值.

    0. uninitialized系列函数

    序列容器

    1. vector序列容器(一)

    2. vector序列容器(二)

    3. vector序列容器(三)

    4. list有序容器(一)

    5. list有序容器(二)

    6. list有序容器(三)

    7. deque有序容器(一)

    8. deque有序容器(二)

    9. deque有序容器(三)

    10. stack配接器

    11. queue配接器

    12. heap大根堆

    13. 优先级队列

    14. slist有序容器(一)

    15. slist有序容器(二)


    关联容器

    1. RB-tree关联容器(一)

    2. RB-tree关联容器(二)

    3. set配接器

    4. pair结构体

    5. map配接器

    6. multiset配接器

    7. multimap配接器

    8. hashtable关联容器(一)

    9. hashtable关联容器(二)

    10. hash_set配接器

    11. hash_multiset配接器

    12. hash_map配接器

    13. hash_multimap配接器


    算法

    STL的算法有很多, 有简单也有一些复杂的, 这里我就以STL3.0源码为例, 挑选出来几个常用的算法来进行分析.

    1. copy算法

    2. rotate算法

    3. 数值算法

    4. stl_algo.h中的基本算法

    5. 二分查找算法


    仿函数

    所谓仿函数也就是函数对象, 以前是这样称呼它的, 只是一直沿用至今了. 仿函数就是一种具有函数特质的对象. STL因为仿函数, 大大在增加了灵活性, 而且可以将部分操作由用户自己来定义然后传入自定义的函数名就可以被调用. 但是你会发现仿函数实现的功能都是相当简单的, 而且都要通过配接器再封装才能够使用.

    STL的仿函数根据参数个数可以分为 : 一元仿函数和二元仿函数. 根据功能可分为 : 算术运算, 关系运算和逻辑运算.

    1. 仿函数

    配接器

    主要用来修改接口. 修改迭代器的接口, 修改容器的接口, 修改仿函数的接口.

    1. 配接器

    总结

    STL这本书对我这个菜鸟收获还是挺有帮助的, 了解了template的强大, STL对程序做到了最大的优化. STL对每个功能都尽可能的单一, 然后可能通过多次的函数调用才调用真正执行的函数.

    让我对c++的模板有了一个更深的认识, 真的很难, 自己还差的太远, 努力加油!

    更多相关内容
  • stl 源码分析

    2018-08-11 09:43:01
    源码之前,了无秘密。大师们的缜密思维、经验结晶、技术思路、独到风格,都原原本本体现在源码之中。 这本书所呈现的源码,使读者看到vector的实现、list的实现、heap的实现、deque的实现、Red Black tree的实现、...
  • STL源码分析

    2017-12-03 20:26:02
    C++ STL源码剖析扫描版 身为C++标准库最重要的组成部分STL不公是一个可复用的组件库,而且是一个包罗算法与数据结构的软件框架。
  • STL源码分析和EFFECTIVE

    2018-10-23 10:15:06
    STL源码分析和EFFECTIVE C++,侯捷书籍,如果有需要可以直接找我
  • 本書假設你對STL 已有基本認識和某種程度的運用經驗。因此除了第㆒章略作介 紹之外,立刻深入STL 技術核心,並以STL 六大組件(components)為章節之進 行依據。以㆘是各章名稱,這樣的次序安排大抵可使每㆒章所剖析...
  • STL,STL有6大部件 标准库以header files形式呈现 C++标准库得header files 不带副档名(.h) 例如:#include<vector> 新式C header files 不带副档名.h 例如: #include<cstdio> 旧式C header files...

    C++ Standard Library

    C++付给你得头文件

    Standard Template Library

    在标准库中百分之80是STL,标准库>STL,STL有6大部件

    标准库以header files形式呈现

    • C++标准库得header files 不带副档名(.h) 例如:#include<vector>
    • 新式C header files 不带副档名.h  例如: #include<cstdio>
    • 旧式C header files(带有副档名 .h)仍可以用   例如#include<stdio.h>
    • 所有新式headers内的组件封装于 namespace std
    • 旧式的headers内的组件不封装于 namespace std

    重要资源网站

    • cplusplus.com
    • cppreference.com
    • gcc.gnu.org

    STL体系机构

    1.STL组成

    STL有六大部件

    • 容器(Containers)
    • 分配器(Allocators)
    • 算法(Algorithms)
    • 迭代器(Iterators)
    • 适配器(Adapters)
    • 仿函数(Functors)

    应用场景

    2.容器区间

    标准库规定使用前闭后开区间来表示元素的区间。

    begin()为容器的第一个元素,而end()是容器中最后一个元素的下一个元素

    C++ 11提供了新的 range-based for statement

    for( decl : coll){
        statement
    }
    for(int i:{2,3,4,5,6}){
        std::cout<<i<<std::end;
    }
    
    vector<int> vec
    for(aotu elem : vec){
        cout<<elem<<endl;
    }
    
    for( auto& elem : vec){
        elem*=3;
    }

    3.容器的分类

    序列式容器(sequence containes)

    关联式容器(associative containers):用于大量查找;

    不定序容器(unordered containers):C++11 新增的,其实属于关联式容器

    下面以缩进的形式表示“基层与衍生层的关系(衍生并非继承,而是复合)

    序列式容器

    • array:连续空间  since C++ 11
    • vector: 连续空间
      • heap:以算法形式呈现
      • priority_queue
    • list:双向
    • slist:单向,非标准
    • deque:分段连续空间
      • stack:  container adapter容器适配器
      • queue: container adapter容器适配器

    关联式容器

    • rb_tree 非公开
      • set
      • map
      • multiset
      • multimap
    • hashtable 非公开
      • hash_set  非标准
      • hash_map 非标准
      • hash_multiset 非标准
      • hash_multimap 非标准

    注:C++ 11中,slist名为forward_list,hash_set,hash_map名为unordered_set,unordered_map.....

    相关预备知识

    1.函数重载

    之前写过一篇非常详细的C++中函数重载的博客,直接发个传送门

    https://blog.csdn.net/weixin_39568744/article/details/105329524

    2.泛型编程

    之前写过一篇非常详细的C++中泛型编程的博客,直接发个传送门

    https://blog.csdn.net/weixin_39568744/article/details/105950208

    展开全文
  • STL源码剖析 2015年12月新版,源码之前,了无秘密。大师们的缜密思维、经验结晶、技术思路、独到风格,都原原本本体现在源码之中。 作者:侯捷 著出版社:华中科技大学出版社出版时间:2015年12月
  • 程序员进阶书籍系列 程序员进阶之路高清pdf系列书籍之--STL源码剖析简体中文完整版(清晰扫描带目录)pdf
  • STL源码分析(总结)

    千次阅读 2017-08-24 20:04:07
    STL六大组件 容器(containers):是一种class template,里面包含各种数据结构。 算法(algorithms):是一种function template,里面包含各种算法。 迭代器(iterators):是所谓的泛型指针,每个容器都有自己的专...

    STL六大组件

    1. 容器(containers):是一种class template,里面包含各种数据结构。
    2. 算法(algorithms):是一种function template,里面包含各种算法。
    3. 迭代器(iterators):是所谓的泛型指针,每个容器都有自己的专属的迭代器,知道如何遍历自己的元素。
    4. 仿函数(functors):是一种重载了operator()的class或class template,可作为算法的某种策略。
    5. 配接器(adapters):是一种用来修饰容器或仿函数或迭代器接口的东西。
    6. 配置器(allocators):是一个实现了动态空间配置,空间管理,空间释放的class template,负责空间配置与管理。

    空间配置器

    构造

    1. 分配新的空间
    2. 在新空间上构造对象
    template <class T>
    inline T* _allocate(...) {
        ...
        T* tmp = (T*)(::operate new((size_t)(size * sizeof(T))));
        ...
    }
    template <class T1, class T2>
    inline void _construct(T1* p, const T2& value) {
        new(p) T1(value);   //placement new.
    }

    operator new
    (1)只分配所要求的空间,不调用相关对象的构造函数。当无法满足所要求分配的空间时,则
    ->如果有new_handler,则调用new_handler,否则
    ->如果没要求不抛出异常(以nothrow参数表达),则执行bad_alloc异常,否则
    ->返回0
    (2)可以被重载
    (3)重载时,返回类型必须声明为void*
    (4)重载时,第一个参数类型必须为表达要求分配空间的大小(字节),类型为size_t
    (5)重载时,可以带其它参数

    Placement new

    placement new 是重载operator new 的一个标准、全局的版本,它不能够被自定义的版本代替(不像普通版本的operator new和operator delete能够被替换)。

    对象的分配

    在已分配的缓存区调用placement new来构造一个对象。
    Task *ptask = new (buf) Task

    SGI中的空间配置与释放(std::alloc)

    SGI设计哲学:
    - 向system heap要求空间
    - 考虑多线程状态
    - 考虑内存不足时的应变措施
    - 考虑过多“小型区块”可能造成的碎片问题

    内存分配中使用::operator new()与::operator delete()分配与释放相当于molloc()与free().

    考虑第四点设计了双层配置器,第一层直接调用malloc()和free().
    配置内存小于128bytes时,使用第二级配置器:
    使用16个自由链表负责16种小型区块的次级配置能力。如果内存不足转一级配置器。

    8 16 24 32 40 48 56 64 72 80 88 96 104 112 120 128

    迭代器

    迭代器类似于一种智能指针,比较重要的行为有内容提领成员访问

    迭代器相应型别

    为了让迭代器适应不同种类的容器即泛化,需利用function template的参数推导机制推导型别。

    偏特化如果class template拥有一个以上的template参数,我们可以针对其中某个template参数进行特化工作(我们可以在泛化设计中提供一个特化版本)。

    trans编程技法

    声明内嵌型别推导函数返回值:

    template <class T>
    struct MyIter {
        typedef T value_type;   //内嵌型别
        T* ptr;
        MyIter(T* p=0) : ptr(p) {}
        T& operator*() const { return *ptr; }
        //...
    }
    
    template <class I>
    typename I::value_type  //这一整行是func的返回值型别
    func(I ite) {
        return *ite;
    }
    
    MyIter<int> ite(new int(8));
    cout << func(ite);

    萃取型别:

    template <class I>
    struct iterator_traits {
        typedef typename I::value_type value_type;
    }
    
    template <class I>
    typename iterator_traits<I>::value_type //函数返回型别
    func(I ite) {
        return *ite;
    }
    
    //萃取原生指针,偏特化版本
    template <class T>
    struct iterator_traits<T*> {
        typedef T value_type;
    };

    STL根据经验,定义了迭代器最常用到的五种类型:value_type、difference_type、pointer、reference、iterator_category,任何开发者如果想将自己开发的容器与STL结合在一起,就一定要为自己开发的容器的迭代器定义这五种类型,这样都可以通过统一接口iterator_traits萃取出相应的类型,下面列出STL中iterator_traits的完整定义:

    tempalte<typename I>
    struct iterator_traits
    {
        typedef typename I::iterator_category iterator_category;
        typedef typename I::value_type value_type;
        typedef typeanme I:difference_type difference_type;
        typedef typename I::pointer pointer;
        typedef typename I::reference reference;
    };

    重点提一下iterator_category:
    根据移动特性与施行操作,迭代器被分为五类:

    1. Input Iterator:只读
    2. Output Iterator:只写
    3. Forward Iterator:允许“写入型”算法(例如replace())在此种迭代器所形成的区间上进行读写操作。
    4. Bidirectional Iterator:可双向移动。
    5. Random Access Iterator:前四种迭代器都只供应一部分指针算术能力(前三种支持 operator++,第四种再加上operator–),第五种则涵盖所有指针算术能力,包括p+n, p-n, p[n], p1-p2, p1

    序列式容器

    序列式容器.jpg-7.5kB
    元素可序但未必有序

    vector

    vector底层为动态数组,分配策略为:

    • 如果vector原大小为0,则配置1,也即一个元素的大小。
    • 如果原大小不为0,则配置原大小的两倍。

    当然,vector的每种实现都可以自由地选择自己的内存分配策略,分配多少内存取决于其实现方式,不同的库采用不同的分配策略。
    当以两倍空间增长时之前分配的内存空间不可能被使用,这样对于缓存并不友好。
    相关连接:https://www.zhihu.com/question/36538542

    vector的迭代器
    使用vector迭代器时要时刻注意vector是否发生了扩容,一旦扩容引起了空间重新配置,指向原vector的所有迭代器都将失效

    vector维护的是一个连续线性空间,与数组array一样,所以无论其元素型别为何,普通指针都可以作为vector的迭代器而满足所有必要的条件。vector所需要的迭代器操作,包括operator*,operator->,operator++,operator–,operator+=,operator-=等,普通指针都具有。

    vector提供了Random Access Iterators。

    vector的数据结构
    vector底层为连续线性空间
    此处输入图片的描述

    list

    list容器完成的功能实际上和数据结构中的双向链表是极其相似的,list中的数据元素是通过链表指针串连成逻辑意义上的线性表

    对于迭代器,只能通过“++”或“–”操作将迭代器移动到后继/前驱节点元素处,而不能对迭代器进行+n或-n的操作。增加任何元素都不会使迭代器失效。删除元素时,除了指向当前被删除元素的迭代器外,其它迭代器都不会失效。
    此处输入图片的描述

    deque

    **deque是一种双向开口的线性空间。**deque容器类与vector类似,支持随机访问和快速插入删除,它在容器中某一位置上的操作所花费的是线性时间。虽然vector也支持从头端插入元素,不过效率奇差,deque与vector最大差异:

    • deque允许常数时间内对起头端进行元素的插入或移除操作。
    • deque没有所谓的容量观念,因为它是动态的以分段连续空间组合而成,随时可以增加一段新的空间并拼接起来。

    此处输入图片的描述

    一旦有必要在deque的前段或尾端增加新空间,便配置一段定量连续空间,串在整个deque的头端或尾端。迭代器较为复杂,操作复杂度大。

    deque是由一块所谓的map作为主控,map是一段连续的空间,其中每个元素指向另一段连续的空间,称为缓冲区。一旦map空间不足,需配备一块更大的map。

    deque迭代器
    虽然deque也提供Random Access Iterators,不过其迭代器比较特殊。
    此处输入图片的描述
    迭代器失效:
    插入操作:

    1、在队前或队后插入元素时(push_back(),push_front()),由于可能缓冲区的空间不够,需要增加map中控器,而中控器的个数也不够,所以新开辟更大的空间来容纳中控器,所以可能会使迭代器失效;但指针、引用仍有效,因为缓冲区已有的元素没有重新分配内存。

    2、在队列其他位置插入元素时,由于会造成缓冲区的一些元素的移动(源码中执行copy()来移动数据),所以肯定会造成迭代器的失效;并且指针、引用都会失效。

    删除操作:

    1、删除队头或队尾的元素时,由于只是对当前的元素进行操作,所以其他元素的迭代器不会受到影响,所以一定不会失效,而且指针和引用也都不会失效;

    2、删除其他位置的元素时,也会造成元素的移动,所以其他元素的迭代器、指针和引用都会失效。

    stack

    是一种配接器,将接口改变符合先进后出规则,没有迭代器。
    以deque为底层容器,以list为底层容器。

    queue

    是一种配接器,将接口改变符合先进先出规则,没有迭代器。
    以deque为底层容器,以list为底层容器。

    priority_queue

    是一种配接器,没有迭代器,是以二叉堆为底层数据结构来实现的,所以先简单介绍heap。

    heap

    堆的实现通过构造二叉堆(binary heap),实为二叉树的一种;由于其应用的普遍性,当不加限定时,均指该数据结构的这种实现。这种数据结构具有以下性质。

    • 任意节点小于(或大于)它的所有后裔,最小元(或最大元)在堆的根上(堆序性)。
    • 堆总是一棵完全树。即除了最底层,其他层的节点都被元素填满,且最底层尽可能地从左到右填入。

    将根节点最大的堆叫做最大堆或大根堆,根节点最小的堆叫做最小堆或小根堆,STL供应的是最大堆。

    在SGI STL中用array来实现堆,则当某个节点位于i处时,其左子节点和右子节点分别为2i,2i+1,父节点为i/2.

    priority_queue 优先级队列是一个拥有权值概念的单向队列queue,在这个队列中,所有元素是按优先级排列的(也可以认为queue是个按进入队列的先后做为优先级的优先级队列——先进入队列的元素优先权要高于后进入队列的元素)。

    priority_queue默认使用vector作为底层容器,默认会在构造时通过max-heap建堆。

    关联式容器

    标准的STL关联式容器分为set(集合)/map(映射表)两大类,以及这两大类的衍生体multiset(多键集合)和 multimap(多键映射表)。这些容器的底层机制均以RB-tree(红黑树)完成。RB-tree也是一个独立容器,但并不开放给外界使用。

    此外,SGI STL 还提供了一个不在标准规格之列的关联式容器:hash table (散列表),以及以此hash table 为底层机制而完成的hash_set(散列集合)、hash_map(散列映射表)、hash_multiset(散列多键集合)、hash_multimap(散列多键映射表)。

    根据C++ 11标准的推荐,用unordered_map代替hash_map。

    所谓的关联式容器,观念上类似关联式数据库:每笔数据(每个元素)都有一个键值(key)和一个实值(value)。当元素被插入到关联式容器中时,容器内部结构(可能是RB-tree ,也可能是hash-table)便依照其键值大小,以某种特定规则将这个元素放置于适当位置。关联式容器没有所谓的头尾(只有最大元素和最小元素),所以不会有所谓push_back()/push_front()/pop_back()/pop_front()/begin()/end() 这样的操作行为。

    一般而言,关联式容器的内部结构是一个balanced binary tree(平衡二叉树),以便获得良好的搜寻效率。balanced binary tree 有许多种类型,包括AVL-tree、RB-tree、AA-tree ,其中最被广泛运用于STL的是RB-tree(红黑树)。

    关联式容器-22.9kB

    红黑树

    算法导论对R-B Tree的介绍:
    红黑树,一种二叉查找树,但在每个结点上增加一个存储位表示结点的颜色,可以是Red或Black。
    通过对任何一条从根到叶子的路径上各个结点着色方式的限制,红黑树确保没有一条路径会比其他路径长出俩倍,因而是接近平衡的。

    红黑树的5个性质:

    1. 每个结点要么是红的要么是黑的。
    2. 根结点是黑的。
    3. 每个叶结点(叶结点即指树尾端NIL指针或NULL结点)都是黑的。
    4. 如果一个结点是红的,那么它的两个儿子都是黑的。
    5. 对于任意结点而言,其到叶结点树尾端NIL指针的每条路径都包含相同数目的黑结点。

    红黑树能够以O(log2 n) 的时间复杂度进行搜索、插入、删除操作。此外,由于它的设计,任何不平衡都会在三次旋转之内解决。当然,还有一些更好的,但实现起来更复杂的数据结构,能够做到一步旋转之内达到平衡,但红黑树能够给我们一个比较“便宜”的解决方案。红黑树的算法时间复杂度和AVL相同,但统计性能比AVL树更高。

    红黑树节点和迭代器:
    红黑树节点和迭代器的设计和slist原理一样,将结构和数据分离.原理如下:

    struct __rb_tree_node_base
    {
      typedef __rb_tree_color_type color_type;
      typedef __rb_tree_node_base* base_ptr;
      color_type color;     // 红黑树的颜色
      base_ptr parent;      // 父节点
      base_ptr left;        // 指左节点
      base_ptr right;       // 指向右节点
    }
    template <class Value>
    struct __rb_tree_node : public __rb_tree_node_base
    {
      typedef __rb_tree_node<Value>* link_type;
      Value value_field;    // 存储数据
    };

    红黑树的基础迭代器为struct __rb_tree_base_iterator,主要成员就是一个__rb_tree_node_base节点,指向树中某个节点,作为迭代器与树的连接关系,还有两个方法,用于将当前迭代器指向前一个节点decrement()和下一个节点increment().下面看下正式迭代器的源码:

    template <class Value, class Ref, class Ptr>
    struct __rb_tree_iterator : public __rb_tree_base_iterator
    {
      typedef Value value_type;
      typedef Ref reference;
      typedef Ptr pointer;
      typedef __rb_tree_iterator<Value, Value&, Value*>     iterator;
      typedef __rb_tree_iterator<Value, const Value&, const Value*> const_iterator;
      typedef __rb_tree_iterator<Value, Ref, Ptr>   self;
      typedef __rb_tree_node<Value>* link_type;
      __rb_tree_iterator() {}//迭代器默认构造函数
      __rb_tree_iterator(link_type x) { node = x; }//由一个节点来初始化迭代器
      __rb_tree_iterator(const iterator& it) { node = it.node; }//迭代器复制构造函数
      //迭代器解引用,即返回这个节点存储的数值
      reference operator*() const { return link_type(node)->value_field; }
    #ifndef __SGI_STL_NO_ARROW_OPERATOR
      //返回这个节点数值值域的指针
      pointer operator->() const { return &(operator*()); }
    #endif /* __SGI_STL_NO_ARROW_OPERATOR */
      //迭代器++运算
      self& operator++() { increment(); return *this; }
      self operator++(int) {
        self tmp = *this;
        increment();
        return tmp;
      }
      //迭代器--运算
      self& operator--() { decrement(); return *this; }
      self operator--(int) {
        self tmp = *this;
        decrement();
        return tmp;
      }
    };
    inline bool operator==(const __rb_tree_base_iterator& x,
                           const __rb_tree_base_iterator& y) {
      return x.node == y.node;
      // 两个迭代器相等,指这两个迭代器指向的节点相等
    }
    inline bool operator!=(const __rb_tree_base_iterator& x,
                           const __rb_tree_base_iterator& y) {
      return x.node != y.node;
      // 两个节点不相等,指这两个迭代器指向的节点不等
    }

    迭代器的解引用运算,返回的是这个节点的值域.所以对于set来说,返回的就是set存储的值,对于map来说,返回的就是pair

    size_type node_count; // 记录树的大小(节点的个数)
    link_type header;    
    Compare key_compare;     // 节点间的比较器,是仿函数

    对于header,其实相当与链表中的头节点,不存储数据,可用于红黑树的入口.header的设计可以说的STL红黑树设计的一个亮点,header和root互为父节点,header的左节点指向最小的值,header的右节点指向最大的值,所以header也可以作为end()迭代器指向的值.图示如下:
    此处输入图片的描述

    红黑树的操作就不再赘述,算法书里都有介绍。

    map&set

    map底层用的是红黑树,所以map只是在红黑树上加了一层封装,set同理。
    multiset与multimap与上述最大的不同在于允许重复的键值在红黑树上,插入操作采用的是底层RB-Tree的insert_equal()而非insert_unique()

    迭代器失效:如果迭代器所指向的元素被删除,则该迭代器失效。其它任何增加、删除元素的操作都不会使迭代器失效。

    hashtable

    hashtable即所谓的散列表,对于冲突的解决方法,stl采用开链的方法来解决冲突。STL的做法是在bucket中维护一个list,然后key对应的值插入list。至于buckets聚合体,stl采用vector作为底层容器。
    hash_table节点的定义:

    template <class _Val>
    struct _Hashtable_node
    {
      _Hashtable_node* _M_next;
      _Val _M_val;
    };

    此处输入图片的描述

    hashtable的迭代器:

    struct _Hashtable_iterator {
      typedef _Hashtable_node<_Val> _Node;
    
      typedef forward_iterator_tag iterator_category;
    
      _Node* _M_cur;
      _Hashtable* _M_ht;
    
      iterator& operator++();
      iterator operator++(int);
    };

    hashtable的迭代器类型为ForwardIterator,所以只支持operator++操作。

    hashtable关键实现:
    对于散列表大小的选取,CLRS上面也提到了m常常选择与2的幂不太接近的质数。在这种情况下,取一个素数总是个不坏的选择。
    SGI STL提供了28个素数最为备选方案,__stl_next_prime可以选出一个最接近n且比n要大的素数。

    enum { __stl_num_primes = 28 };
    
    static const unsigned long __stl_prime_list[__stl_num_primes] =
    {
      53ul,         97ul,         193ul,       389ul,       769ul,
      1543ul,       3079ul,       6151ul,      12289ul,     24593ul,
      49157ul,      98317ul,      196613ul,    393241ul,    786433ul,
      1572869ul,    3145739ul,    6291469ul,   12582917ul,  25165843ul,
      50331653ul,   100663319ul,  201326611ul, 402653189ul, 805306457ul,
      1610612741ul, 3221225473ul, 4294967291ul
    };
    
    inline unsigned long __stl_next_prime(unsigned long __n)
    {
      const unsigned long* __first = __stl_prime_list;
      const unsigned long* __last = __stl_prime_list + (int)__stl_num_primes;
      const unsigned long* pos = lower_bound(__first, __last, __n);
      return pos == __last ? *(__last - 1) : *pos;
    }
    
    size_type max_bucket_count() const
    {
      return __stl_prime_list[(int)__stl_num_primes - 1];
    }

    hash_table的模板参数

    template <class _Val, class _Key, class _HashFcn,
              class _ExtractKey, class _EqualKey, class _Alloc>

    其中

    // 重新调整表格大小
    template <class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
    void hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>
      ::resize(size_type __num_elements_hint)
    {
      const size_type __old_n = _M_buckets.size();
      // 超过原来表格的大小时才进行调整
      if (__num_elements_hint > __old_n) {
        // 新的表格大小
        const size_type __n = _M_next_size(__num_elements_hint);
        // 在边界情况下可能无法调整(没有更大的素数了)
        if (__n > __old_n) {
          vector<_Node*, _All> __tmp(__n, (_Node*)(0),
                                     _M_buckets.get_allocator());
          __STL_TRY {
            // 填充新的表格
            for (size_type __bucket = 0; __bucket < __old_n; ++__bucket) {
              _Node* __first = _M_buckets[__bucket];
              while (__first) {
                size_type __new_bucket = _M_bkt_num(__first->_M_val, __n);
                _M_buckets[__bucket] = __first->_M_next;
                __first->_M_next = __tmp[__new_bucket];
                __tmp[__new_bucket] = __first;
                __first = _M_buckets[__bucket];
              }
            }
            // 通过swap交换
            _M_buckets.swap(__tmp);
          }
    #         ifdef __STL_USE_EXCEPTIONS
          // 异常处理
          catch(...) {
            for (size_type __bucket = 0; __bucket < __tmp.size(); ++__bucket) {
              while (__tmp[__bucket]) {
                _Node* __next = __tmp[__bucket]->_M_next;
                _M_delete_node(__tmp[__bucket]);
                __tmp[__bucket] = __next;
              }
            }
            throw;
          }
    #         endif /* __STL_USE_EXCEPTIONS */
        }
      }
    }

    unordered_map

    unordered_map是以hash_table为底层容器来实现的。

    算法

    STL算法部分主要由头文件,,组成。要使用 STL中的算法函数必须包含头文件,对于数值算法须包含,中则定义了一些模板类,用来声明函数对象。
    STL中算法大致分为四类:
    1. 非可变序列算法:指不直接修改其所操作的容器内容的算法。
    2. 可变序列算法:指可以修改它们所操作的容器内容的算法。
    3. 排序算法:包括对序列进行排序和合并的算法、搜索算法以及有序序列上的集合操作。
    4. 数值算法:对容器内容进行数值计算。

    stl中大概有70个算法,不再一一列举。接下来介绍STL中最庞大的sort()排序算法。

    sort:
    sort接受两个RandomAccessIterators(随机存取迭代器),然后将区间内的所有元素以渐增方式从小到大排列。第二个版本允许用户指定一个仿函数作为比较的标准。

    STL的sort()算法,数据量大时采用Quick Sort,分段递归排序,一旦分段后的数据量小于某个门槛,为避免Quick Sort的递归调用带来过大的额外负荷,就改用Insertion Sort。如果递归层次过深,还会改用Heap Sort。

    Insertion Sort是《算法导论》一开始就讨论的算法。它的基本原理是:将初始序列的第一个元素作为一个有序序列,然后将剩下的N-1个元素按关键字大小依次插入序列,并一直保持有序。这个算法的复杂度为O(N^2),最好情况下时间复杂度为O(N)。在数据量很少时,尤其还是在序列“几近排序但尚未完成”时,有着很不错的效果。

    Insertion Sort
    
        // 默认以渐增方式排序
        template <class RandomAccessIterator>
        void __insertion_sort(RandomAccessIterator first,
            RandomAccessIterator last)
        {
            if (first == last) return;
                    // --- insertion sort 外循环 ---
            for (RandomAccessIterator i = first + 1; i != last; ++i)
                __linear_insert(first, i, value_type(first));
            // 以上,[first,i) 形成一个子区间
        }
    
        template <class RandomAccessIterator, class T>
        inline void __linear_insert(RandomAccessIterator first,
            RandomAccessIterator last, T*)
        {
            T value = *last;      // 记录尾元素
            if (value < *first){      // 尾比头还小 (注意,头端必为最小元素)
                copy_backward(first, last, last + 1);    // 将整个区间向右移一个位置
                *first = value;      // 令头元素等于原先的尾元素值
            }
            else    // 尾不小于头
                __unguarded_linear_insert(last, value);
        }
    
        template <class RandomAccessIterator, class T>
        void __unguarded_linear_insert(RandomAccessIterator last, T value)
        {
            RandomAccessIterator next = last;
            --next;
    
            // --- insertion sort 内循环 ---
            // 注意,一旦不再出现逆转对(inversion),循环就可以结束了
            while (value < *next){    // 逆转对(inversion)存在
                *last = *next;        // 调整
                last = next;        // 调整迭代器    
                --next;            // 左移一个位置
            }
            *last = value;            // value 的正确落脚处
        }

    上述函数之所以命名为unguarded_x是因为,一般的Insertion Sort在内循环原本需要做两次判断,判断是否相邻两元素是”逆转对“,同时也判断循环的行进是否超过边界。但由于上述所示的源代码会导致最小值必然在内循环子区间的边缘,所以两个判断可合为一个判断,所以称为unguarded_。省下一个判断操作,在大数据量的情况下,影响还是可观的。

    Quick Sort是目前已知最快的排序法,平均复杂度为O(NlogN),可是最坏情况下将达O(N^2)。
    Quick Sort算法可以叙述如下。假设S代表将被处理的序列:
    1. 如果S的元素个数为0或1,结束。
    2. 取S中的任何一个元素,当做枢轴(pivot) v。
    3. 将S分割为L、R两段,使L内的每一个元素都小于或等于v,R内的每一个元素都大于或等于v。
    4. 对L、R递归执行Quick Sort。

    Median-of-Three(三点中值)
    因为任何元素都可以当做枢轴(pivot),为了避免元素输入时不够随机带来的恶化效应,最理想最稳当的方式就是取整个序列的投、尾、中央三个元素的中值(median)作为枢轴。这种做法称为median-of-three partitioning。

    Quick Sort
    
        // 返回 a,b,c之居中者
        template <class T>
        inline const T& __median(const T& a, const T& b, const T& c)
        {
            if (a < b)
                if (b < c)        // a < b < c
                    return b;
                else if (a < c)    // a < b, b >= c, a < c  -->     a < b <= c
                    return c;
                else            // a < b, b >= c, a >= c    -->     c <= a < b
                    return a;
            else if (a < c)        // c > a >= b
                return a;
            else if (b < c)        // a >= b, a >= c, b < c    -->   b < c <= a
                return c;
            else                // a >= b, a >= c, b >= c    -->      c<= b <= a
                return b;        
        }

    Partitioning(分割)
    分割方法有很多,以下叙述既简单又有良好成效的做法。令first向尾移动,last向头移动。当*first大于或等于pivot时停下来,当*last小于或等于pivot时也停下来,然后检验两个迭代器是否交错。未交错则元素互相,然后各自调整一个位置,再继续相同行为。若交错,则以此时first为轴将序列分为左右两半,左边值都小于或等于pivot,右边都大于等于pivot

    Partitioning
    
        template <class RandomAccessIterator, class T>
        RandomAccessIterator __unguarded_partition(
                                        RandomAccessIterator first,
                                        RandomAccessIterator last,
                                        T pivot)
        {
            while(true){
                while (*first < pivot) ++first;    // first 找到 >= pivot的元素就停
                --last;
    
                while (pivot < *last) --last;    // last 找到 <=pivot
    
                if (!(first < last)) return first;    // 交错,结束循环    
            //    else
                iter_swap(first,last);                // 大小值交换
                ++first;                            // 调整
            }
        }

    Heap Sort:partial_sort(),即heap不断将头取出.

    Heap Sort
    
        // paitial_sort的任务是找出middle - first个最小元素。
        template <class RandomAccessIterator>
        inline void partial_sort(RandomAccessIterator first,
                                 RandomAccessIterator middle,
                                 RandomAccessIterator last)
        {
            __partial_sort(first, middle, last, value_type(first));
        }
        template <class RandomAccessIterator,class T>
        inline void __partial_sort(RandomAccessIterator first,
                                RandomAccessIterator middle,
                                RandomAccessIterator last, T*)
        {
            make_heap(first, middle); // 默认是max-heap,即root是最大的
            for (RandomAccessIterator i = middle; i < last; ++i)
                if (*i < *first)
                    __pop_heap(first, middle, i, T(*i), distance_type(first));
            sort_heap(first,middle);
        }

    IntroSort
    不当的枢轴选择,导致不当的分割,导致Quick Sort恶化为O(N^2)。David R. Musser于1996年提出一种混合式排序算法,Introspective Sorting。其行为在大部分情况下几乎与 median-of-3 Quick Sort完全相同。但是当分割行为(partitioning)有恶化为二次行为倾向时,能自我侦测,转而改用Heap Sort,使效率维持在O(NlogN),又比一开始就使用Heap Sort来得好。大部分STL的sort内部其实就是用的IntroSort。

        template <class RandomAccessIterator>
        inline void sort(RandomAccessIterator first,
                        RandomAccessIterator last)
        {
            if (first != last){
                __introsort_loop(first, last, value_type(first), __lg(last-first)*2);
                __final_insertion_sort(first,last);
            }
    
        }
        // __lg()用来控制分割恶化的情况
        // 找出2^k <= n 的最大值,例:n=7得k=2; n=20得k=4
        template<class Size>
        inline Size __lg(Size n)
        {
            Size k;
            for (k = 0; n > 1; n >>= 1) 
                ++k;
            return k;
        }
            // 当元素个数为40时,__introsort_loop的最后一个参数
            // 即__lg(last-first)*2是5*2,意思是最多允许分割10层。
    
        const int  __stl_threshold = 16;
    
        template <class RandomAccessIterator, class T, class Size>
        void __introsort_loop(RandomAccessIterator first,
                        RandomAccessIterator last, T*, 
                        Size depth_limit)
        {
            while (last - first > __stl_threshold){        // > 16
                if (depth_limit == 0){                    // 至此,分割恶化
                    partial_sort(first, last, last);    // 改用 heapsort
                    return;
                }
    
                --depth_limit;
                // 以下是 median-of-3 partition,选择一个够好的枢轴并决定分割点
                // 分割点将落在迭代器cut身上
                RandomAccessIterator cut = __unguarded_partition
                    (first, last, T(__median(*first,
                                             *(first + (last - first)/2),
                                            *(last - 1))));
    
                // 对右半段递归进行sort
                __introsort_loop(cut,last,value_type(first), depth_limit);
    
                last = cut;
                // 现在回到while循环中,准备对左半段递归进行sort
                // 这种写法可读性较差,效率也并没有比较好
            }
        }

    函数一开始就判断序列大小,通过个数检验之后,再检测分割层次,若分割层次超过指定值,就改用partial_sort(),即Heap sort。都通过了这些校验之后,便进入与Quick Sort完全相同的程序。

    当__introsort_loop()结束,[first,last)内有多个“元素个数少于或等于”16的子序列,每个序列有相当程序的排序,但尚未完全排序(因为元素个数一旦小于 __stl_threshold,就被中止了)。回到母函数,再进入__final_insertion_sort():

    template <class RandomAccessIterator>
        void __final_insertion_sort(RandomAccessIterator first,
            RandomAccessIterator last)
        {
            if (last - first > __stl_threshold){   
                // > 16
                // 一、[first,first+16)进行插入排序
                // 二、调用__unguarded_insertion_sort,实质是直接进入插入排序内循环,
                //       *参见Insertion sort 源码
                __insertion_sort(first,first + __stl_threshold);
                __unguarded_insertion_sort(first + __stl_threshold, last);
            }
            else
                __insertion_sort(first, last);
        }
    
        template <class RandomAccessIterator>
        inline void __unguarded_insertion_sort(RandomAccessIterator first,
            RandomAccessIterator last)
        {
            __unguarded_insertion_sort_aux(first, last, value_type(first));
        }
    
        template <class RandomAccessIterator, class T>
    
        void __unguarded_insertion_sort_aux(RandomAccessIterator first,
            RandomAccessIterator last,
            T*)
        {
            for (RandomAccessIterator i = first; i != last; ++i)
                __unguarded_linear_insert(i, T(*i));
        }
    展开全文
  • C++STL源码分析 SGI版

    2016-10-30 09:58:25
    这个是SGI,比PJ版难,大家可以先分析PJ版的,再来挑战这个
  • STL源码剖析!无水印!
  • 按理说应该先读其他书,敲下少说上万行代码再来看stl,特别是应该先用再看实现,可我发现那样效率不高,不如跟着代码,学与用结合。 学习编程最重要的一个步骤是实践,其次是思考。希望阅读中自己牢记...

    前言

    现在的工作我不是很喜欢,就是在造轮子,而且预计以维护为主,造轮子为辅。既然涉及C++,我是准备把经典书籍都看一遍,前几年工作内容不同,使用语言也不同,也就看点皮毛《C++ Primer》都没看完。

    按理说应该先读其他书,敲下少说上万行代码再来看stl,特别是应该先用再看实现,可我发现那样效率不高,不如跟着代码,学与用结合。

    学习编程最重要的一个步骤是实践,其次是思考。希望阅读中自己牢记这句话。

    此次分析以侯捷老师的《STL 源码剖析》为根本,自己也不打算超出书本范围。

    备注:该篇需要在分析完之后修改完善

    STL概论

    STL是放之四海而皆准(基于泛型编程)的轮子(库)。

    STL 六大组件:
    STL 六大组件的交互关系

    STL 六大组件的交互关系:
    Container 透过 Allocator 取得数据储存空间,Algorithm 透过 Iterator 存取 Container 内容,Functor 可以协助 Algorithm 完 成不同的策略变化,Adapter 可以修饰或套接 Functor

    大概就是这么回事:
    王老板有一大片地,想用来种植各种农作物、水产品或者干脆盖房子。
    老王找到可靠的土地管理人员(Allocator)对土地规划分配。
    老王雇了农民、渔民、建筑师(Container)来干活。
    老王想提高收益,于是请来了各类专家(Algorithm)如农业学家、建筑设计师来指导完成工作。
    术业有专攻,农业学家可能需要地质、气象学家给出的策略(Functor)。
    无论专家还是老王,他们关心的是具体的东西,譬如是小麦还是玉米,是鱼虾还是螃蟹。农民、渔民提供一个库存或账本,这样无论是专家还是老王不用时刻跟农民、渔民打交道,直接访问他们的库存或账本(Iterator)。
    个体户、无业游民,要么看到了商机,要么出于无奈他们选择了从事农业劳动。聪明的他们发现种植按照农民、渔夫的套路来就行了,利润独立结算。这样他们就成了伪农民、伪渔夫,外界不知道他们的真实情况,还以为是新新人类(Adapter),他们自己当然就可以随时换汤不换药。

    stl_config.h

    一群脑洞的专家提出了许多语言特性,一群苦逼的编译器开发人员天天加班,改不完的bug,新增的鬼畜。无奈之下决定,先完成基本的功能,特别偏僻的功能就先放一放,老子没空啊!!!
    于是stl_config.h对编译器说,你能就你上,否则就拉倒。

    1.9.1代码我在XCode上测试,基本都不通,根据错误稍微调调就好了。模板那些偏僻的特性啊,最好少用吧。。
    1.9.4-1.9.6 主要讲了操作符重载,还是值得一读的。


    展开全文
  • STL编程中, 容器就是我们经常会用到的, 容器分为序列容器和关联式容器. 而这一篇我们就分析序列容器之一vector. 关于用过vector三的人肯定对其一点都不陌生, vector基本能够支持任何类型的对象, 同时是一个可以...
  • C++STL源码分析

    2014-05-20 23:06:43
    好资料,都懂的!学习STL必读提高书籍之一,有用
  • STL源码分析:Adapters

    2019-09-27 22:04:13
    配接器在STL组件的灵活组合运用功能上,扮演着轴承、转换器的角色。Adaper这个概念,事实上是一种设计模式。在《设计模式》中adapter定义如下:将一个class的接口转换为另一个class的接口,使原本因接口不兼容而不能...
  • 上一节我们分析了空间配置器对new的配置, 而STL将空间配置器分为了两级, 第一级是直接调用malloc分配空间, 调用free释放空间, 第二级三就是建立一个内存池, 小于128字节的申请都直接在内存池申请, 不直接调用malloc...
  • 2. 源码分析 以G2.9为例,以下是map的部分源码实现: template <class Key, class T, class Compare = less<Key>, class Alloc = alloc> class map { public: typedef Key key_type; ...
  • STL源码刨析

    千次阅读 2021-11-20 18:26:16
    1. STL概述 STL起源: 为的就是复用性的提升,减少人力资源的浪费,建立了数据结构与算法的一套标准。 STL所实现的、是依据泛型思维架设起来的一个概念结构。这个以抽象概念〔 abstract concepts)为主体而非以实际...
  • 运用STL时的几个最重要的观念: 1.所谓使用STL,就是去扩充它。 2.STL的算法和容器是独立分离的。 3.无须继承。 4.抽象化并不意味效率低。 STL所实现的,是依据泛型思维架设起来的一个概念结构。这个以抽象...
  • 源代码来自sgi-2.91版本stl_hash_map.h 文章目录unordered_map总述unordered_map类hash_map构造函数operator[]重载size()begin()、end()find()count()insert()erase() unordered_map总述 先了解hash表 (1)底层实现...
  • STL 源码剖析.pdf

    2018-08-28 00:11:00
    STL 源码剖析 作者: 侯捷 出版社: 华中科技大学出版社 出版年: 2002-6 页数: 493 定价: 68.00元 装帧: 平装 ISBN: 9787560926995
  • 前言 hash_map是以hashtable为底层的配接器, 他与map的功能基本一样, 只是map是有序的将键值插入, 而hash_...#ifndef __STL_LIMITED_DEFAULT_TEMPLATES template &amp;lt;class Key, class T, class HashFcn = ...
  • STL 源码分析之string(一)基础篇

    千次阅读 2017-10-20 16:32:17
    STL源码下载:https://www.sgi.com/tech/stl/download.html其中string类需要在...源码分析:typedef basic_string<char> string;string类是由模板类basic_string_String_base类template , class _Alloc> class _Strin
  • 1. 概念 set是一种关联式容器。...2. 源码分析 以G2.9为例,以下为set的部分源码实现: template<class Key, class Compare = less<Key>, class Alloc = alloc> class set { public: //typedefs t
  • STL源码分析 stack容器

    2020-12-16 21:57:26
    文章目录stack总述stack类 stack总述 先了解deque容器->deque (1)因为deque容器双向push和pop的特性,所以stack的底层实现可以完全由deque代替...#ifndef __STL_LIMITED_DEFAULT_TEMPLATES template <class T,
  • 侯捷_STL源码分析_STLsource(JJhou)
  • STL源码分析之pair

    2020-01-15 09:52:53
    pair主要是用于map中,它的实现代码很...#ifndef __SGI_STL_INTERNAL_PAIR_H #define __SGI_STL_INTERNAL_PAIR_H __STL_BEGIN_NAMESPACE template <class T1, class T2> struct pair { typedef T1 first_t...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 15,041
精华内容 6,016
关键字:

stl源码分析

友情链接: taskschedulerview-x64.zip