佛山营销网站建设,wordpress请求超时,外贸公司是私企还是国企,室内装修工人培训学校STL标准库与泛型编程#xff08;侯捷#xff09;
本文是学习笔记#xff0c;仅供个人学习使用。如有侵权#xff0c;请联系删除。
参考链接
Youbute: 侯捷-STL标准库与泛型编程
B站: 侯捷 - STL
Github:STL源码剖析中源码 https://github.com/SilverMaple/STLSourceCo…STL标准库与泛型编程侯捷
本文是学习笔记仅供个人学习使用。如有侵权请联系删除。
参考链接
Youbute: 侯捷-STL标准库与泛型编程
B站: 侯捷 - STL
Github:STL源码剖析中源码 https://github.com/SilverMaple/STLSourceCodeNote/tree/master
Github:课程ppt和源码 https://github.com/ZachL1/Bilibili-plus
下面是第二讲的部分笔记C标准库体系结构与内核分析第二讲
主要介绍分配器allocator还有容器list的底层实现讨论iterator traits的设计 文章目录 STL标准库与泛型编程侯捷8 源代码之分布 VCGcc9 OOP 面向对象编程 vs GP 泛型编程10 技术基础操作符重载and模板泛化, 全特化, 偏特化11 分配器12 容器之间的实现关系与分类13 深度探索list上14 深度探索list下15 迭代器的设计原则和Iterator Traits的作用与设计后记 8 源代码之分布 VCGcc
学这门课应该有的基础
C基本语法
模板基础
数据结构和算法的基础
9 OOP 面向对象编程 vs GP 泛型编程
面向对象想要把data和method关联在一起比如list类内部实现sort函数。 泛型编程想要把data和method分开来比如vector和deque类没有实现sort函数而是调用algorithm里面的sort函数两者分开来。 10 技术基础操作符重载and模板泛化, 全特化, 偏特化
这部分在侯捷老师的面向对象课程里有详细的介绍请参考笔者的笔记里面含有课程的视频链接。
C面向对象高级编程侯捷笔记1
C面向对象高级编程侯捷笔记2
C程序设计兼谈对象模型侯捷笔记
这里补充type_traits里面用到的特化specialization的知识
泛化指的是用模板特化指的是指定模板到具体的类型。下面的代码中__STL_TEMPLATE_NULL指的是 template 这种类型表示空模板。
//type_traits.h文件
// 泛化
template class _Tp
struct __type_traits { typedef __true_type this_dummy_member_must_be_first; typedef __false_type has_trivial_default_constructor;typedef __false_type has_trivial_copy_constructor;typedef __false_type has_trivial_assignment_operator;typedef __false_type has_trivial_destructor;typedef __false_type is_POD_type;
};
// 特化
__STL_TEMPLATE_NULL struct __type_traitsint {typedef __true_type has_trivial_default_constructor;typedef __true_type has_trivial_copy_constructor;typedef __true_type has_trivial_assignment_operator;typedef __true_type has_trivial_destructor;typedef __true_type is_POD_type;
};__STL_TEMPLATE_NULL struct __type_traitsunsigned int {typedef __true_type has_trivial_default_constructor;typedef __true_type has_trivial_copy_constructor;typedef __true_type has_trivial_assignment_operator;typedef __true_type has_trivial_destructor;typedef __true_type is_POD_type;
};下图中的allocator这个类也是用到了泛化和特化比如当allocator指定的是void类型的时候会调用特化版本的代码。 偏特化有多个模板参数只指定部分个参数为特定类型。比如下图中的vector的类型T指定为bool而后面的Alloc分配器没有指定类型这就是一种偏特化。是一种个数的偏特化。
另外下图中iterator_traits中也用到了偏特化只不过这里是对指针类型的一个偏特化如果传入的是T*会有一种处理方式。这种偏特化是范围的偏特化指的是从T类型范围缩到T *指针类型。 11 分配器
分配器 allocators
先谈operator new() 和malloc()
malloc的内存实际分配情况
下图中的内存分配蓝色是块是实际我们需要malloc给我们分配的空间灰色的块是debug mode需要添加的内存空间上下两个红色的块是cookie它记录分配内存的大小《深度探索c对象模型》书上称为记录元素的大小这个指的是delete时该delete多大的内存空间即delete掉的数组维度大小绿色的部分指的是为了内存大小的对齐。 STL对allocator的使用 VC6编译器所附的标准库
allocator分配内存的时候调用operator new而operator new调用c语言的malloc。
而释放内存的时候调用operator delete而operator delete调用c语言的free。 测试分配512个int型数据需要指定分配的大小释放时也要指定大小
// VC的allocate第二个参数没有默认值需要自己给定任意值都行
int* p allocatorint().allocate(512, (int *)0); // allocatorint()是一个临时对象
allocatorint().deallocate(p, 512);BC5编译器所附的标准库对allocator的使用
_RWSTD_COMPLEX_DEFAULT(a)就是a所以可以看到下面的分配器用的就是allocator 那么BC5编译器对于allocator的内部设计呢分配内存和回收内存用的还是operator new和operator delete底部还是用c语言的malloc和free完成和VC6的实现别无二致。 接着示范BC5分配器的使用
测试分配512个int型数据需要指定分配的大小释放时也要指定大小
// BC的allocate第二个参数有默认值为0
int* p allocatorint().allocate(512); // allocatorint()是一个临时对象
allocatorint().deallocate(p, 512);GNU CG 2.9版本所附的标准库
分配内存和回收内存用的还是operator new和operator delete底部还是用c语言的malloc和free实现和上面相同。
参见右下角的说明这个分配器并没有被SGI STL header引入即没有被使用。 那GNU C2.9对allocator的使用是怎么样的呢
它用的是一个名字叫做alloc的分配器如下图所示。 G2.9 alloc的实现如下图所示共有16条链表每一条链表负责特定大小的区块编号为#0的链表负责大小为8B的内存块编号为#1的链表负责大小为8 x 2 16B的内存块编号为#3的链表负责大小为8 x 3 24B的内存块…以此类推每次增加8B。每一条链表都是一次用malloc分配的一大块内存带cookie然后切分成小的标准块不带cookie当容器需要内存的时候alloc就会按照需要的大小变成8B的倍数在链表中查找进行分配这样实现在分配小块的时候就不需要存储cookie的开销了。 G4.9所附的标准库它的分配器实现
名字叫做new_allocator, 这个4.9版本默认又不再使用alloc分配器而是继续调用operator new 和operator delete。 G4.9所附的标准库中的__pool_alloc就是G2.9版本的alloc分配器 如果想要使用这个分配器语法是什么呢
vectorstring, __gnu_cxx::__pool_allocstring vec;// __gnu_cxx是一个命名空间12 容器之间的实现关系与分类
容器结构与分类
下图中缩进的函数下图中的rb_tree红黑树下面有4个set,map,multiset,multimap缩进这表示下面四个和rb_tree是衍生关系复合composition关系has-a拿set举例表示set里面有has a1个rb_tree做底部拿heap举例表示heap里面有一个vector做底部拿priority_queue举例它是heap的缩进表示priority_queue里面有一个heap作为底部等等。 13 深度探索list上
容器list
容器list是双向链表底部实现是环状双向链表
下面是以GNU C2.9版本进行介绍
list内部除了存data之外还要存一个前向指针prev和一个后向指针next。
list的iterator当迭代器的时候是从一个节点走到下一个节点是通过访问next指针实现的。
templateclass T
struct __list_node {// 设计不理想后面需要类型转型typedef void* pointer; // 这里__list_node中竟然有一种指向void的指针而不是指向自己类型的指针void_pointer prev;void_pointer next;T data;
};templateclass T, class Alloc alloc
class list {
protected:typedef __list_nodeT list_node;
public:typdef list_node* link_node;typedef __list_iteratorT, T, T* iterator;
protected:link_type node;
...
};templateclass T, class Ref, class Ptr
struct __list_iterator {typedef T value_type;typedef Ptr pointer;typedef Ref reference;
...
};list’s iterator
下面看list的迭代器
__list_iterator 这个类中主要有两部分一部分是一堆typedef另一部分是操作符的重载如下图所示。 看迭代器iterator迭代器的操作
操作有两种一种是ite另一种是ite分别是前置(prefix)和后置(postfix)
先看prefix form通过取出next指针指向链表的下一个节点实现迭代器的操作。
self
operator() // 操作符重载
{// node是一个指向结构体__list_node的指针// 取出结构体里面的成员next指针node (link_type)((*node).next); // link_type是指针类型return *this;
}
// 结构体如下所示
templateclass T
struct __list_node {typedef void* pointer; void_pointer prev;void_pointer next;T data;
};再看postfix form用一个int参数operator(int) 表示后,当使用后置递增符号如ite时意味你想要递增迭代器但在递增之前返回其先前的值。
self
operator(int) //操作符重载
{self tmp *this; // 1.记录原值*this; // 2.前进一个位置//整个操作 *this 的结果是递增迭代器并返回递增后的迭代器的引用return tmp; // 3.返回原来的值
}这里的 self tmp *this;没有调用operator*这个操作而是调用拷贝构造的函数把后面*this解释为拷贝构造的参数
__list_iterator(const iterator x): node(x.node) {}再看这里的第2步*this;它也没有调用operator* 这个操作而是因为在前调用前置操作进行node指向next指针实现真正的迭代器前进这里的*this被解释为operator的参数。
*this 指向的是链表节点通过 *this 可以使得链表迭代器前进到下一个节点。 templateclass T,class Ref,class Ptr
struct __list_iterator {typedef __list_iteratorT,T,T* iterator;typedef __list_iteratorT,Ref,Ptr self;typedef bidirectional_iterator_tag iterator_category;typedef T value_type;typedef Ptr pointer;typedef Ref reference;typedef __list_nodeT* link_type;typedef size_t size_type;typedef ptrdiff_t difference_type;link_type node; //迭代器内部需要一个普通指针指向list的节点//构造函数__list_iterator(link_type x):node(x) {}__list_iterator() {}__list_iterator(const iterator x):node(x.node) {}reference operator*() const { return (*node).data;}pointer operator-() const {return (operator*());}//前向迭代器self operator(){ // 前置itenode (link_type)((*node).next);return *this;}self operator(int){ // 后置iteself tmp *this;*this;return tmp;}//后向迭代器self operator--(){ // 前置--itenode(link_type)((*node).prev);return *this;}self operator--(int){ // 后置ite--self tmp *this;--*this;return tmp;}
};这里的代码参考https://www.cnblogs.com/ybf-yyj/p/9843391.html
14 深度探索list下
GNU C2.9版本和GNU C 4.9版本关于list中iterator的设计差别
G2.9中iterator需要传三个模板参数T, T, T*而G4.9中仅需要传一个模板参数 G2.9中list的结构 G4.9中list的结构继承关系更加复杂 15 迭代器的设计原则和Iterator Traits的作用与设计
Iterator需要遵循的原则
看一下rotate函数它的参数里调用std::__iterator_category里面返回iterator_category这是iterator的一个属性下面图还有另外两个属性difference_type和value_type,这里共涉及三个associated types相关的类型另外还有两种分别是reference和pointer。也就是说共有5种associated types。
算法algorithm模块和容器container彼此独立中间需要迭代器iterator进行交流 iterator必须提供的5种associated types刚才上面介绍过如下图所示iterator_category, value_type, pointer, reference, difference_type。
difference指的是距离 一个容器中两个iterator的距离 为什么需要traits指针也被看作是一种退化的iterator但指针并不是一个类自然无法在类中定义上述的5种associated types。
traits机制必须有能力分辨它所获得的iterator是class iterator T还是native pointer to Tnative pointer原生指针指的是non class(template) iterators它无法定义associated type iterator traits用来分离class iterator和non-class iterator 当想知道一个迭代器的value type是什么的时候不能直接I::value_type而是
iterator_traitsI::value_type这就涉及到iterator_traits的偏特化指针是范围上的偏特化前文讲过如果传入的是指针T*它就是调用上图中的2或者3直接定义T为value_type类型如果传入的是class iterator那就直接定义I::value_type为value_type。
完整的iterator_traits这里就全部列出了5个asscicated types以及偏特化处理传入的是指针的情况 后面还有各种类型的traits比如type traits, char traits, allocator traits, pointer traits, array traits等等
后记
这是系列笔记连载会继续更新。
