程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> C++ Primer 學習筆記_47_STL剖析(二):vector源碼剖析、內存分配器Allocator

C++ Primer 學習筆記_47_STL剖析(二):vector源碼剖析、內存分配器Allocator

編輯:C++入門知識

C++ Primer 學習筆記_47_STL剖析(二):vector源碼剖析、內存分配器Allocator


一、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++編程規范


  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved