GeekBand STL与泛型编程 First Week

GeekBand STL与泛型编程 First Week

泛型编程

模版介绍

模版是C++的一种特性，允许函数或类通过泛型的形式表现和运行。模版的类型有 类模版，函数模版， 成员模版等。

模版的实例化是从模版构建出一个真正函数或类的过程。模版被编译了两次。没有被实例化之前，检查模版代码本身是否有语法错误，在实例化期间，检查对模版代码的调用是否合法。

函数模版是参数化的一族函数。通过模版函数，可以定义一系列函数。这些函数都是基于同一套代码，但是可以作用在不同型别的参数上

C++类模版，与函数模版类似，类也可以通过参数泛化，从而可以构建出一族不同型别的类实例。类模版实参可以是某一型别或常量。

const std::size_t DefaultStackSize = 1024;
template <typename T, std::size_t n = DefaultStackSize > class stack
{
public:
    void push(const T const& elememt);
    int Pop(T& element);
    int Top(T& elememt) const;
private:
    std::vector<T> m_Members;
    std::size_t m_nMaxSize = n;
}

类模版的特化，允许对一个类模版的某些模版参数类型做特化。特化的作用在于：对于某种特殊的型别，可能可以做些特别的优化或提供不同的实现；避免在实例化类的时候引起一些可能产生的诡异行为。类模版同样可以特化或者偏特化。 如果有不止一个偏特化铜等程度地能匹配某个应用，那么该调用具有二义性，会产生编译错误。

C++类模版参数可以有默认值。

Traits(特性)

Traits在面向对象程序设计中，是一个不可实例化（uninstantiable）的方法与类型的集合，为一个对象或算法提供了策略（policy）或实现自身界面的细节功能。

Traits作为模板类，既声明了统一的界面（包括类型、枚举、函数方法等），又可以通过模板特化，针对不同数据类型或其他模板参数，为类、函数或者通用算法在因为使用的数据类型不同而导致处理逻辑不同时，提供了区分不同类型的具体细节，从而把这部分用Traits实现的功能与其它共同的功能区分开来。例如，容器的元素的不同数据类型，或者iostream是使用char还是wchar_t。

C++标准模板库中大量使用了traits。将因为模板形参（包括类型形参、非类型形参）不同而导致的不同抽取到新的模板（即traits）中去；然后通过traits的模板特化来实现针对具体情况的优化实现。一个traits包括了enum、typedef、模板偏特化（template partial specialization）。其中，enum定义了各种类的标识的统一表示；typedef定义了各个类的各自不同的类型定义，这对于使用模板元编程（template meta-programming）的灵活性非常重要；模板偏特化用于实现各个类的不同功能。

Example:

// tag struct
struct input_iterator_tag {};
struct output_iterator_tag {};
struct forward_iterator_tag : public input_iterator_tag {};
struct bidirectional_iterator_tag : public forward_iterator_tag {};
struct random_access_iterator_tag : public forward_iterator_tag {};

traits 必须能够施行于内置类型，意味着 类型内嵌套信息(nesting inforamtion) 这种东西出局了，因为我们无法将信息嵌套于原始指针内。因此类型的traits信息。因此类型的traits信息必须位于类型自身之外。标准技术放入一个template及其一个或多个特化版本中。

Example:

// trabit classes
template<typename IterT>
struct iterator_traits;

template <...>
class deque {
public:
    class iterator {
    public:
        typedef random_access_iterator_tag iterator_category;
    }
};

template <...>
class list {
public:
    class iterator {
    public:
        typedef bidirectional_iterator_tag iterator_category;
    }
};

template<typename IterT>
struct iterator_traits {
    typedef typename IterT::iterator_category iterator_category;
};

template<typename IterT>
struct iterator_traits<Iter T*> {
    typedef random_access_itrator_tag iterator_category;
}

Trabit Class 如何设计

• 确认若干希望将来可以取得的类型信息，比如对于Iterator而言，我们希望可以取得其category
• 为信息选择一个名称，例如 iterator_category
• 提供一个template和一组特化版本，内含你希望支持的类型相关信息

此处编译期间的if...else语句 判断类型，可以使用重载

template<typename IterT, typename DistT>
void advance(IterT &iter, DistT d)
{
    doAdvance(iter, d, typename std::iterator_trabits<IterT>::iterator_category())
}

tempalte<typename IterT, typename Dist T>
void doAdvance(IterT &iter, DistT d, std::random_access_iterator_tag)
{
    iter += d;
}

