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

2017-05-31  本文已影响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来说最好的一点就是，方法和数据在同一个类中，那么方法是专门为类所设计的。比较方便能够管理其中的数据。GP由于数据和方法分离，操作的时候，难免有些数据，不能被这个方法所操作。比如，list 不能使用::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来进行排序
    ......
}

//标准库中的两个函数
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()。

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来管理元素的内存

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的管理方式示意图

那么对于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

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

容器结构分类

容器 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 内存关系示意图 
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的设计原则

算法要求这几项的类型必须指定出来 
//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;
}

容器Vector

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); }
}

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

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;
    }
}
UML

容器array

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

UML 内存示意图
上一篇下一篇

猜你喜欢

热点阅读