2 STL的程式設計範式

OOP(Object-Oriented Programming)：面向對象 資料和操作在同一個類;OOP企圖将datas和methods關聯在一起

template<class T, class Alloc = alloc>
class list{
	...
	void sort();
}
           

GP(Generic Programming)：泛型程式設計 datas和methods分隔開，即algorithm和contains分隔開，通過iterator互動。

template<typename _RandomAccessIterator>
inline void sort(_RandomAccessIterator __first, _RandomAccessIterator __end)
           

STL采用GP的原因：

1. Containers和Algorithms團隊刻個字閉門造車，Iterators團隊溝通。
2. Algorithms通過Iterators确定操作範圍，并通過Iterators取用Containers元素。

例子：

有算法（Algorithms）如下：

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

如果要對一個自定義類進行大小比較，則可以重載<，或者寫個Compare函數。這樣，算法就有了其通用性，而無需關心容器是什麼。

泛化、特化、偏特化

特化即特殊化，即設計者認為對于制定類型，使用特定版本更好。

全特化就是限定死模闆實作的具體類型。

偏特化就是如果這個模闆有多個類型，那麼隻限定其中的一部分。

優先級：全特化類>偏特化類>主版本模闆類

//泛化
Template <class type>   
Struct __type_traits{typedef __true_type this_dummy_member_must_be_first; };
//特化1
Template < >   
Struct __type_traits<int>{typedef __true_type this_dummy_member_must_be_first; };
//特化2
Template < >   
Struct __type_traits<double>{typedef __true_type this_dummy_member_must_be_first; };
//__type_traits<FOO>:: this_dummy_member_must_be_first; 使用的是泛化的内容

//泛化
Template <class T, class Alloc = alloc> 
Class vecor{};
//偏特化(個數偏特化，第一個特化，第二個不特化)
Template <class Alloc>
Class vector<bool, Alloc>{};

//泛化
Template <class Iterator>
Struct iterator_traits {};
//偏特化1（範圍偏特化，隻能是傳入指針）
Template <class T>
Struct iterator_traits<T*>{};
//偏特化2
Template <class T>
Struct iterator_traits<const T*>{};
           

為什麼list不能使用::sort函數

list底層資料結構為連結清單，不支援随機通路（random access），是以list這個Containers中，有自帶的sort方法。

::sort接口為：

sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
{
    typedef typename __comp_ref_type<_Compare>::type _Comp_ref;
    _VSTD::__sort<_Comp_ref>(__first, __last, _Comp_ref(__comp));
}
           

list.sort為，可以看到為連結清單的歸并排序：

template <class _Tp, class _Alloc>
template <class _Comp>
typename list<_Tp, _Alloc>::iterator
list<_Tp, _Alloc>::__sort(iterator __f1, iterator __e2, size_type __n, _Comp& __comp)
{
    switch (__n)
    {
    case 0:
    case 1:
        return __f1;
    case 2:
        if (__comp(*--__e2, *__f1))
        {
            __link_pointer __f = __e2.__ptr_;
            base::__unlink_nodes(__f, __f);
            __link_nodes(__f1.__ptr_, __f, __f);
            return __e2;
        }
        return __f1;
    }
    size_type __n2 = __n / 2;
    iterator __e1 = _VSTD::next(__f1, __n2);
    iterator  __r = __f1 = __sort(__f1, __e1, __n2, __comp);
    iterator __f2 = __e1 = __sort(__e1, __e2, __n - __n2, __comp);
    if (__comp(*__f2, *__f1))
    {
        iterator __m2 = _VSTD::next(__f2);
        for (; __m2 != __e2 && __comp(*__m2, *__f1); ++__m2)
            ;
        __link_pointer __f = __f2.__ptr_;
        __link_pointer __l = __m2.__ptr_->__prev_;
        __r = __f2;
        __e1 = __f2 = __m2;
        base::__unlink_nodes(__f, __l);
        __m2 = _VSTD::next(__f1);
        __link_nodes(__f1.__ptr_, __f, __l);
        __f1 = __m2;
    }
    else
        ++__f1;
    while (__f1 != __e1 && __f2 != __e2)
    {
        if (__comp(*__f2, *__f1))
        {
            iterator __m2 = _VSTD::next(__f2);
            for (; __m2 != __e2 && __comp(*__m2, *__f1); ++__m2)
                ;
            __link_pointer __f = __f2.__ptr_;
            __link_pointer __l = __m2.__ptr_->__prev_;
            if (__e1 == __f2)
                __e1 = __m2;
            __f2 = __m2;
            base::__unlink_nodes(__f, __l);
            __m2 = _VSTD::next(__f1);
            __link_nodes(__f1.__ptr_, __f, __l);
            __f1 = __m2;
        }
        else
            ++__f1;
    }
    return __r;
}