tempalte<typename IterT, typename Dist T>
void doAdvance(IterT &iter, DistT d, std::bidirectional_iterator_tag)
{
    if (d >= 0) { while(d--) ++iter; }
    else { while (d++) --iter; }
}

tempalte<typename IterT, typename Dist T>
void doAdvance(IterT &iter, DistT d, std::bidirectional_iterator_tag)
{
    if (d < 0) { throw std::out_of_range("Negative distance"); }
    
    while (d--) ++iter;
}

总结:

• 建立一组重载函数或者函数模板(例如doAdvance)，彼此之间的差异只在于各自的trabit参数。令各个函数实现码与其接受之trabits信息相应和
• 建立一个控制函数或者函数模板(例如advance)，它调用上述的"劳工函数"，并传递traits class提供的信息

迭代器 Iterator

迭代器是一种 Pointer-like class。是指针的泛化。迭代器本身是一个对象。在STL中迭代器是容器与算法之间的接口。在STL中，算法和容器是分离的，而迭代器就是它们之间的粘合剂。如 find 算法，接收一对迭代器作为参数，分别指向容器的开始和结束。

template<class _InIt, class _Ty>
inline _InIt find(_InIt _First, _InIt _Last, const _Ty& _Val)
{
    for(; _First != _Last; ++_First)
        if(*_First == _Val)
            break;
    return (_First);
}

Iterator也是一种很长的设计模式的手法，用来遍历一个Resource，这样可以屏蔽很多内部操作，直接利用了C++的operator++/operator--/operator+/operator-重载。

当然C++的iterator也是有好几个分类的。具体而言
1.输入迭代器(input iterator)
2.输出迭代器(output iterator)
3.前向迭代器(forward iterator)
4.双向迭代器(bidirectional iterator)
5.随机存取迭代器(random access iterator)

输入迭代器(input iterator)
input iterator就像其名字所说的,工作的就像输入流一样.我们必须能

• 取出其所指向的值
• 访问下一个元素
• 判断是否到达了最后一个元素
• 可以复制
  因此其支持的操作符有 *p,++p,p++,p!=q,p == q这五个.凡是支持这五个操作的类都可以称作是输入迭代器.当然指针是符合的.

输出迭代器(output iterator)
output iterator工作方式类似输出流,我们能对其指向的序列进行写操作,其与input iterator不相同的就是*p所返回的值允许修改,而不一定要读取,而input只允许读取,不允许修改.
支持的操作和上头一样,支持的操作符也是 *p,++p,p++,p!=q,p == q.

Example:

template<class In,class Out>
void copy(In start,In beyond, Out result)
{
     while(start != beyond) {
         *result = *start; // result是输出迭代器,其*result返回的值允许修改
         ++result;
         ++start;
      }
}

// 简写
template<class In,class Out>
void copy(In start,In beyond, Out result)
{
     while(start != beyond)
        *result++ = *start++;
}

前向迭代器(forward iterator)
前向迭代器就像是输入和输出迭代器的结合体,其*p既可以访问元素,也可以修改元素.因此支持的操作也是相同的.

双向迭代器(bidirectional iterator)
双向迭代器在前向迭代器上更近一步,其要求该种迭代器支持operator--,因此其支持的操作有*p,++p,p++,p!=q,p == q,--p,p--

随机存取迭代器(random access iterator)
即如其名字所显示的一样,其在双向迭代器的功能上,允许随机访问序列的任意值.显然,指针就是这样的一个迭代器.
对于随机存取迭代器来说, 其要求高了很多:

• 可以判断是否到结尾( a==b or a != b)
• 可以双向递增或递减( --a or ++a)
• 可以比较大小( a < b or a > b or a>=b ...etc)
• 支持算术运算( a + n)
• 支持随机访问( a[n] )
• 支持复合运算( a+= n)

容器 Containter

我们所用的常用的数据结构不外乎 array, list, tree, stack, queue, hash table, set, map 等。这些数据结构分为序列式（sequence）和关联式（associative）两种。

Sequence Container : array, vector, list, deque
Associative Containter : set, map, multimap, unordered map

对于Sequence Container，我们一般认为这个是一个动态的数组，只是实现上各有差异，可以为链表，这个差异就是索引时候的速度，数组是O(1), 链表是O(n)。且从空间上来说动态数组在capacity相同的时候空间占用会比链表要少一些。但是链表在指定位置插入的成本会比数组少很多，是O(1)。