(Boolan) C++ STL与泛型编程——容器1

作者: 故事狗 | 来源:发表于2017-05-31 19:48 被阅读74次

STL标准库是开发中的利器，也是开发的宝库。

这次的源码分析主要以GNU C++的2.9和4.9版本为例，因为4.9之后代码重构，核心部分发生了巨大的变化，再次分别分析一下。

以GCC为例的标准库位置： ....\x.x.x\include\c++\

本地的目录

对于2.9和4.9最大的差别其实就是，2.9主要采用了泛型编程的思想，4.9引入了大量的面向对象编程的思想。

OOP（Object-Oriented Programming 面向对象编程） vs. GP（Generic Programming 泛型编程）

OOP
- OOP主要的思想是将datas和methods关联在一起的思想。
  也就是数据放在类中，操作数据的方法也是放在类中。（就像我以前举的一个例子，如果class 猫身上有毛，那么他必须有一个方法来管理他的毛，也就是舔毛()这个函数。只需要猫咪.舔毛();来调用这个函数，就可以管理和操作对应的数据）
GP
- GP的主要思想是将datas和methods分开
  在STL中大量使用到了GP的思想，来实现了数据和算法的分离，那么，算法如何才能操作数据呢，这中间的桥梁就是Iterators（迭代器）了，通过Iterator，算法可以从容器中获取到需要的数据，同样也就可以起到操作数据的目的。
  为何STL会采用GP的思想呢？其实使用了GP思想，类和类之间的关系不会那么紧密，也就不会产生很强的耦合性，便于不同的成员，协同开发不同的模块，有助于加快项目开发得效率，大家只需要依据“中间商”Iterator来编写各自代码就行了。

对于OOP来说最好的一点就是，方法和数据在同一个类中，那么方法是专门为类所设计的。比较方便能够管理其中的数据。GP由于数据和方法分离，操作的时候，难免有些数据，不能被这个方法所操作。比如，list 不能使用::sort() 进行排序，那到底是为什么呢？

看看::sort()的源码，发现问题所在

template <class RandomAccessIterator>
inline void sort(RandomAccessIterator first, RandomAccessIterator last)
{
    if(first != last)
    {
        _introsort_loop(first, last, value_type(first), __lg(last-first)*2);
        __final_insertion_sort(first, last);
    }
}
.....
template <class RandomAccessIterator, class T, class Size>
void __introsort_loop(RandomAccessterator first, RandomAccessIterator last, T*, Size depth_limit)
{
    ......
    RandomAccessIterator cut = __unguarded_partition(first, last, T(__median(*first, *(first + (last - first)/2), *(last - 1))));
//由于此处牵扯到了Iterator的下标运算
//list不是一个连续空间，前后节点之间靠指针相连，所以list 的Iterator不具备下表直接运算的能力，所以，list不能直接使用::sort()来进行排序
//也正是由于这个原因::sort() 只能为RandomAccessIterator来进行排序
    ......
}

那既然如此，在STL中，难道数据不适合就不能使用了，是否有其他方式来使用呢？
- 以max()为例

//标准库中的两个函数
template<class T>
inline const T& max(const T& a, const T& b){
    return a < b ? b: a;
}

template<class T, class Compare>
inline const T& max(const T& a, const T& b, Compare comp){
    return comp(a, b)? b: a;
}

//如何使用
//定义一个依据长度比较大小的函数
bool strLonger(const T& a, const T& b){
    return a.size() < s2.size();
}
cout << "max of zoo and hello:" 
  << max(string("zoo"), string("hello")) << endl;

cout << "longer of zoo and hello: " 
   << max(string("zoo"), string("hello"), strLonger) << endl;

分配器

分配器是容器管理内存的工具，对于容器的效率起着比较重要的作用
在正式开始说allocator之前，先说几句operator new()和 malloc()以及operator delete() 和free()
在创建对象时，会调用operator new()，而operator new()中分配内存实际也还是调用有C语言的Runtime Library所提供的malloc()，再由系统来分配所需要的内存；销毁对象时，则会使用operator delete()，而他实际会调用free()。

vc中的operator new()

