侧边栏壁纸
博主头像
lmg博主等级

  • 累计撰写 55 篇文章
  • 累计创建 6 个标签
  • 累计收到 2 条评论
标签搜索

《STL源码剖析》

lmg
lmg
2023-01-07 / 0 评论 / 0 点赞 / 314 阅读 / 3,182 字
温馨提示:
本文最后更新于 2023-01-15,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

第三次翻开这本书了,希望这次可以看下去,立个flag,以此为鉴。

STL六大组件

  1. 容器(containers)

各种数据结果,如vector, list, deque, set, map,用来存放数据。

  1. 算法(algorithms)

各种常用算法,如sort, search, copy, erase, 是一种function template

  1. 迭代器(iterators)

迭代器是一种将operator*, operator->, operator++, operator–等指针相关操作予以重载的class template, 是所谓的“泛型指针”。

  1. 仿函数(functors)

行为类似函数,可算作算法的某种策略(policy),仿函数是一种重载了operator()的class或class template。

  1. 配接器(adapters)

一种用来修饰containers或functors或iterators接口的东西。如queue和stack,虽然看似内存,其实是一种容器配接器,因为它们的底层完全借助deque,所有的操作都由底层的deque供应。

  1. 配置器(allocators)

负责空间(内存,甚至可以是硬盘空间)的配置和管理

allocator

考虑到小型区块所可能造成得内存碎片问题,SGI设计了双层配置器
第一级配置器:
直接使用malloc()和free()
第二级配置器:
视不同情况采用不同的策略。
当申请空间大于128字节时,视之为“足够大”,便调用第一级配置器。
当申请空间小于128字节时,视之为“足够小”,使用复杂的memory pool方法。

第二级配置器

SGI第二级配置器会将任何小额内存需求量上调到8的倍数。并会维护16个free lists。各自管理大小为8,16,24 …128字节的链表。

  1. 大于128字节就调用第一级配置器
  2. 小于128字节就检查对应的free list, 如果free list有可用的区块,则直接拿来用
  3. 如果free list没有可用区块,就去内存池取空间给fress list使用。

内存池起始位置由内存起始位置的两个指针指定,中间的空间即为内存池空间。

static char* start_free;
static char* end_free;
  1. 如果内存池也没有足够空间,则用malloc heap空间,用来补充内存池。
  2. 如果山穷水尽,整个system heap空间都不够了,malloc行动失败,则会遍历寻找有无“尚有可用区块且区块够大”的free list, 找到了则挖一块交出,找不到则调用第一级配置器。第一级配置器其实也是使用malloc()来配置内存,但他有out of memory处理机制,或许有机会释放其它内存拿来此处使用,最差也可以发出bad_alloc异常。

iterator

iterator模式定义如下:提供一种方法,使之能依次巡访某个容器所含的各个元素,而又无需暴露该容器的内部表述方式。

iterator_traits

template<typename I>
struct iteraotr_traits { // traits 意为“特性”
	typedef typename I::value_type value_type;
}

在每个容器定义中,会标识自自身迭代器的类型:

// vector 容器 随机迭代器。list 容器 双向迭代器。
template<...> 
class vector{ 
public: 
    class iterator{ 
    public: 
        typedef random_access_iterator_tag iterator_category;  
     // 类型定义: vector<T>::iterator::iterator_category 就是 random_access_iterator_tag
     // 即类型里面还有一个类型, 而这个类型仅仅是用来标识 这个类是属于哪个类型的。 
    }; 
};
 
template<...> 
class list{ 
public: 
    class iterator{ 
    public: 
        typedef bidirectional_iterator_tag iterator_category; 
    }; 
};

这里选择迭代器模版和Advance的实现来讲解trait技术。

// advance为向前走n步
// advance 函数签名
template <class Iterator, class Distance>
void advance (Iterator& it, Distance n);

  std::list<int> mylist;
  for (int i=0; i<10; i++) mylist.push_back (i*10);
 
  std::list<int>::iterator it = mylist.begin();
  std::advance (it,5);


advance内部操作时候,需要知道advance的迭代器类型,看有哪些可用操作,比如随机访问器可以直接+= -=操作,前向仅支持++,输入输出均不支持,例子中的list属于双向,支持++,–。

所以在advance内部需要在取得某种类型信息,即迭代器的类型,进行不同的实现。

如何取得类型信息呢,容器类型::iterator::iterator_category(如上述2中的定义)

但是有一个问题,如果要支持内置类型,比如指针是一种随机迭代器类型,那么类型信息就不能放在类型内了,所以类型内的嵌套类的方式不能工作,所以类型的信息必须位于类型自身之外。

而trait标准技术是把它放进一个template,并进行一个偏特化版本,来实现迭代器所属类型trait。

// advance内部实现
// advance运行时确定使用哪种迭代器类型版本
template<typename IterT, typename DistT> 
void advance(IterT& iter, DistT d) 
{ 
    if (typeid(typename std::iterator_traits<IterT>::iterator_category) 
        == typeid(std::random_access_iterator_tag)) 
    { 
        iter += d;
    } 
    else if(前向迭代器类型)
    { 
         if (d < 0){throw std::out_of_range("Negative distance");} 
         while (d--) ++iter; 
    }
    else if(等等其他类型)
    ... 
}

// 或者可以优化一下,不用typeid, 用函数重载机制
// advance编译器确定使用哪种迭代器类型版本
template<typename IterT, typename DistT> 
void advance(IterT& iter, DistT d) 
{ 
    doAdvance(iter, d, typename std::iterator_traits<IterT>::iterator_category()); 
}
// 比如 双向迭代器的函数 。重载doAdvance,实现不同的迭代器类型的具体操作。
// 可以看到迭代器类型仅仅是个重载的作用,使得重载机制得以运行,都不需要变量名。
void doAdvance(IterT& iter, DistT d, std::bidirectional_iterator_tag)          
{                                                                                                               
    if (d >= 0) {while (d--) ++iter;} 
    else {while(d++) --iter;} 
}

序列式容器

序列式容器:元素ordered, not sorted
关联式容器:

vector

与数组(array)十分类似,唯一差别就是array是静态空间,一旦配置了就不能改变,vector是动态空间,可以扩容。

0

评论区