精华内容
下载资源
问答
  • 2017-06-30 16:45:24

    序列式容器

    • 容器的概观和分类

      容器,致物之所也。研究数据的特定排列方式,以利于搜索或排序或其他特殊目的的,这一门学科就称为数据结构,几乎可以说,任何特定的数据结构都是实现某一算法。根据数据在容器中排列的特性,可以分为序列式和关联式两种。

      这里写图片描述

    • 序列式容器

      C++本身提供了一个序列式容器array,STL提供额外的其他容器,下面一一简单介绍关键细节。

    • vector

      我们不必害怕内存不够而先使用一个巨大的array,我们可以尽情的用vector,吃多少用多少。vector的关键技术在于对内存的灵活配置以及重新配置时数据移动的效率。

    更多相关内容
  • STL源码剖析读书笔记

    2014-01-26 17:11:10
    STL经典著作的读书笔记。按章节写的,算是一份不错的总结吧
  • STL中,所有的元素都是存放在容器中,容器需要配置空间来储存这些数值,因此需要用到空间配置器。 概览 SGI的空间配置器 SGI标准的空间配置器是allocator, 只是对基层内存配置/释放行为(对运算符new/delete)...

    空间配置器 allocator

    在STL中,所有的元素都是存放在容器中,容器需要配置空间来储存这些数值,因此需要用到空间配置器。

    概览

    • SGI的空间配置器
      • SGI标准的空间配置器是allocator, 只是对基层内存配置/释放行为(对运算符new/delete)进行了一层薄薄的封装,没有考虑到效率上的优化。
      • SGI特殊的空间配置器是alloc,
        SGI以malloc()和free()完成内存的配置和释放。考虑到小型区块可能造成内存破碎问题,SGI设计了双层级配置器。第一层直接用malloc和free,第二级配置器视情况采用不同策略。如果配置区别大于128bytes,选用第一级配置器;当小于128bytes时,采用复杂的memory pool的整理方式。是否同时开放第二级配置器,取决于__USE_MALLOC是否被定义。

    精细分工

    • STL Allocator的精细分工
      stl_construct.h
      内存配置:allocate();
      内存释放前进行对象的析构:destroy(),调用析构函数;
      stl_alloc.h
      内存配置后进行对象的构造:construct(),placement new调用构造函数;
      内存释放: deallocate();
      stl_uninitialized.h
      定义一些全域函式,用来填充(fill)或者复制(copy)大块的内存内容。

    • stl_construct.h
      construct()接收一个指针和一个初始值value,用途是将初值设定到指针所指的空间上
      destroy有两个版本,版本1接受一个指针,准备将该指针所指之物析构掉;版本2是接收first和last两个迭代器,将[first,last)范围内所有对象析构掉

    • std::alloc(设置配置器)
      SGI用malloc和free这2个C函数代替完成内存的申请和释放。考虑到内存碎片问题,SGI设计了两级配置器,第一级直接使用malloc和free,包括了内存不足处理机制,需要调用者自己提供。第二级判断配置区超过128字节,调用第一级配置器。小于128字节,采用内存池管理
      这里写图片描述
      这里写图片描述

    双层级配置器

    • 第一级配置器
      __malloc_alloc_template
      SGI第一级配置器的allocate()和realloc()使用malloc与free来配置和释放内存。调用不成功后,会调用oom_malloc()和oom_realloc()。后两个函数都有内循环,不断调用“内存不足处理例程”,期待在某次调用后获得足够内存而圆满完成任务。设定“内存不足处理例程”是客端的责任。

    • 第二级配置器
      __default_alloc_template
      当区块小于128byte,交由第二级配置器处理。用内存池(memory pool)来管理。也叫次层配置(sub-allocation)

      • 实现方式

        • 每次配置一大块内存,并维护对应的自由链表
        • 如果下次有相同大小的内存需求,就从free-list中拨出
        • 如果客端释放小额区块,就由配置器回收到free-list中
        • SGI第二级配置器会主动将任何小额区块的内存需求量上调至8的倍数。它维护16个free-lists,各自管理大小分别为8,16,24,32,…,128byte的小额区块。
        • 节点结构
          //利用union的性质使得链表既是指针又是实际区块
          union obj
          {
              union obj * free_list_link;
              char client_data[1];       //柔性数组
          };
      • 内存池
        chunk_alloc的工作:从内存池中取空间给free-list使用。

        if(内存池水量足够)
            直接调出20个区块给free list
        else if(内存池水量还足够提供至少1个区块)
            调出实际能够供应的区块
        else
            利用malloc()向堆heap中配置内存,为内存池注入源头活水以应付需求。一般申请为需求量的两倍,再加上随着配置次数增加而越来越大的附加量
            if(heap的空间也不够)
                malloc()失败,调用第一级配置器中的out of memory处理机制,或许有机会释放其内存拿来此处使用。如果可以就成功,否则发出bad_alloc异常。

    相关问题

    • STL里面空间分配是怎么样的?
      STL中用allocator类来实现空间分配,有一级配置器二级配置器,根据一个环境组态来确定使用哪一级的配置器。SGI STL将alloc设置为第二级配置器。

    • 如果用让你写一个STL的空间配置器,这个配置器需要经常分配大量的小内存,但大量的分配小内存会造成内存碎片,你会怎么解决这个问题?那如果用你实现的配置器分配的空间是怎么释放的?
      参考:可以说一些二级配置器是怎么实现的,可以参照STL特有的空间配置器alloc的设计

      1. 针对于小内存的问题,可以像第二级配置器一样来实现,用内存池来管理。每次配置一大块内存,然后维护16个自由链表free-lists。每个链表会维护若干个小额区块,每个小额区块的大小是8的倍数。
      2. 如果自由链表里的小额区块不够了,利用chunk_alloc(size,num),从内存池中取空间给free-list使用(参考上面的内存池内容)
      3. 如果客端申请需求量小于128byte,会将申请的内存需求量上调至8的倍数,然后再查找对应的自由链表中的小额区块。如果大于128byte,就用第一级配置器的allocate()函数,直接用malloc来配置内存。
      4. 释放内存时,如果释放量小于128byte,配置器会将它归还到对应的自由链表中。如果大于128byte,就用第一级配置器的deallocate()函数,直接用free来释放内存。
    展开全文
  • STL源码剖析读书笔记3

    2017-06-12 21:29:12
    SGI STL的每一容器都已经指定其缺省的空间配置器为alloc。例如: vector的声明: template,class Alloc = alloc> //缺省 class vector {...}; 我们所习惯的new/delete内存配置:class Foo{...}; Foo* pf = ...

    SGI空间配置器

    SGI STL的每一容器都已经指定其缺省的空间配置器为alloc。例如:
    vector的声明:
    template<class T,class Alloc = alloc> //缺省
    class vector {...};

    我们所习惯的new/delete内存配置:

    class Foo{...};
    Foo* pf = new Foo; //配置内存然后分配对象
    delete pf;//将对象析构然后释放
    这其中包含两个阶段,调用::operator new配置内存,Foo::Foo()构造对象

    为了精密分工,STL allocator决定将这俩个阶段操作分开来,alloc::allocate()/alloc::deallocate()/:construct()/:destory()/。并将配置器定义与memory头文件内。

    这里写图片描述

    construct

    上述construct()接受一个指针p和一个value,该函数的用途就是将初值设定到指定的空间上去,用C++中的placement new来完成。

    destroy

    两个版本,第一个版本接受一个指针,然后将该指针指向之物析构掉。第二个版本接受范围的迭代器,将[first,last)范围内的所有对象全部析构掉,这里先用value_type()获得迭代器所指对象的类别,再用type_traits《T》判断该类别的析构函数是否无关痛痒。

    这里写图片描述

    当operator new申请一个内存失败的时候,它会进行如下的处理步骤:
    1、如果存在客户指定的处理函数,则调用处理函数(new_handler),如果不存在则抛出一个异常。
    2、继续申请内存分配请求。
    3、判断申请内存是否成功,如果成功则返回内存指针,如果失败转向处理步骤1
    一个设计良好的new_handler必须做以下事情:
    1、删除其它无用的内存,使系统具有可以更多的内存可以使用,为下一步的内存申请作准备。
    实现此策略的办法是:程序一开始执行就分配一大块内存,当new_handler被调用时,将它们释放还给程序使用。
    2、设置另外一个new_handler。
    如果当前的new_handler不能够做到更多的内存申请操作,或者它知道另外一个new_handler可以做到,则可以调用set_new_handler函数设置另外一个new_handler,这样在operator new下一次调用的时候,可以使用这个新的new_handler。
    3、卸载new_handler,使operator new在下一次调用的时候,因为new_handler为空抛出内存申请异常。
    4、new_handler抛出自定义的异常
    5、不再返回,调用abort或者exit退出程序

    一二级配置器的包装接口与运用方式

    第一级配置器源码剖析

    这里写图片描述
    这里写图片描述

    展开全文
  • STL源码剖析读书笔记5

    2017-06-21 16:10:05
    重新填充Refill_Freelist 在allocate()分配内存发现freelist没有可用内存时,需要调用refill函数重新填充freelist,这些新的空间将从内存池中获得,一次分配20个节点或区块,当然如果内存池内存不足很有可能区块会...

    重新填充Refill_Freelist

    在allocate()分配内存发现freelist没有可用内存时,需要调用refill函数重新填充freelist,这些新的空间将从内存池中获得,一次分配20个节点或区块,当然如果内存池内存不足很有可能区块会小于20个。

    //假设n已经上调至8的倍数
    template<bool threads,int inst>
    void* _default_alloc_template<threads,inst>::refill(size_t n){
          int nobjs = 20;
          char* chunk = chunk_alloc(n,nobjs);//nobjs传引用
          obj* volatile *my_free_list;
          if(1==nobjs) retrun(chunk);
          my_free_list = free_list + FREELIST_INDEX(n);
          obj* result;
          obj* current_obj, * next_obj;
          result = (obj*) chunk;//第一块给客端
          *my_free_list = next_obj = (obj*)(chunk+n);//剩下的串起来 
          for(int i=1;;i++){
              currnt_obj = next_obj;
                next_obj = (obj*)((char*)next_obj+n);
              if(nobj-1 == i){
                 currnt_obj->free_list_link = 0;
                 break;
              }else{
                 currnt_obj->free_list_link = next_obj;
               } 
          }
          return (result);
    }

    内存池取空间的CHUNK_ALLOC>

    chunk_alloc函数是以end_free-start_free来判断内存池是否还有可用内存,如果有则拨款20个nobjs,如若不足20但仍有超过一个需求大小的内存块,则把这些空间全部拨出去。这时候nobjs就变成了实际得到内存块。如果一个都无法配置,那么内存池将会调用malloc从heap上获取内存,内存量为需求量的2倍加上一个和配置次数成比例的附加量。举个例子:chunk_alloc(32,20),这是第一次内存池没有内存,便向heap申请32*40的内存,其中1个给客端,19个给free_list维护,剩下的留给自己。这时候chunk_alloc(64,20),内存池还有32*20/64,也就是10个可用内存块,1个给客端,9个给相应的freelist维护。自己空空如也了,下次在申请就是2倍加附加量了。万一山穷水尽了,heap也没了,那么就调用第一级配置器,虽然他也是malloc,但是他有out_of_memory机制可以释放其他内存拿来用,失败了大不了喊一句bad_alloc;

    这里写图片描述

    //内存池chunk_alloc的实现,模板省略了
    char* chunk_alloc(size_t size,int& nobjs){
          char* result;
          size_t total_bytes = size * nobjs;
          size_t  left_bytes = end_free - start_free;
          if(left_bytes >= total_bytes){
             //内存池完全够用
             result = start_free;
             start_free += total_bytes;
             return (result);
          }else if(left_bytes >= size){
                   nobjs = left_bytes / size ;
                   result = start_free;
                   start_free += nobjs * size;
                   return (result);
                }else{
                 //内存池一个区块的大小都无法提供
                  size_t bytes_to_get = 2 * total_bytes +                        ROUND_UP(heap_size>>4);
                  if(left_bytes >0){
                     //内存池还有一点零头,先配置给合适的free_list
                     obj* volatile* my_free_list = free_list + FREELIST_INDEX(left_bytes);
                     ((obj*) start_free) -> free_list_link = *my_free_list;
                     *my_free_list = (obj*) start_free;
                  }
                  //在heap上配置空间,用来补充内存池
                  start_free = (char*)malloc(byte_to_get);
                  if(0==start_free){
                    //heap空间失败,malloc()失败
                    int i;
                    obj* volatile* my_free_list,*p;
                    //我们检视手上的东西,找到适当大小的未用内存,适当即为区块要足够大。
                    for(i = size;i<=_MAX_BYTES;i += _ALLIN){
                        my_free_list = free_list + FREELIST_INDEX(i);
                        p = my_free_list;
                        if(0 != p){
                          //还有货,当然我们就拿1个区块
                           *my_free_list = p -> free_list_link;
                           start_free = (char*)p;
                             end_free = start_free + i;
                             //内存找到了,则递归重新配置修正nobjs
                           return (chunk_alloc(size,nobjs));
                        }
                    }
                    end_free = 0;
                    start_free = (char*)malloc_alloc::allocate(bytes_to_get);
                  }
                  heap_size += bytes_to_get;
                  end_free = start_free + bytes_to_get;
                  return (chunk_alloc(size,nobjs));
                 }
    }
    

    内存处理的基本工具

    这里写图片描述

    该函数会调用construct(&*(result + (i-first)),*i);如果你要实现一个容器的全区间构造函数,一般经过两个步骤,第一个配置内存空间,第二个调用copy();

    这里写图片描述

    该函数会调用construct(&*i,*i);

    这里写图片描述

    这里写图片描述

    这里面value_type()判断迭代器所指是否为POD类型。POD为plane old data,包含标量型或C 里的结构体类型,对于POD类型必然拥有copy/assignment/dtor,因此我有更高效的初值填写手法。否则采用最保险的做法。

    这里写图片描述

    展开全文
  • 而《STL源码剖析》这本书也是集精华于一体,深度探索了对于STL的各个部分。配合老师的视频食用极佳。 从这篇开始,我想根据视频和书籍的主要内容做一些整理以及一些理解部分的记录。因为视频部分和书籍部分不完全...
  • Traits编程技法 - STL源码门钥 1 value_type萃取   书本前面简单实现了一个list的迭代器,同时引出了一个问题:当我们需要使用迭代器所指的类型去声明一个变量或者判断迭代器类型和本身类型是否相等时该怎么办?...
  • 1、vector概述 vector是动态空间,随着元素的加入,它内部机制会自行扩充空间以容纳新元素。 vector的实现技术,关键在于其对大小的控制及重新配置时的数据移动效率。 2、vector的迭代器 vector的迭代器是普通...
  • 一、STL六大组件: 1、容器(containers):各种数据结构,如:vector、list、deque、set、map,主要用来存放数据。 2、算法(algorithms):各种常见算法,如:sort、search、copy、erase...... 3、迭代器(iterators)...
  • STL源码剖析(侯杰)——读书笔记

    千次阅读 2020-11-16 14:32:14
    文章目录STL源码剖析(侯杰)——读书笔记1. STL概论2.空间配置器SGI标准空间配置器, std::allocatorSGI特殊的空间配置器, std::alloc构造和析构 construct()和destroy()空间配置与释放3.迭代器概念与traits编程...
  • 关联式容器 5.1 树的导览 树由节点(nodes)和边(edges)组成。最上面是根,根下面是子节点,如果最多允许两个子节点,则称此树为二叉树(binary tree)。 5.1.1 二叉搜索树 二叉搜索树可提供对数时间的元素搜索和...
  • 迭代器的设计思维--STL设计理念 STL在设计的时候希望达到将数据结构和算法分离开来独立设计,最后再使用一点耦合剂来使它们联系起来。 这里举了一个容器、算法、迭代器的例子,就是find函数,对于不同类型的迭代器...
  • STL 源码剖析读书笔记

    千次阅读 多人点赞 2018-09-13 16:00:56
    可以详细地了解STL的底层实现机制,同时也可以对常用数据结构,C++内存管理拥有更深的理解。特别对于找工作的C++软件开发工程师帮助很大。 但个人觉得读这本书的过程中可以详略得当,有些只需要大概了解,有些则...
  • 第6章 算法 6.1 算法概观 算法,解决问题的方法。 质变算法,改变元素内容。拷贝(copy)、互换(swap),替换(replace) “非质变算法”,不改变元素的值。查找(find)、匹配(search)、计数(count) ...
  • 扮演一种“策略”角色,能让STL算法更灵活的演出。 7.2.1 unary_function 用来呈现一元函数的参数型别和返回值型别。 7.2.2 binary_function 用来呈现二元函数的第一参数型别,第二参数型别以及返回值型别。 7.3 ...
  • 空间配置器作为隐藏在一切组件背后的关键组件,是学习STL源码的重要内容。事实上allocator不应该称为空间配置器,而应该称为内存配置器。因为空间并不一定是内存,也可以是磁盘或者其他辅助存储介质。 //.h文件 #...
  • 第3章 迭代器概念与...3.4 Traits编程技法 - STL源码门钥 迭代器所指的物件的型别,称为该迭代器的value type。 所谓value type 是指迭代器所指对象的型别。 型别2:difference type ,用来表示两个迭代器之间...
  • STL源码剖析-读书笔记

    千次阅读 2019-08-01 16:24:54
    STL实现的是依据泛型思维架设起来的一个概念结构。这个以抽象概念为主体而非以实际类为主体的结构,形成严谨的接口标准。在此接口下,任何组件都有最大的独立体,并以所谓迭代器(iterator)胶合起来,或以所谓适配器...
  • 算法 算法可分为质变算法和非质变算法,质变算法改变操作对象的值,通常提供两个版本,一个直接改变操作对象值...使用SGI版STL数值算法需要包含头文件&lt;stl_numeric.h&gt; 1.1 accumulate template&l...
  • generic programming GP 泛型编程 object oriented OO 面向对象 C++ Standard Library C++标准库 ...Standard Template Library STL 标准模板库 ...C++标准库中有百分之八十左右都是由 STL组成的 ...建议阅读书籍...
  • STL的list事实上是一个双向链表,了解链表概念的应该明白,这种前后可移动的链表结构提供了非常灵活的操作性。 二、定义 2.1 节点形式   它的节点形式可以比较形象化地展示为下图的样子:   而具体的代码也很...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,001
精华内容 400
关键字:

stl源码剖析读书笔记