SGI STL 阅读笔记

2018-06-20  语言  ,,,  2,074

这是OOP课留下的作业,要求阅读别人的项目。

我选择的是SGI STL,项目地址:github.com/steveLauwh/SGI-STL

下边是我在阅读过程中的一些笔记(并不一定都是STL相关的,但肯定是C++相关)

template偏特化

template<typename T>
void func<T *> () {}

接受的是指针类型,使用func<int *>();才能正确调用

template中class和typename的区别

如果要用模版类型T的作用域中的东西T::,就必须在T前声明typename,来指明T是一种类型,比如

template<typename T>
class A {
    typename T::iterator it;
};

A<vector<int>> a;

traits classes

将一些模版类型(一般是迭代器类型或者指针)中的信息给封装好的类

比如

template <typename T>
struct get_value_type {
    typedef typename T::value_type the_value_type;
};

get_value_type<vector<int>::iterator>::the_value_type a; // int a

就可以获得STL中容器的迭代器所指类型(前提是迭代器类都定义了value_type这个类型)

由于迭代器也可以是指针,因此要特化一下

template <typename T>
struct get_value_type<T *> {
    typedef T the_value_type;
};

那么get_value_type<int *>::the_value_type同样也能得到int类型

STL的六大组件

  • 容器(container):一些数据结构。是类模板(class template)。
  • 算法(algorithm):一些算法。是函数模版(function template)。
  • 迭代器(iterator):是容器与算法之间的黏合剂;是所谓的泛型指针;是一种将指针相关操作(++--等操作符)进行重载的类模板。每个STL容器都有自己的迭代器。C语言中的指针也是一种迭代器。
  • 仿函数(functor):是重载了()操作符的类或者类模板。
  • 配接器(adapter):继承于已有类型,隐藏一些接口、重新暴露一些接口来形成的一种新的类型。
  • 配置器(allocator):是管理内存的类模板。

STL源码中的文件

源码中每一个容器都有3个文件对应,比如vector模板类,那么有以下3个文件:

  • vector:就是我们平常include的文件,#include <vector>;里面包含的是依赖头文件。
  • vector.h:和vector差不多,不过考虑到了兼容有C语言习惯的人,直接将std中的vector给暴露出来。
  • stl_vector.h:真正实现vector模板类的文件。

vector

由于我对vector内部的内存分配比较感兴趣,因此我选择查看vector的代码

concept_check.h文件

vector中include了concept_checks.h,看了下该文件,应该是定义了很多STL要用到的宏(各种用于检查的宏等)

traits技术

代码中大量用到了traits技术,这个技术的思想还是很niub的。

我们想通过仅仅一个value_type *来获取一些信息该怎么做呢?请看代码:

template <typename T>
struct the_trait <T *> {
    typedef T value_type;
    typedef T * pointer;
};

那么你就可以通过the_trait<int *>::value_typethe_trait<int *>::pointer得到相应的类型intint *

你说这大可不必?那么我们再看一个例子。

假如你有一个m_iterator泛型指针(即是一个类),那么你想要得到这个m_iteratorvalue_type怎么办呢?用m_iterator::value_type吗?那你怎么兼容T *value_type(即T)?写两份代码?No,这不符合OOP。

你可以这样

template <typename T>
struct the_trait <T> {
    typedef typename T::value_type value_type;
    typedef typename T::pointer pointer;
};

template <typename T>
struct the_trait <T *> {
    typedef T value_type;
    typedef T * pointer;
};

// 那么你可以这样
typedef int * iterator_1;
typedef vector<int>::iterator iterator_2;

the_trait<iterator_1>::value_type a1; // int a1
the_trait<iterator_1>::pointer a2; // int * a2
the_trait<iterator_2>::value_type b1; // int b1
the_trait<iterator_2>::pointer b1; // vector<int>::iterator b2

// 如果放到模板里就可以这样
template <typename Iterator>
void func() {
    the_trait<Iterator>::value_type value;
    the_trait<Iterator>::pointer ptr;
}

只需要特化模版类the_trait就完美了!是不是十分帅气,十分OOP?!

这个技术在STL中大量使用。

iterator

在vector中,迭代器其实就是value_type *的别名,即C语言中的指针。

_Vector_alloc_base 类

定义了__STL_USE_STD_ALLOCATORS宏后才有的类(即表示使用STL提供的内存管理器)。

这是管理vector内存的模版基类,该类还有静态的模版特化类。

只提供两个方法_M_allocate_M_deallocate,分别表示内存申请和释放。还提供了三个指针:

  • _M_start:指向动态数组的开始位置
  • _M_finish:指向动态数组的结束位置的后一位(但并不是所申请连续一段内存的结束位置的后一位)
  • _M_end_of_storage:指向所申请连续一段内存的结束位置的后一位(往往_M_finish不等于_M_end_of_storage,因为要预留一些空间出来,而不至于频繁的申请内存)

_Vector_alloc_base析构的时候并不释放内存。

注意在STL里,范围一般都是左闭右开的。

_Vector_base 类

若定义了__STL_USE_STD_ALLOCATORS宏,则该类直接继承于_Vector_alloc_base类,并在析构时释放所申请的内存;

否则不继承任何类。并且使用使用者提供的allocator来管理内存。同时实现了_Vector_alloc_base类里的两个方法_M_allocate_M_deallocate,并在析构时也释放所申请内存。

可以看做是真正意义上的vector的用于管理内存的基类。

vector 类

继承于_Vector_base类。

在这里我挑一些比较有代表性的东西出来:

  • Q:为什么在vector的析构函数中有个destroy?在_Vector_base中的析构函数不是已经释放了内存吗?

destroy方法定义在stl_construct.h中,总结一下就是,调用迭代器所指对象的析构函数(若迭代器是基础数据类型的指针,则不做任何操作)。注意此方法并不会delete掉迭代器所指对象!而delete掉迭代器所指对象这个活,是由_Vector_base的析构函数中的deallocate来做的。具体来说是这样的:

class_A *a = new class_A();

a->~a(); // destroy所做的事
delete a; // _Vector_base析构函数中的deallocate所做的事
  • Qstl_construct.h中的_Construct函数的奇怪语句new ((void*) __p) _T1();是什么?

这是placement new,表示在指针__p所指地址上用默认构造函数重新构建对象。

  • erase方法并不会释放内存

erase方法中用的是destory方法,并不会释放内存。若要释放vector内存只有析构它或者调用_M_deallocate方法手动释放(实际上是调用不了_M_deallocate的,没权限)。

  • 真正核心的东西在_M_insert_aux方法里

vector预留的空间满了怎么办?重新开辟一个2倍大小的空间(stl_vector.h的第645行const size_type __len = __old_size != 0 ? 2 * __old_size : 1;)!然后将之前的数据迁移过去。

很容易证明这样的插入操作时间复杂度是均摊$O(1)$的。

总结

  • 模版类、方法
  • 模版的特化、方法的重载
  • 普通的is-a继承关系
  • 大量宏
  • traits技术

参考资料

STL——STL六大组件概念:https://blog.csdn.net/bian_cheng_ru_men/article/details/80735221

《STL源码剖析》总结:https://blog.csdn.net/bian_cheng_ru_men/article/details/80735221

细说 C++ Traits Classes:https://blog.csdn.net/lihao21/article/details/55043881

C++ new关键字深入理解:https://blog.csdn.net/bbs375/article/details/53202079

欢迎留言>_<

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据