void *operator new (size_t size, const std::nothrow_t&)
{
    void *p;
    while((p = malloc(size)) == 0)
    {
        _TRY_BEGIN
        if(_callnewh(size) == 0) break;
        _CATCH(std::bad_alloc) return(0);
        _CATCH_END
    }
    return (p);
}

malloc所分配的内存图

malloc所分配的内存图，如上图所示，其中蓝色部分为真正需要的内存。其余部分为系统分配的管理这部分空间的配套内存，其中保存了需要的这块内存的相关信息
灰色部分为调试模式系统分配的内存空间

根据vc版本，容器主要的使用的是allocator这个分配器的情况

template<class _Ty, class _a = allocator<_Ty> >
class vector{....}
template<class _Ty, class _a = allocator<_Ty> >
class list{....}
template<class _Ty, class _a = allocator<_Ty> >
class deque{....}
template<class _Ty, class _a = allocator<_Ty> >
class set{....}

template <class _Ty>
class allocator{
public:
    typedef _SIZT size_type;
    typedef _PDFT difference_type;
    typedef _Ty _FARQ *pointer;
    typedef _Ty value_type;
    pointer allocate(size_type _N, const void *){return (_Allocate((difference_type)_N, (pointer)0));  }
    void deallocate(void _FAQ *_P, size_type){operator delete(_P); }
}

///.....
//其中_Allocate()如下：
template<class _Ty> inline
_Ty _FARQ*_Allocate(_PDFT _N, _FARQ *){
    if (_N < 0) _N = 0;
    return (( _Ty _FARQ*) operator new ((_SIZT) _N * sizeof(_Ty)));
}

//如果使用allocator来申请内存
int *p = allocator<int>.allocate(512, (int*)0);  //申请空间
allocator<int>().dellocate(p, 512);//释放空间

由源代码可以看出，VC分配器实际是通过operator new和delete来调用malloc和free来管理元素的内存

GNU2.9的allocator也没有过多的设计，依然是通过::operator new和::operator delete来完成allocate()和deallocate()，但是，在2.9版本中，实际容器使用的并非allocator，而是alloc

template<class _Ty, class _a = alloc >
class vector{....}
template<class _Ty, class _a = alloc >
class list{....}
template<class _Ty, class _a = alloc >
class deque{....}
template<class _Ty, class _a = alloc >
class set{....}

alloc这个分配器的主要目的是为了减少malloc的调用次数
malloc申请空间时，多余的空间的主要目的是为了free时能够快速的知道申请的空间到底是多大。而对于容器来说，其中所保存的元素大小是相同的，不需要在每个元素的前头都记录空间到底是多大。
alloc的解决方案：

alloc的管理方式示意图

设计了十六条链表，每条链表都负责对应大小的管理工作
元素的大小会被调整到8的倍数，然后在管理，比如，50字节会被调整为56字节
第一条链表负责8个字节大小元素的部分，第二条链表负责16个字节大小元素的部分，第三条负责24个字节大小元素的部分，以此类推，一直到第十六条链表，负责管理128字节的元素的部分
如果没有内存，则一次性申请较大的空间，然后将这些空间等分，所以相对于只malloc一次，则只有大空间具有那些额外的空间，而中间等分的部分实际上没有那么多额外的空间的浪费

那么对于GNU4.5之后还在使用alloc这个分配器吗？

template<typename _Tp, typename _Alloc = std::allocator<_Tp> >
class vector: protected _Vector_base<_Tp, _Alloc>{....}

#define __allocator_base __gnu_cxx::new_allocator
template<typename _Tp>
class allocator: public __allocator_base<_Tp>
{
 .....
}

template<typename _Tp>
class new_allocator
{
    ...
    pointer allocator(size_type __n, const void* = 0){
        if(__n > this ->max_size())
            std::__throw_bad_alloc();
        return static_cast<_Tp*> (::operator new (_n * sizeof(_Tp)));
}
    void deallocate(pointer __p, size_type){
        ::operator delete(__p);
}
    ...
}

分配器的UML

在4.9版本以后，gnu的分配器也没有特殊设计，也是采用直接调用operator new来分配空间
之前设计的分配器被放入到了扩充分配器中（extention allocators），其中__pool_alloc就是GNU2.9的alloc，可以

vector<string,__gun::_cxx::__pool_alloc<string> > vec;来使用

