【STL和泛型編程】2. 分配器、萃取器、迭代器、仿函數(shù)和適配器源碼精讀

分配器allocator 和萃取器Iterator Traits 源碼解讀，迭代器以及這其中涉及到的仿函數(shù)、適配器的源碼精讀，理解STL這6大部件之間的合作，設計太巧妙了。

1. OOP和GP

OOP（Object-Oriented programming）和GP（Generic Programming）面向?qū)ο缶幊毯屯ㄓ镁幊?/p>

OOP的目標是將數(shù)據(jù)和方法整合到一個類中
GP的目標是將數(shù)據(jù)和方法分開，容器包含了數(shù)據(jù)，算法包括排序方法等，而他們通過迭代器連接
- 例：sort()函數(shù)需要傳入支持隨機訪問的迭代器，所以sort()不能對list的迭代器進行排序（但list自身有sort函數(shù)）

2. 模板

模板（泛化、全特化、偏特化）廣泛存在于STL中
- 全特化：template<>來表示模板的特化版本

#define __STL_TEMPLATE_NULL template<>

template <class Key> struct hash {};    // 泛化

__STL_TEMPLATE_NULL struct hash<char> {
    size_t operator()(char x) const {return x;}    // 全特化
__STL_TEMPLATE_NULL struct hash<short> {
    size_t operator()(char short) const {return x;}    // 全特化...

- 偏特化：個數(shù)上的偏特化和范圍上的偏特化

template <class T, class Alloc = alloc>    // 全特化
class vector {};

template <class Alloc>    // 偏特化（數(shù)量上的局部，原本有2個模板參數(shù)，現(xiàn)在只有1個）
class vector<bool, Alloc> {};

template <class Iterator>
struct iterator_traits {};

template <class T>    // 偏特化（范圍上的局部，如果傳入的是指針）
sturct iterator_traits<T*> {};

template <class T>    // 偏特化（范圍上的局部，如果傳入的是指針）
sturct iterator_traits<const T*> {};

3. 分配器

operator new()操作符根據(jù)類對象進行malloc()操作，申請一塊內(nèi)存，結(jié)構(gòu)如圖所示，它會包含必須的內(nèi)存空間以及一些額外的空間存儲數(shù)據(jù)

　　在VC6中，allocator只是調(diào)用了operator new和operator delete這兩個操作符來完成allocate和deallocate這兩個函數(shù)，沒有任何特殊設計。這里存在一個問題，如果每次申請的都是1個int變量，因為調(diào)用operator new會申請額外空間存儲一些必要數(shù)據(jù)，這會導致存儲的額外開銷非常大。

class allocator {
public:
    typedef _SIZT size_type;
    typedef _PDEF 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 _FARQ *_P, size_type)
        { operator delete(_P); }
};

　　直接使用 allocator 非常反人性，需要傳入需要的類型以及數(shù)量，清除內(nèi)存的時候也需要傳入對應正確的數(shù)量

// 分配 512 個 int
int *p = allocator<int>().allocate(512, (int*)0);
allocate<int>().deallocate(p, 512);

　　在 G2.9 中也實現(xiàn)了allocator分配器，但實際實際上沒有使用，而是使用了alloc分配器。allocator分配器每次申請一個元素時，在該塊內(nèi)存空間還有額外的內(nèi)存記錄該元素的大小等信息。但在容器中，這些信息實際上是非必要的。例如vector<int>容器中所有的元素都是8個字節(jié)，不需要為每個元素單獨開辟內(nèi)存空間來記錄。alloc從這一點著手進行了優(yōu)化

// STL源碼中默認的分配器都使用了alloc
template <class T, class Alloc = alloc>
class vector {};

template <class T, class Alloc = alloc>
class list {};

　　alloc實現(xiàn)在<stl_alloc.h>中，有16條鏈，每個鏈負責8字節(jié)。例如8字節(jié)的int全部放到第0條鏈中，而alloc每次申請一大塊內(nèi)存來存儲這些數(shù)據(jù)，減少了額外內(nèi)存空間的使用

　　在新版的 G4.9 中默認的alloc又恢復成了基本的allocator，而alloc這個分配器被移動到了extension allocators，并且名字修改為了__pool_alloc，所以如果想要使用這個分配器，需要額外進行顯示的說明

vector<string, __gnu_cxx::__pool_alloc<string>> myVec;

4. 迭代器作用與設計

4.1 Iterator

　　iterator是算法和容器間的橋梁，它讓算法知道元素處理的范圍，同時也需要滿足算法需要的性質(zhì)（如隨機訪問，++操作等）。即算法向迭代器提問，迭代器需要有回答的能力，標準規(guī)定迭代器必須有下面5種必須的能力

template<typename _Tp>
struct _List_iterator
{
    typedef std::bidirectional_iterator_tag iterator_category;    // 迭代器類別（輸入、輸出、正向、雙向、隨機訪問迭代器）
    typedef _Tp  value_type;    // 值的類型
    typedef _Tp* pointer;    
    typedef _Tp& reference;    
    typedef ptrdiff_t difference_type;    // 容器種兩個元素的距離，比如unsigned long
    // ...
};

五種迭代器（使用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 bidirectional_iterator_tag {};

注意迭代器begin()指向第一個元素，end()指向最后一個元素。迭代器rbegin()和rend()實現(xiàn)比較巧妙

reverse_iterator rbegin() {
    return reverse_iterator(end());
}

reverse_iterator rend() {
    return reverse_iterator(begin());
}

4.2 Iterator Traits

　　理想情況下iterator應該具備以上5種能力，實際應用中，最基本的指針也是一種退化的迭代器，他不是一個類，沒辦法描述自己的能力，所以有必要提出一種概念：Iterator Traits迭代器的萃取器，來描述該指針具有的迭代器的特征。

　　在初始的情況下，算法直接調(diào)用傳入的類來詢問它具有哪些能力，但如果傳入的是一個普通的指針就會失效。這里引入一個中間層來解決該問題，該中間層就是Iterator Traits。算法通過詢問中間層來獲取這些信息，這也是一種編程思想。

　　具體實現(xiàn)中非常巧妙的利用了偏特化的特性。首先看下圖最下方的代碼，算法調(diào)用iterator_traits并傳入I來詢問該迭代器對應的變量類型是什么。

如果I是一個iterator類，則會調(diào)用第1種全泛化的方法，并且返回該iterator中的類型
如果I是一個指針，則會進入第2種偏特化的方法，然后返回這個指針的類型
如果I是一個const指針，則進入第3種偏特化方法，這樣算法中拿到的類型才不會是一個 const T 類型，否則就沒辦法操作這些值了

　　下圖展現(xiàn)了完整的 iterator traits

4.3 iterator_category 分類對算法的影響

4.3.1 distance

　　STL中計算distance利用了函數(shù)重載的特性。__distance返回兩個指針間的距離，通過第三個參數(shù)可以實現(xiàn)函數(shù)重載

如果該迭代器支持隨機訪問，則第三個參數(shù)category()會實例化一個右值，并且是random_access_iterator_tag類型，此時編譯器會調(diào)用第二個重載方法
如果該迭代器不支持隨機訪問，則第三個參數(shù)是普通的input_iterator_tag類型，此時調(diào)用第一個重載方法，一點一點移動指針計算距離

template<class InputIterator>
inline iterator_traits<InputIterator>::difference_type
__distance(InputIterator first, InputIterator last, input_iterator_tag){
    iterator_traits<InputIterator>::difference_type n=0;
    while(first!=last)
    {    ++first; ++n;}
    return n;
}

template<class RandomAccessIterator>
inline iterator_traits<RandomAccessIterator>::difference_type
__distance(RandomAccessIterator first, RandomAccessIterator last, random_access_iterator_tag){
    return last-first;
}

template<class InputIterator>
inline iterator_traits<InputIterator>::difference_type
distance(InputIterator first, InputIterator last){
    typedef typename iterator_traits<InputIterator>::iterator_category category;
    return __distance(first, last, category()):
}

4.3.2 copy

　　copy函數(shù)，給定來源的起點和終點，并給定目標就可以實現(xiàn)復制，但實際上內(nèi)部實現(xiàn)非常復雜

如果傳入的迭代器類型是字符指針，則執(zhí)行memmove()函數(shù)進行拷貝，速度很快
否則進入泛化的函數(shù)__copy_dispatch()
- 如果是指針類型的迭代器，則執(zhí)行__copy_t()
  - 如果拷貝指針時需要調(diào)用拷貝構(gòu)造器單獨處理（重寫了復制構(gòu)造函數(shù)）
  - 如果不需要調(diào)用拷貝構(gòu)造器則直接調(diào)用memmove()
- 否則進入泛化的函數(shù)__copy()
  - 如果是普通的迭代器，則以iterator是否相等來判斷是否到迭代器終點，速度較慢
  - 如果是隨機訪問迭代器，則用循環(huán)次數(shù)判斷是否循環(huán)結(jié)束，速度快一些

template<class InputIterator, class OutputIterator>
OutputIterator copy(InputIterator first, InputIterator last, OutputIterator result){
    while(first!=last){
        *result = *first;
        ++result; ++first;
    }
    return result;
}

4.3.3 源碼對迭代器的暗示

　　在算法中，由于是模板函數(shù)，所以寫代碼的時候編譯器不會報錯，但是編譯中因為底層需要某種迭代器的功能來完成這個函數(shù)，所以編譯到這一步時會出現(xiàn)問題。算法源碼中會對這些迭代器用命名的方式進行暗示。例如下面暗示了需要容器有隨機訪問迭代器或前向迭代器

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 ForwardIterator>
inline void rotate(ForwardIterator first, ForwardIterator middle, ForwardIterator last){
    if(first == middle || middle == last) return;
    __rotate(first, middle, last, distance_type(first), iterator_category(first));
}

4.3.4 STL中的算法

　　STL中所有的算法都是如下類型，前兩個參數(shù)提供迭代器

template<typename Iterator>
std::Algorithm(Iterator itr1, Iterator itr2, ...)
{
}

　　STL中提供的算法一般都有兩種重載，一種是普通的調(diào)用，另一種提供給用戶自定義的處理方式。可以自定一個函數(shù)或者函數(shù)對象傳入

template<class InputIterator, class T>
T accumulate(InputIterator first, InputIterator last, T init)
{
    for(; first!=last; ++first)
        init = init + *first;
    return init;
}

template<class InputIterator, class T, class BinaryOperation>
T accumulate(InputIterator first, InputIterator last, T init, BinaryOperation binary_op)
{
    for(; first!=last; ++first)
        init = binary_op(init, *first);    // 普通的函數(shù)或者函數(shù)對象都可以被調(diào)用
    return init;
}

5.仿函數(shù)和適配器

5.1 仿函數(shù)functors

　　4.3.4小節(jié)中提到了算法允許用戶自定義處理方式，自定義函數(shù)或函數(shù)對象（仿函數(shù)）傳入

　　注意標準庫提供的仿函數(shù)都繼承了一個父類，而我們自己寫的仿函數(shù)沒有繼承，沒有繼承實際上就沒有融入STL的體系結(jié)構(gòu)

template<class T>
struct plus : public binary_function<T, T, T> {
    T operator()(const T&x, cont T&y) const
        {return x+y;}
}

struct equal_to : public binary_function<T, T, bool>{
    bool operator()(const T&x, const T&y) const
        {return x==y;}
}

　　標準庫提供了兩個仿函數(shù)的可適配（adaptable）條件，STL規(guī)定所有的可適配函數(shù)都應該繼承其中之一。下面一節(jié)介紹了為什么適配器必須能夠回答這些問題，因為有些函數(shù)會向仿函數(shù)提出問題，這和萃取器非常類似

// 一個操作數(shù)
template<class Arg, class Result>
struct unary_function {
    typedef Arg argument_type;
    typedef Result result_type;
}

// 兩個操作數(shù)
template<class Arg1, class Arg2, class Result>
struct binary_function{
    typedef Arg1 first_argument_type;
    typedef Arg2 second_argument_type;
    typedef Result result_type;
}

5.2 適配器Adapters

　　仿函數(shù)適配器的例子。count_if函數(shù)會調(diào)用第三個仿函數(shù)并傳入迭代器當前指針的位置，但是less函數(shù)需要傳入兩個值并返回bool值，在這里count_if的調(diào)用只能傳入一個值，可以使用函數(shù)適配器bind2nd來完成這個想法，bind2nd函數(shù)對象實際上包裝了less函數(shù)對象，它需要傳入一個函數(shù)對象（包含括號重載的處理邏輯），以及第二個值。

　　它將less函數(shù)對象保存到自己的字段中，并在每次調(diào)用bind2nd函數(shù)對象時，第一個參數(shù)是count_if傳入的當前迭代器位置，而第二個位置是bind2nd初始化時傳入的第二個參數(shù)，這樣實現(xiàn)了在count_if中調(diào)用兩個參數(shù)的函數(shù)對象

　　這期間，都是通過適配器完成的這一系列操作。bind2nd需要去問函數(shù)對象它的第二個參數(shù)類型是什么，binder2nd需要去問函數(shù)對象它的第返回值類型是什么，這些都是需要適配器完成的。并且在bind2nd函數(shù)對象創(chuàng)建binder2nd函數(shù)對象時，由于存在強制類型轉(zhuǎn)換，實際上編譯器會進行一些檢查，如果這里不能轉(zhuǎn)換就會編譯失敗。

int main() {
    vector<int> vi = { 40, 50, 20, 11, 23, 88, 99 };
    cout << count_if(vi.begin(), vi.end(), bind2nd(less<int>(), 40);
}
// count_if 中調(diào)用第三個仿函數(shù) _Pred, 僅傳入當前迭代器的位置
for (; _UFirst != _ULast; ++_UFirst) {
    if (_Pred(*_UFirst)) {
        ++_Count;
    }
}

// bind2nd 輔助函數(shù), 方便用戶調(diào)用 binder2nd<Op>
template<class Operation, class T>
inline binder2nd<Operation> bind2nd(const Operation& op, const T&x) {
    typedef typename Operation::second_argument_type arg2_type;    // 問適配器函數(shù)對象的第二個參數(shù)是什么類型
    return binder2nd<Operation>(op, arg2_type(x));    // 將函數(shù)對象和強制類型轉(zhuǎn)換的第二個參數(shù)構(gòu)造出 binder2nd 對象
}

// binder2nd
template<class Operation>
class binder2nd : public unary_function<typename Operation::first_argument, typename Operation::result_tpye> { ·
protected:
    Operation op;    // 函數(shù)對象本身, 實際上的操作邏輯
    typename Operation::second_argument_type value;
public:
    // 構(gòu)造函數(shù), 將函數(shù)對象和第二參數(shù)傳入
    binder2nd(const Operation& x, const typename Operation::second_argument_type& y) : op(x), value(y) {}
    // 返回值類型是函數(shù)對象的返回值類型, 第二參數(shù)是綁定的參數(shù), 然后調(diào)用函數(shù)對象的括號重載
    typename Operation::result_type operator() (const typename OPeration::first_argument_type &x) const {
        return op(x, value);
    }
};

　　接下來我們?nèi)钥梢岳^續(xù)使用not1函數(shù)將他返回的bool值取反，原理也是類似的，實現(xiàn)很巧妙

template<class Predicate>
inline unary_negate<Predicate> not1(const Predicate& pred) {
    return unary_negate<Predicate>(pred);
}

template<class Predicate>
class unary_negate : unary_function<typename Predicate::argument_type, bool> {
protected:
    Predicate pred;
public:
    explicit unary_negate(const Predicate& x) : pred(x) {}
    bool operator() (const typename Predicate::argument_type&x) const {
        return !pred(x);
    }
};

5.3 C++11 bind

　　在新版本的C++11中，有新的適配器bind，比之前的更高級。可以綁定函數(shù)

using namespace std::placeholders;    // 占位符 _1, _2, _3, ...

double my_divide(double x, double y)
    { return x/y; }

auto fn_five = bind(my_divide, 10, 2);
cout<< fn_five() << endl;    // 5

auto fn_five = bind(my_divide, _1, 2);
cout<< fn_five(10) << endl;    // 5

auto fn_five = bind(my_divide, _2, _1);
cout<< fn_five(10, 2) << endl;    // 2/10 = 0.2 它交換了位置

auto fn_five = bind<int>(my_divide, _1, _2);
cout<< fn_five(10, 3)<< endl;    // 3（返回值類型為int）

　　同時也可以綁定函數(shù)對象、成員函數(shù)甚至成員變量

struct MyPair {
    double a,b;
    double multiply() {return a*b; }
};

MyPair ten_two {10, 2};

auto bound_menfn = bind(&MyPair::multiply, _1);
cout << bound_memfn(ten_two) << endl;    // 綁定成員函數(shù), 輸出20

auto bound_memdata = bind(&MyPair::a, ten_two);
cout << bound_memdata() <<endl;    // 綁定成員變量a, 輸出 10

5.4 inserter 迭代器適配器

　　copy在算法中已經(jīng)寫死了，他的復制方式就是給定源的開始和終止目標，然后用覆蓋的方式復制到目標位置

　　但是如果我們希望用插入的方式呢？copy函數(shù)不能修改，他就是不斷移動指針和賦值的操作

list<int> foo = {1, 2, 3, 4, 5};
list<int> bar = {10, 20, 30, 40, 50};

list<int>iterator it = foo.begin();
advance(it, 3);    // 很底層的代碼, 讓迭代器移動3個位置

copy(bar.begin(), bar.end(), inserter(foo, it));

　　下面給出了copy中的核心代碼部分

// copy中的核心代碼
while(first!=last) {
    *result = *first;
    ++result; ++first;
}

　　開發(fā)人員非常巧妙的利用了運算符重載，將=運算符重載為insert插入函數(shù)，解決了這個問題

// 輔助函數(shù), 幫助用戶使用
template <class Container, class Iterator>
inline insert_iterator<Container> insert(Container& x, Iterator i) {
    typedef typename Container::iterator iter;
    return insert_iterator<Container>(i);
}

// 實際函數(shù), 重載運算符在調(diào)用insert函數(shù)
template<class Container>
class insert_iterator {
protected:
    Container* container;
    typename Container::iterator iter;
public:
    typedef output_iterator_tag iterator_category;

    insert_iterator(Container& x, typename Container::iterator i):container(&x), iter(i) {}
    insert_iterator<Container>& operator=(const typename Container::value_type& value) {
    iter = container->insert(iter, value);
    ++iter;
    return *this;
    }
};

6 array和deque例子

以array作為例子（GNU2.9），該容器的實現(xiàn)中，迭代器 iterator 就是一個普通的指針，接下來進入針對指針的萃取機中

template<typename _Tp, std::size_t _Nm>
struct array
{
    typedef _Tp    value_type;
    typedef _Tp*   pointer;
    typedef value_type* iterator;    // 直接將指針定義成迭代器, 接下來算法中的萃取器會通過偏泛化獲取其能力
    
    value_type _M_instance[_Nm ? _Nm : 1];
    
    iterator begin()
    { return iterator(&_M_instance[0]); }
    
    iterator end()
    { return iterator(&_M_instance[_Nm]); }
}

以deque雙端隊列為例子（GNU2.9），這里的 iterator 有很多復雜的動作，所以需要額外的定義該迭代器類來完成這些動作
deque底層維護了一個map數(shù)組，這個數(shù)組指向了幾個分段數(shù)組。deque的迭代器類重寫了++、--、*等運算符，并且自動從一個分段數(shù)組進入另一個分段數(shù)組，制造連續(xù)假象
cur：當前遍歷的元素
first：當前片段的首地址
last：當前片段的尾地址
node：二級指針，指向map中的指針，該指針指向當前內(nèi)存地址
map數(shù)組擴充時，如從8擴充到16的時候，會把map復制到新的map的中間部分，讓左右都有冗余

template <class T, class Alloc=alloc, size_t BufSiz=0>    // 每一段buffer的大小, 新版本不能自己設置了
class deque {
public:
    typedef T value_type;
    typedef __deque_iterator<T, T&, T*, BufSiz> iterator;
protected:
    typedef pointer* map_pointer;    // T** 指向指針的指針
protected:
    iterator start;
    iterator finish;
    map_pointer map;
    size_type map_size;
public:
    iterator begin() { return start;}
    iterator end() { return finish; }
    size_type size() const { return finish - start; }
    // ...
}

stack 棧后進先出和 queue 先進先出都是 deque 的部分功能。但注意，stack 和 queue 都是特殊的容器，他們有特殊的性質(zhì)，所以沒有迭代器，也不允許遍歷
- queue<typename _Tp, typename _Container = deque> 隊列可以人為配置第二個部分容器是什么，也就是內(nèi)存片段使用什么存儲
- 因為要調(diào)用pop函數(shù)，這里如果使用deque或者stack都是可以的，但是如果使用vector、map、set都會有問題（編譯可能通過，但是pop()會error，它們沒有這種功能）

posted @ 2024-02-28 16:08 cear 閱讀(92) 評論(0) 收藏舉報

刷新頁面返回頂部

imXuan

xduer@qq.com