注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Leo

笑:胸怀,傲:实力,才能笑傲江湖。

 
 
 

日志

 
 

STL源码 学习笔记  

2017-05-30 11:10:18|  分类: 技术小白 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
一、STL 六大组件
1、容器:各种数据结构,如vector,list,deque,set,map。用来存放数据。
2、算法:各种常用的算法,如sort,search,copy,erase。
3、迭代器:扮演容器与算法之间的胶合剂,所谓的的“泛型指针”。
常用的几个:
template<class Category, class T, class Distance=ptrdiff_t, class Pointer =T*, class = Reference = T&>
struct itertor{
typedef Categor iterator_category;
typedef T     vaue_type;
typedef Distance difference_type;
typedef Pointer    pointer;
typedef reference reference;
};
(ptrdiff_t类型变量通常用来保存两个指针法操作的结果,标准库类型(library type)与size_t类型一样)
4、仿函数:行为类似函数,可作为算法的某种策略。
定义一个模板,然后实现一个函数,这个函数直接用operator来运算结果;
template<class T>
struct plus : public binary<T, T, T,>{
T oprtator()(const T& x, const T& y) const {return x - y};
可以定义一个int啥的:plus<int> leo_plus; leo_plus(3,5); 可以输出结果。
5、配接器:一种用来修饰容器或仿函数或迭代器接口的东西。
将一个class的接口转换为另外一个class的接口,使原本不兼容的接口得以兼容。
6、配置器:负责空间配置和管理。

二、空间配置器
二级配置器如果需要的空间大于128KB的,使用一级配置器,直接malloc。
如果小于128KB,那就使用二级配置器,二级配置器是一个内存池,一个大小为16的数组,每个数组都是一个指针,数组指针,然后指针指向一个内存链表。16个数组空间,从8,16,....到120,128。具体链表空间个数,根据自己的需要来定吧。如果用完了节点,就要重新申请空间来填充,默认是20个新节点大小。

三、容器
1、序列是容器
 容器

描述

优点

缺点

 vector1、和数组相似,数组是静态空间;2、vector是动态空间,加入元素时,内部机制会自行扩充空间;3、数据接口是线性连续空间;4、实际内存会比客户要求内存大,已被将来扩充,一般是两倍;5、删除前面的元素,后面的元素会像前移动;6、pop_backpush_back,表示是先进后出,单向开口;7、删除元素效率高到低:earse后面、earse前面、pop_back 内存合理利用,运用灵活,用多少申请多少; 需要动态扩充内存,配置新空间-移动数据-释放就空间,成本高。
 List1、每次插入和删除,就要配置一个元素空间,用多少申请多少;2、环状双向链表,只有一个指针;内存用多少申请多少,单独一个节点; 
 deque1、双向开口的连续线性空间,头尾都可以插入和删除;2、分段的连续的空间链接而成;3、迭代器类似map的,处理比较复杂,因为要找分开的连续的空间;3、缺省情况下,是以stack作为底部结构;1、允许于常数时间内对起头端进行元素的插入和移除;2、没用vector的容量观念,动态的分段的连续空间组合而成,随时可以新增一段新的空间链接起来。除非必要,尽可能使用vector而非deque,迭代器复杂耗时;
 stack1、单向数据结构,先进后出;2、允许移除、新增、取最顶端元素,但不能遍历;3、以list作为底部容器;  没有遍历元素的方法;
 queue1、一种先进先出的数据结构;2、默认以deque作为底部数据结构;3、可以指定list作为底部数据结构;  除了低端加入、顶端取出元素之外,没有任何其他方法获取其中节点;
 heap1、并不归于STL容器,是后台机制;2、可以将元素推入容器内,取出时按照优先级取出元素;3、内部用完全二叉树和数组来实现优先级高低排序,在插入元素时就需要排序; 优先级高的先出; 
 Priority
_queue
1、功能和queue相似,具有排序功能,优先级高的,排在前面;2、缺省情况下以vector作为容器,再加上heap的处理;
  
 slist 单向链表; 耗用空间小,某些操作更快; 相比list,很多功能就受限制;
2、关联式容器
 容器 说明
 set1、若有的元素都会根据元素的键值都会到自动排序;2、set的键值就是实值,实值就是键值;3、不允许两个相同的键值;
 map1、所有元素都会根据元素的键值自动排序;2、拥有实值和键值;3、不允许重复;
 multiset1、用法和set相同;2、允许键值重复;
 multimap1、用法和map相同;2、允许键值重复;
 hashtable1、可提供任何有名项的存取和删除;2、使用某种映射函数,将大数映射为小数,负责将某一元素映射为一个大小可接受之索引;3、元素被映射到相同位置是不可避免的;4、在算法这本书中,讲述可以采用插入,如果这个位置已经被占用了,那就继续循环找下一个可用空间;有的采用1次方,如果数组大,就可用2次方;5、如果找到的位置被占用,还可以在这个节点下,用链表连接,索引找到这个节点,再遍历这个节点下的队列,找到节点。
 hash_set1、set多半以RB-tree为底层;2、hash_sethashtable为底层;3、Set的元素自动排序,但是hash_set么有;4、键值就是实值;
 hash_map1、hashtable为底层;2、不能自动排序;
 hash_multiset1、mulitset一样;2、区别在于底层是用hashtable3、不自动排序;
 hash_multimap1、和mulitset一样;2、区别在于底层是用hashtable3、不自动排序;
   
四、算法
在书中讲到这章,不怎么能看进去,只看懂了一个说法:把一些函数写成一个模板,然后可以听过定义来实现自己的功能和运算。
  评论这张
 
阅读(59)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018