c++ vector模擬實現的全過程

Posted on by

一、vector是什麼？

vector是表示可變大小數組的序列容器，它也采用連續存儲空間來存儲元素，因此可以采用下標對vector的元素進行訪問，它的大小是動態改變的，vector使用動態分配數組來存儲它的元素；

二、容器特性

1.順序序列

順序容器中的元素按照嚴格的線性順序排序。可以通過元素在序列中的位置訪問對應的元素;

2.動態數組

支持對序列中的任意元素進行快速直接訪問，甚至可以通過指針進行該操作。操供瞭在序列末尾相對快速地添加/刪除元素的操作;

3.能夠感知內存分配器的

容器使用一個內存分配器對象來動態地處理它的存儲需求;

三、vector的模擬實現

定義一個類：

template<class T>
class Vector
{
    T* _start; //首元素地址
    T* _finish; //最後一個元素地址的下一個地址
    T* _endOfStorage; //空間的尾地址
public：
//成員函數
};

構造函數

Vector()
    :_start(nullptr)
    , _finish(nullptr)
    , _endOfStorage(nullptr)
{}

Vector(size_t n, const T& value = T())
    :_start(nullptr)
    , _finish(nullptr)
    , _endOfStorage(nullptr)
{
    reserve(n);
    while (n--)
    {
        push_back(value);
    }
}
Vector(InputInterator first, InputInterator last)
        :_start(nullptr)
        , _finish(nullptr)
        , _endOfStorage(nullptr)
    {
        while (first != last)
        {
            pushBack(*first);
            ++first;
        }
    }

數據大小、空間大小

size_t size() const
{
    return _finish - _start;
}

size_t capacity() const
{
    return _endOfStorage - _start;
}

尾插

void pushBack(const T& value)
    {
        if (_finish == _endOfStorage)
        {
            size_t newC = _endOfStorage == nullptr ? 1 : 2 * capacity();
            reverse(value);
        }
        *_finish = value;   
        ++_finish;
    }

擴容

有資源進行拷貝時，使用深拷貝；類型為自定義類型時，發生淺拷貝，調用自定義類型析構函數，釋放資源，導致資源二次釋放，所以自定義類型的拷貝有資源時進行深拷貝；

深拷貝與淺拷貝的區別及應用 

void reserve(size_t n)
{
if (n &gt; capacity())
{
size_t sz = size();
T* arr = new T[n];
if (_start)
{
memcpy(arr, _start, sizeof(T) * sz);
delete[] _start;
}
//update
_start = arr;
_finish = _start + sz;
_endOfStorage = _start + n;
}
}

改變數據大小

void resize(size_t n, const T& val = T())
    {
        if (n > capacity())
        {
            reserve(n);
        }
        else if (n > size())
        {
            while (_finish != _start + n)
            {
                *_finish = val;
                _finish++;
            }
        }
            _finish = _start + n;
    }

位置插入值

void insert(iterator pos, const T& val)
    {
        size_t sz = pos - _start;
        //檢查位置
        if (pos >= _start && pos <= _finish)
        {
            //檢查容量
            if (_finish == _endOfStoage)
            {
                size_t n = _endOfStorage == nullptr ? 1 : 2 * capacity();               
                reserve(n);
                //更新迭代器
                pos = _start + sz;
            }
            //移動元素
            iterator end_u = _finish;
            while (end_u != pos)
            {
                *end = *(end_u - 1);
                --end_u();
            }
            //插入元素
            *pos = val;
            //更新位置
            ++_finish;
        }
    }

刪除數據

iterator erase(iterator pos)
    {
        //檢查位置
        if (pos < _finish && pos >= _start)
        {
            //移動元素
            iterator start = pos + 1;
            while (start!=_finish)
            {
                *(start - 1) = *start;
                start++;
            }
            //更新
            --_finish;
        }
        return pos;
    }
    //返回刪除數據的下一個元素的位置

operator[] 重載

T& operator[](size_t pos)
    {
        if (pos >= 0 && pos < size())
            return _start[pos];
    }

operator= 重載

    Vector<T>& operator=(const Vector<T>& v)
    {
        if (this != &v)
        {
            delete[]_start;
            size_t n = v.capacity();
            _start = new T[n];
            for (size_t i = 0; i < v.capacity(); ++i)
            {
                _start[i] = v._start[i];
            }
            _finish = _start + v.size();
            _finish = _start + n;
        }
        return *this;
    }

迭代器

//vector迭代器：T*
typedef T* iterator;
typedef const T* const_iterator;

iterator begin()
{
    return _start;
}

iterator end()
{
    return _finish;
}

const_iterator begin() const
{
    return _start;
}

const_iterator end() const
{
    return _finish;
}

析構函數

~Vector()
{
    if (_start)
    {
        delete[] _start;
        _start = _finish = _endOfStorage = nullptr;
    }
}

總結

到此這篇關於c++ vector模擬實現的文章就介紹到這瞭,更多相關c++ vector模擬實現內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！

推薦閱讀：

    None Found