容器结构分类

序列式容器（Sequence Container）的衍生关系
- array （C++2.0）连续空间
- vector 连续空间
- heap 以算法形式呈现（xxx_heap()）
  - priority_queue
- list 双向链表
- slist C++2.0中为forward_list,单向链表
- deque 分段连续空间
  - stack Container Adapter
  - queue Container Adapter
关联式容器（Associative Containers）的衍生关系(复合)
- rb_tree 红黑树，非公开
  - set
  - map
  - multiset
  - multimap
- hashtable非公开
  - hash_set非标准，C++2.0为unordered_set
  - hash_map非标准，C++2.0为unordered_map
  - hash_multiset非标准，C++2.0为unordered_multiset
  - hash_mulitmap非标准，C++2.0为unordered_multimap

容器 list

template <class T>
struct __list_node{
    typedef void* void_pointer;
    void_pointer prev;
    void_pointer next;
    T data;
};

template<class T, class Alloc = alloc>
class list{
protected:
    typedef __list_node<T> list_node;
public:
    typedef list_node* link_type;
    typedef __list_iterator<T, T&, T*> iterator;
protected:
    link_type node;
};

template<class T, class Ref, class Ptr>
struct __list_iterator{
    typedef T value_type;
    typedef Ptr pointer;
    typedef Ref reference;
}

UML

内存关系示意图

list为一个循环链表（如图），但是对于迭代器来说，end()获取到的并非容器中的最后一个元素，而应该是，最后一个元素之后的空元素，所以在list实现的时，可以看到，end()指向了一个灰色的区域，这个区域实际就是end()指向的非容器内元素的区域
由于list非连续空间，所以Iterator在++时，如果不作调整，不会默认的移动到下一个不连续空间，所以，为了让Iterator能够和指针的用法相似，Iterator一定是一个class

template<class T, class Ref, class Ptr>
struct __list_iterator{
    typedef __list_iterator(T, Ref, Ptr> self;
    typedef bidirectional_iterator_tag iterator_category;
    typedef T  value_type;
    typedef Ptr pointer;
    typedef Ref reference;
    typedef __list_node<T>* link_type;
    typedef  ptrdiff_t difference_type;

    link_type nod;

    reference operator*() const{
        return (*node).data;
    }
    pointer operator->() const {
        return &(operator*());
    }
    self& operator++(){//前++
        node = (link_type)((*node).next); return *this;
    }
    self operator++(int){//后++，参数实际无意义
        self temp = *this; ++*this; return tmp;
    }
};

4.9版本list的UML

Iterator的设计原则

算法要求这几项的类型必须指定出来

算法（algorithms）在操作容器（Container）中的数据需要通过Iterator知道的信息如下：
1. iterator_category：Iterator的性质，例如是否可以双向查询
- difference_type：两个Iterator之间的距离的type（int、unsigned int），决定了容器可以容纳多少元素
- value_type：元素本身的type
- reference：引用
- pointer：指针
  在Iterator的设计时，必须有这五种associated types
traits的引入
- 如果Iterator不是一个class的情况，如果这样的情况，无法从一个指针中获取以上的几种类型，那么这时候，需要一个“中介”来去协调这件事，这时候就出现了一个traits的机制
- 这个traits可以区分到底是class设计的Iterator，也能够区分是指针传入的Iterator

//traits的设计
template<class I>
struct iterator_traits{
    typedef typename I::value_type value_type;
    typedef typename I::iterator_category
    typedef typename I::difference_type
    typedef typename I::pointer
    typedef typename I::reference
};

//针对指针的两种偏特化
template<class T>
struct iterator_traits<T*>{
    typedef T value_type;
    typedef random_access_iterator_tag iterator_category;
    typedef ptrdiff_t difference_type;
    typedef T* pointer;
    typedef T& reference;
};

template <class T>
struct iterator_traits<const T*>{
    typedef T value_type;
    typedef random_access_iterator_tag iterator_category;
    typedef ptrdiff_t difference_type;
    typedef T* pointer;
    typedef T& reference;
}

//traits的使用
template<typename I, ....>
void algorithm(......){
    typename iterator_traits<I>::value_type v1;
}

根据偏特化，如果传入的为指针就会自动进入偏特化的部分，那么就根据偏特化来获取响应信息
各式各样的traits以及对应的头文件
- type traits : .../c++/type_traits
- iterator traits: .../c++/bits/stl_iterator.h
- char traits: .../c++/bits/char_traits.h
- allocator traits:.../c++/bits/alloc_traits.h
- pointer traits: .../c++/bits/ptr_traits.h
- array traits:.../c++/bits/array.h

容器Vector

vector根据三个指针就可以控制全部内容 iterator start;、 iterator finish;、iterator end_of_storage;
其中finish指向最后一个元素之后的位置。

template <class T, class Alloc = alloc>
class vector
{
public:
    typedef  T value_type;
    typedef value_type* iterator;
    typedef value_tyle&  reference;
    typedef size_t  size_type;
protected:
    iterator start;
    iterator finish;
    iterator end_of_storage;
public:
    iterator begin(){return start;}
    iterator end() {return finish;}
    size_type size() const{
        return size_type(end() - begin());
    }
    size_type capacity() const {
        return size_type(end_of_storage - begin());
    }
    bool empty() const {
      return begin() == end();
    }
    reference operator[](size_type n){return *(begin() + n); }
    reference front() {return *begin();}
    reference back(){ return *(end() - 1); }
}

二倍成长
- 对于内存来说没办法实现原地扩充，因为前后都可能存在着其他程序的数据，如果扩充，意味着会要影响到其他程序，并且操作系统也不允许这样干。那么对于vector来说，hi如何来实现扩充的呢？那么再扩充的时候，需要在内存的其他区域找到空间，在新找到的空间进行扩充完成后，再将数据复制到新开辟的空间中。而且每次增长的空间都是以两倍作为基准。
  
