欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

詳解C++ STL中vector擴容機制

 更新時間：2024年03月28日 09:51:47   作者：number=10086  
vector是表示可以改變大小的數組的序列容器,就像數組一樣,vector對其元素使用連續(xù)的存儲位置,這篇文章將給大家詳細介紹C++ STL中vector擴容機制,文中通過代碼示例介紹的非常詳細,需要的朋友可以參考下

vector是STL提供的動態(tài)數組，它會在內部空間不夠用時動態(tài)的調整自身的大小，調整過程中會有大量的數據拷貝，為了減少數據拷貝的次數vector會在調整空間的時候盡量多申請一些空間，這些預留出的空間可以很大程度上減少拷貝的發(fā)生。

在windows環(huán)境中使用vs運行這段代碼

#include<iostream>
#include<vector>
using namespace std;
void fun(vector<int>&vec){
	vec.push_back(1);
    cout<<&vec[0]<<vec.size()<<" "<<vec.capacity()<<endl;
}
int main(){
    vector<int>vec;
    for(int i=0;i<10;i++) fun();
}

打印內容依次為，首元素地址，已經使用的空間，容器的容量

首先看push_back源碼，第一個拷貝版本，第二個移動版本，需要注意的是這里第二個不是萬能引用而是右值引用，下面看emplace_back代碼

void push_back(const _Ty& _Val) { // insert element at end, provide strong guarantee
        emplace_back(_Val);
    }

    void push_back(_Ty&& _Val) { // insert by moving into element at end, provide strong guarantee
        emplace_back(_STD move(_Val));
    }

emplace_back使用了可變參數，并且對參數使用了萬能引用，從而使得可以在插入節(jié)點時調用對應的構造函數，比如：vector<pair<int,int>>vec；vec.emplace_back(1,2);這么做可以很大程度上簡化代碼的書寫，同時還可以減少一次移動或是拷貝的過程，decltype(auto)這個沒什么說的根據返回值推導返回值類型。

回歸正題，執(zhí)行emplace_back的時候會判斷容量是否充足，size！=capacity的時候會直接加入元素，否則的話會調用_Emplace_reallocate函數進行擴容。

template <class... _Valty>
    decltype(auto) emplace_back(_Valty&&... _Val) {
        // insert by perfectly forwarding into element at end, provide strong guarantee
        auto& _My_data   = _Mypair._Myval2;
        pointer& _Mylast = _My_data._Mylast;
        if (_Mylast != _My_data._Myend) {
            return _Emplace_back_with_unused_capacity(_STD forward<_Valty>(_Val)...);
        }

        _Ty& _Result = *_Emplace_reallocate(_Mylast, _STD forward<_Valty>(_Val)...);
#if _HAS_CXX17
        return _Result;
#else // ^^^ _HAS_CXX17 ^^^ // vvv !_HAS_CXX17 vvv
        (void) _Result;
#endif // _HAS_CXX17
    }

下面看擴容代碼，代碼有點長我直接在代碼上加注釋了

template <class... _Valty>
    pointer _Emplace_reallocate(const pointer _Whereptr, _Valty&&... _Val) {
        // reallocate and insert by perfectly forwarding _Val at _Whereptr
        _Alty& _Al        = _Getal();
        auto& _My_data    = _Mypair._Myval2;//使用的長度
        pointer& _Myfirst = _My_data._Myfirst;//容器開始的位置
        pointer& _Mylast  = _My_data._Mylast;//容器末尾

        _STL_INTERNAL_CHECK(_Mylast == _My_data._Myend); // check that we have no unused capacity

        const auto _Whereoff = static_cast<size_type>(_Whereptr - _Myfirst);//插入元素的位置，這個函數insert也有在用，所以插入的位置不一定在尾部
        const auto _Oldsize  = static_cast<size_type>(_Mylast - _Myfirst);//容器大小

        if (_Oldsize == max_size()) {//長度超過數組的最大長度時報錯
            _Xlength();
        }

        const size_type _Newsize     = _Oldsize + 1;
        const size_type _Newcapacity = _Calculate_growth(_Newsize);//調用擴容函數

        const pointer _Newvec           = _Al.allocate(_Newcapacity);//申請新的空間
        const pointer _Constructed_last = _Newvec + _Whereoff + 1;//計算新的末尾
        pointer _Constructed_first      = _Constructed_last;

        _TRY_BEGIN
        _Alty_traits::construct(_Al, _Unfancy(_Newvec + _Whereoff), _STD forward<_Valty>(_Val)...);//在新的空間添加新的元素
        _Constructed_first = _Newvec + _Whereoff;
		//下面是根據插入元素的位置判斷如何拷貝
        if (_Whereptr == _Mylast) { // at back, provide strong guarantee
            _Umove_if_noexcept(_Myfirst, _Mylast, _Newvec);//移動，不能移動時拷貝
        } else { // provide basic guarantee
            _Umove(_Myfirst, _Whereptr, _Newvec);
            _Constructed_first = _Newvec;
            _Umove(_Whereptr, _Mylast, _Newvec + _Whereoff + 1);
        }
        _CATCH_ALL//拷貝出現異常的時候釋放對應的內容
        _Destroy(_Constructed_first, _Constructed_last);
        _Al.deallocate(_Newvec, _Newcapacity);
        _RERAISE;
        _CATCH_END

        _Change_array(_Newvec, _Newsize, _Newcapacity);//更新數組信息
        return _Newvec + _Whereoff;//偏移到新元素的地址
    }

下面看擴展策略，傳入的_Newsize是_Oldsize + 1，_Max是容器最大容量一般是達不到的我試著輸出了一下我的環(huán)境下是4611686018427387903，可以看到正常情況下新的容量是以前的容量的1.5倍（不同編譯器的擴容策略不一樣，g++中是2），當新的容量還不夠的時候會轉而按需分配。

size_type _Calculate_growth(const size_type _Newsize) const {
        // given _Oldcapacity and _Newsize, calculate geometric growth
        const size_type _Oldcapacity = capacity();
        const auto _Max              = max_size();
        if (_Oldcapacity > _Max - _Oldcapacity / 2) {
            return _Max; // geometric growth would overflow
        }
        const size_type _Geometric = _Oldcapacity + _Oldcapacity / 2;
        if (_Geometric < _Newsize) {
            return _Newsize; // geometric growth would be insufficient
        }
        return _Geometric; // geometric growth is sufficient
    }

需要注意的是resize申請機制是按需分配的，當新的容量大于舊的時候會更新容量大小，當新的大小大于舊的容量的時候只會刪除多余的元素而不會進行拷貝，數組容量不變不會釋放數組空間但是多余的元素會被析構掉，詳情運行下面這段代碼。

#include<iostream>
#include<vector>
using namespace std;

class A {
public:
    A(){}
    int* a = new int(1);
    ~A() { cout << this << "析構"<<endl; }
};

void fun(vector<A>& vec) {
    vec.push_back(A());
    cout << &vec[0] << " " << vec.size() << " " << vec.capacity() << endl;
}
int main() {
    vector<A>vec;
    for (int i = 0; i < 10; i++) fun(vec);
    vec.resize(5);
    cout << vec.capacity()<<endl;
}

以上就是詳解C++ STL中vector擴容機制的詳細內容，更多關于C++ STL vector擴容的資料請關注腳本之家其它相關文章！

相關文章

最新評論