程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> C++ Primer 學習筆記_47_STL剖析（二）：vector源碼剖析、內存分配器Allocator

C++ Primer 學習筆記_47_STL剖析（二）：vector源碼剖析、內存分配器Allocator

編輯：關於C++

一、vector初始化源碼通過跟蹤一個簡單的程序，觀察vector初始化的過程，通過調試單步執行

#include 
#include 
using namespace std;

int main()
{
    vector v;
    return 0;
}

1、首先，執行了代碼

vector() _NOEXCEPT
        : _Mybase()
        {    // construct empty vector
        }

    explicit vector(const _Alloc& _Al) _NOEXCEPT
        : _Mybase(_Al)
        {    // construct empty vector, allocator
        }

2、執行allocator

    allocator() _THROW0()
        {    // construct default allocator (do nothing)
        }

3、進一步執行

    _Vector_alloc(const _Alloc& _Al = _Alloc())
        : _Mypair(_One_then_variadic_args_t(), _Al)
        {    // construct allocator from _Al
        _Alloc_proxy();
        }

4、分配內存，初始化為0，經過一連串的調用，初始化結束

    _Vector_val()
        {    // initialize values
        _Myfirst = pointer();
        _Mylast = pointer();
        _Myend = pointer();
        }

    pointer _Myfirst;    // pointer to beginning of array
    pointer _Mylast;    // pointer to current end of sequence
    pointer _Myend;    // pointer to end of array
    };

二、capacity

1、首先，vector 在VC 2008 中的實現比較復雜，雖然vector 的聲明跟VC6.0 是一致的，如下：

template < class _Ty, class _Ax = allocator<_Ty> > //第二參數是有默認參數的
class vector;

2、但在VC2008 中vector 還有基類，如下：

// TEMPLATE CLASS vector
template < class _Ty,
         class _Ax >
class vector
    : public _Vector_val<_Ty, _Ax>
{
};

3、稍微來看一下基類_Vector_val：

// TEMPLATE CLASS _Vector_val
template < class _Ty,
         class _Alloc >
class _Vector_val
    : public _CONTAINER_BASE_AUX_ALLOC<_Alloc>
{
    // base class for vector to hold allocator _Alval
protected:
    _Vector_val(_Alloc _Al = _Alloc())
        : _CONTAINER_BASE_AUX_ALLOC<_Alloc>(_Al), _Alval(_Al)
    {
        // construct allocator from _Al
    }

    typedef typename _Alloc::template
    rebind<_Ty>::other _Alty;

    _Alty _Alval;   // allocator object for values
};

4、為了理解_Alty 的類型，還得看一下allocator模板類：

template class allocator
{

    template<> class _CRTIMP2_PURE allocator
    {
        // generic allocator for type void
    public:
        template
        struct rebind
        {
            // convert an allocator to an allocator <_Other>
            typedef allocator<_Other> other;
        };
        ....
    };
    ...
};

typedeftypename_Alloc::templaterebind<_Ty>::other_Alty; 整體來看是類型定義，假設現在我們這樣使用vector，那麼_Ty 即 int, _Ax 即 allocator，由vector 類傳遞給基類Vector_val，則_Alloc 即allocator ；可以看到allocator 是allocator模板類的特化，rebind<_Ty>是成員模板類，other是成員模板類中自定義類型，_Ty 即是int ，那麼other 類型也就是allocator，也就是說_Alty 是類型allocator 。_Alty _Alval; 即基類定義了一個allocator 類型的成員，被vector 繼承後以後用於為vector 裡面元素分配內存等操作。

如iteratornew_data =alloc.allocate(new_size); 注意，標准的vector::iterator 是以模板類實現的，下面的實現簡單地將其等同為指針，實際上真正的iterator 類的實現是內部有一個指針成員，指向容器元素。

××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××

對比list 的實現，繼承它的基類_List_nod 的一個成員 allocator<_Node> _Alnod; 如下：

typename _Alloc::template rebind<_Node>::other _Alnod; // allocator object for nodes

其中 _Node有三個成員，如下：

_Nodeptr _Next; // successor node, or first element if head

_Nodeptr _Prev; // predecessor node, or last element if head

_Ty _Myval; // the stored value, unused if head

如果是list ，那麼_Ty 即是int 類型。雙向鏈表在創建一個新結點時，這樣實現：

_Nodeptr _Pnode = this->_Alnod.allocate(1); // 即分配一個節點的空間，返回指向這個節點的指針。

實際上list 還繼承另外兩個基類的兩個成員，如下：

typename _Alloc::template rebind<_Nodeptr>::other _Alptr;// allocator object for pointers to nodes

typename _Alloc::template rebind<_Ty>::other _Alty _Alval; // allocator object for values stored in nodes

×××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××

三、vector動態數組內部如何實現連續空間

1、通過跟蹤一個簡單的程序，觀察vector的capacity分配的過程，通過調試單步執行

#include 
#include 
using namespace std;

int main()
{
    vector v;
    v.push_back(1);
    cout << v.capacity() << endl;
    v.push_back(1);
    cout << v.capacity() << endl;
    v.push_back(1);
    cout << v.capacity() << endl;
    v.push_back(1);
    cout << v.capacity() << endl;
    v.push_back(1);
    cout << v.capacity() << endl;
    v.push_back(1);
    cout << v.capacity() << endl;
    v.push_back(1);
    cout << v.capacity() << endl;
    v.push_back(1);
    cout << v.capacity() << endl;
    return 0;
}

capacity 容量的計算方式如下：容量每次增長為原先容量 + 原先容量 / 2;

增長的源碼跟蹤結果如下：

    size_type _Grow_to(size_type _Count) const
        {    // grow by 50% or at least to _Count
        size_type _Capacity = capacity();

        _Capacity = max_size() - _Capacity / 2 < _Capacity
            ? 0 : _Capacity + _Capacity / 2;    // try to grow by 50%
        if (_Capacity < _Count)
            _Capacity = _Count;
        return (_Capacity);
        }

2、容量跟vector 大小的概念是不一樣的，capacity >= size，如下圖所示：

size 指的是_Mylast - _Myfirst 的區間；capacity 指的是 _Myend- _Myfirst的區間；也就是說存在尚未使用的空間。

當push_back 的時候往往帶有拷貝和析構多個操作，所以一下子分配比size() 大的空間capacity，可以減輕頻繁操作造成的效率問題。

通常，向量緩存了一部分內存空間，用來容納更多的元素，這樣，下一次插入新元素的時候，就不必重新分配內存，提高了插入速度。

四、內存分配器Allocator

allocator 模板類：

#include 
template  class allocator
{
public:
    T *allocate(size_t);
    void deallocate(T *, size_t);
    void construct(T *, size_t);
    void destroy(T *);
    //.......
};

當然實際的接口沒實現沒那麼簡單，但大概實現的功能差不多:

allocate 調用operator new ；deallocate 調用 operator delete; construct 調用placement new （即在分配好的內存上調用拷貝構造函數），destroy 調用析構函數。

參考：

C++ primer 第四版
Effective C++ 3rd
C++編程規范