  vector的内存图

存入元素和两杯增长的代码

void push_back()(const T& x)
{
    if(finish != end_of_storage){//尚有备用空间
        construct(finish, x); 
        ++finish; 
    }
    else{
        insert_aux(end(), x);
    }
}


template<class T, class Alloc>
void vector<T, Alloc>::insert_aux(iterator position, const T& x){
    if(finish != end_of_storage){//空间够用
        //在备用空间起始处建一个元素，并以vector最后一个元素为其初值
        construct(finish, *(finish - 1);
        ++finish;
        T x_copy = x;
        copy_backward(postion, finish - 2, finish - 1);
        *postion = x_copy;
    }
    else{  //空间不够用
        const size_type old_size = size();
        const size_type len = old_size != 0? 2*old_size: 1;
        iterator new_start = data_allocator::allocate(len);
        //以上分配原则：剐原大小为0，分配1；不为0，分配原大小的两倍；前半段用来放置原数据，后半段用来放置新数据
        iterator new_finish = new start;
        try{
            //将原vector的内容拷贝到新的vector
            new_finish = uninitialized_copy(start, position, new_start);
            construnct(new_finish, x);//为新元素设置初值x
            ++new_finish;
            //拷贝安插点后的原内容
            new_finish = uninitialized_copy(postion, finish, new_finish);
        }
        catch(...){
              destory(new_start, new_finish);
            data_allocator::deallocate(new_start, len);
          throwl
        }
        //析构并释放元vector
        destory(begin(), end());
        //调整迭代器，指向新的vector
        deallocate();
        start = new_start;
        finish = new_finish;
        end_of_storage = new_start + len;
    }
}

GNU4.9之后的结构

UML

容器array

没有ctor，没有dtor

template<typename _Tp, std::size_t _Nm>
struct array{
    typedef _Tp;
    typedef _Tp*;
    typedef value_type*;
  
    value_type _M_instance[_Nm? _Nm: 1];
    iterator begin(){
        return iterator(&_M_instance[0]);
    }
    iterator end(){
        return iterator(&_M_instance[_Nm]);
    }
}

forward_list

单向链表，具体可以参考list（双向链表）

UML

内存示意图

(Boolan) C++ STL与泛型编程——容器1

OOP（Object-Oriented Programming 面向对象编程） vs. GP（Generic Programming 泛型编程）

分配器

容器结构分类

容器 list

Iterator的设计原则

容器Vector

容器array

forward_list

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读