Boolan微专业-STL与泛型编程（Week02）

2018-02-18 本文已影响0人 GoMomi

STL与泛型编程

主要内容：

简单介绍了 OOP 和 GP 编程。详细剖析了 STL 中的分配器、list、Iterator、vector、array、forward_list

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来进行排序
    ......
}

分配器

分配器是容器管理内存的工具，对于容器的效率起着比较重要的作用

在正式开始说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);
}

容器结构分类

序列式容器（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;
}

内存关系示意图

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

Iterator 的设计原则

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

算法（algorithms）在操作容器（Container）中的数据需要通过Iterator知道的信息如下：
- iterator_category：Iterator的性质，例如是否可以双向查询
- ifference_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如何来实现扩充的呢？那么再扩充的时候，需要在内存的其他区域找到空间，在新找到的空间进行扩充完成后，再将数据复制到新开辟的空间中。而且每次增长的空间都是以两倍作为基准。
存入元素和两杯增长的代码

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

容器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

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