C++ STL vector的模擬實現(xiàn)

更新時間：2021年05月07日 11:08:19 投稿：zx

這篇文章主要介紹了C++ STL vector的模擬實現(xiàn),文中通過示例代碼介紹的非常詳細，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧

1. vector的介紹和使用

vector是表示可變大小數(shù)組的序列容器。
就像數(shù)組一樣，vector也采用的連續(xù)存儲空間來存儲元素。也就是意味著可以采用下標對vector的元素進行訪問，和數(shù)組一樣高效。但是又不像數(shù)組，它的大小是可以動態(tài)改變的，而且它的大小會被容器自動處理。
本質(zhì)講，vector使用動態(tài)分配數(shù)組來存儲它的元素。當(dāng)新元素插入時候，這個數(shù)組需要被重新分配大小為了增加存儲空間。其做法是，分配一個新的數(shù)組，然后將全部元素移到這個數(shù)組。就時間而言，這是一個相對代價高的任務(wù)，因為每當(dāng)一個新的元素加入到容器的時候，vector并不會每次都重新分配大小。
vector分配空間策略：vector會分配一些額外的空間以適應(yīng)可能的增長，因為存儲空間比實際需要的存儲空間更大。不同的庫采用不同的策略權(quán)衡空間的使用和重新分配。但是無論如何，重新分配都應(yīng)該是對數(shù)增長的間隔大小，以至于在末尾插入一個元素的時候是在常數(shù)時間的復(fù)雜度完成的。
因此，vector占用了更多的存儲空間，為了獲得管理存儲空間的能力，并且以一種有效的方式動態(tài)增長。
與其它動態(tài)序列容器相比（deques, lists and forward_lists）， vector在訪問元素的時候更加高效，在末尾添加和刪除元素相對高效。對于其它不在末尾的刪除和插入操作，效率更低。比起lists和forward_lists統(tǒng)一的迭代器和引用更好。

更為詳細的可以查看vector文檔介紹。

2. vector的模擬實現(xiàn)

vector的嵌套型別定義

typedef _Ty         value_type;
typedef value_type* iterator;
typedef value_type& reference;
typedef size_t      size_type;

vector的成員變量

private:
        iterator _start;
        iterator _last;
        iterator _end;

2.1 vector構(gòu)造函數(shù)和拷貝構(gòu)造函數(shù)

vector():_start(nullptr),_last(nullptr),_end(nullptr)
{}
vector(size_type n,const _Ty& value):_start(nullptr),_last(nullptr),_end(nullptr)
{
     insert(n,value);
}
vector(iterator f,iterator l):_start(nullptr),_last(nullptr),_end(nullptr)
{
     insert(f,l);
}   
vector(const vector<int>& iv)
{
        reserve(iv.capacity());
        iterator it = begin();
        iterator vit = iv.end();
        while (vit != iv.begin())
        {
              *it++ = *vit--;     
        }
}

2.2 insert函數(shù)和eraser函數(shù)

iterator insert(iterator pos,const _Ty& value)
{
    //1.當(dāng)size()==capacity()時，表明vector已滿，再進行插入前需要進行擴容
    if(size()== capacity())
    {
        size_type oldpos = pos - begin();
        //這里需要防止一種情況：若vector為空的時候，他的capacity為0，這個時候給他直接擴容2倍是行不通的，
        //因為2*0 = 0，因此就需要進行判斷 
        size_type newcapacity = (capacity() == 0)? 1 : 2*capacity();

        reserve(newcapacity);

        //這里空間發(fā)生了變化，pos迭代器會失效，因此需要重新對pos進行設(shè)置
        //reserve不會使vector的成員變量失效
        pos = begin() + oldpos;
    }
    //2.當(dāng)size() < capacity()時，表明vector未滿，插入直接在pos的位置進行插入
    //需要注意的是插入是在pos指向的位置進行插入，并且插入需要挪動數(shù)據(jù)，
    //將pos位置之后的數(shù)據(jù)全部向后挪動一個,為防止元素被改寫，則需要從后向前進行挪動
    iterator tail = _last;
    while(tail > pos)
    {
        *tail = *(tail-1);
        --tail;
    }
    //這里要注意的是挪動數(shù)據(jù)時，因為沒有對pos位置進行操作，所以pos位置的迭代器并沒有失效，
    //但是pos位置之后的迭代器全部失效了，但在這里并沒有關(guān)系，我們并不會用到那些迭代器
    *pos = value;

    //插入完之后，一定要對_last指針+1，因為全部向后挪動了一個元素
    ++_last;

    return pos;
}

void insert(size_type n,const _Ty& value)
{
    for(int i = 0;i < n; ++i)
    {
        insert(end(),value);
    }
}
void insert(iterator f,iterator l)
{
    while(f!=l)
    {
        insert(end(),*f);
        ++f;
    }
}


iterator erase(iterator pos)
{
    assert(pos >= _start || pos < _last);
    //1.刪除pos位置的元素，就是將[pos,end()]這個區(qū)間向前挪動一個即可
    iterator it = pos + 1;
    while(it != _last)
    {
        *(it-1) = *(it);
        ++it;
    }

    --_last;
    return pos;
}

2.3 reserve函數(shù)和resize函數(shù)

void reserve(size_type n)
{
    //若 n 的值大于vector的容量，則開辟空間
    //若 n 的值小于等于，則不進行任何操作
    if(n > capacity())
    {
        //1.新開辟一個空間
        size_type oldSize = size();
        _Ty* newVector = new _Ty[n];
        //2.將原空間的數(shù)值賦值到新空間
        if(_start)
        {
            //注意：這里不能使用memcpy,因為memcpy是一個淺拷貝。
            //memcpy(newVector,_start,sizeof(_Ty)*size());
            for(size_type i = 0; i < oldSize; ++i)
            {
                newVector[i] = _start[i];
            }
        }
        //3.改變?nèi)齻€指針的指向
        //這里直接重新給三個成員進行賦值，所以調(diào)用reserve()函數(shù)不用擔(dān)心迭代器失效的問題
        _start = newVector;
        _last = _start + oldSize;
        _end = _start + n;
    }
}

void resize(size_type n,const _Ty& value = _Ty())
{
    //1.如果n的值小于等于size()的時候，則只需要將_last的指針往前移動即可
    if(n <= size())
    {
        _last = _start + n;
        return;
    }
    //2.如果n的值大于capacity()的時候，則需調(diào)用reserve()函數(shù)，重新設(shè)置容量大小
    if(n > capacity())
    {
        reserve(n);
    }
    //若當(dāng)n的值大于size()而小于capacity()的時候，只需將_last的指針往后移即可

    iterator it = _last;
    _last = _start + n;

    while(it != _last)
    {
        *it = value;
        ++it;
    }
    //resize()函數(shù)也不需要擔(dān)心迭代器失效的問題
}

2.4 push_back函數(shù)和pop_back函數(shù)

void push_back(const _Ty& value)
{
    insert(end(),value);
}
void pop_back()
{
    erase(end()-1);
}

2.5 begin函數(shù)和end函數(shù)

iterator begin()const
{
    return _start;
}
iterator end() const
{
    return _last;
}

2.6 size函數(shù)、capacity函數(shù)

size_type size()
{
    return end()-begin();
}
size_type capacity()const
{
    return _end-begin();
}

2.7 empty函數(shù)和operator[]重載

bool empty()const
{
    return end() == begin();
}

reference operator[](size_type n)
{
    return *(begin() + n);
}

2.8 完整代碼和相應(yīng)測試

#include <iostream>
#include <assert.h>

using namespace std;


namespace mytest{
    template<class _Ty>
    class vector
    {
        public:
            typedef _Ty         value_type;
            typedef value_type* iterator;
            typedef value_type& reference;
            typedef size_t      size_type;
        public:
            iterator begin()const
            {
                return _start;
            }
            iterator end() const
            {
                return _last;
            }
            size_type size()
            {
                return end()-begin();
            }
            size_type capacity()const
            {
                return _end-begin();
            }
            bool empty()const
            {
                return end() == begin();
            }
            reference operator[](size_type n)
            {
               return *(begin() + n); 
            }

        public:
            vector():_start(nullptr),_last(nullptr),_end(nullptr)
            {}
            vector(size_type n,const _Ty& value):_start(nullptr),_last(nullptr),_end(nullptr)
            {
                insert(n,value);
            }
            vector(iterator f,iterator l):_start(nullptr),_last(nullptr),_end(nullptr)
            {
                insert(f,l);
            }   
            vector(const vector<int>& iv)
            {
                reserve(iv.capacity());
                iterator it = begin();
                iterator vit = iv.end();
                while (vit != iv.begin())
                {
                    *it++ = *vit--;     
                }
            }
        public:
            void reserve(size_type n)
            {
                //若 n 的值大于vector的容量，則開辟空間
                //若 n 的值小于等于，則不進行任何操作
                if(n > capacity())
                {
                    //1.新開辟一個空間
                    size_type oldSize = size();
                    _Ty* newVector = new _Ty[n];
                    //2.將原空間的數(shù)值賦值到新空間
                    if(_start)
                    {
                        //注意：這里不能使用memcpy,因為memcpy是一個淺拷貝。
                        //memcpy(newVector,_start,sizeof(_Ty)*size());
                        for(size_type i = 0; i < oldSize; ++i)
                        {
                            newVector[i] = _start[i];
                        }
                    }
                    //3.改變?nèi)齻€指針的指向
                    //這里直接重新給三個成員進行賦值，所以調(diào)用reserve()函數(shù)不用擔(dān)心迭代器失效的問題
                    _start = newVector;
                    _last = _start + oldSize;
                    _end = _start + n;
                }
            }

            void resize(size_type n,const _Ty& value = _Ty())
            {
                //1.如果n的值小于等于size()的時候，則只需要將_last的指針往前移動即可
                if(n <= size())
                {
                    _last = _start + n;
                    return;
                }
                //2.如果n的值大于capacity()的時候，則需調(diào)用reserve()函數(shù)，重新設(shè)置容量大小
                if(n > capacity())
                {
                    reserve(n);
                }
                //若當(dāng)n的值大于size()而小于capacity()的時候，只需將_last的指針往后移即可
                
                iterator it = _last;
                _last = _start + n;

                while(it != _last)
                {
                    *it = value;
                    ++it;
                }
                //resize()函數(shù)也不需要擔(dān)心迭代器失效的問題
            }

            void push_back(const _Ty& value)
            {
                insert(end(),value);
            }
            void pop_back()
            {
                erase(end()-1);
            }

            

            iterator insert(iterator pos,const _Ty& value)
            {
                //1.當(dāng)size()==capacity()時，表明vector已滿，再進行插入前需要進行擴容
                if(size()== capacity())
                {
                    size_type oldpos = pos - begin();
                    //這里需要防止一種情況：若vector為空的時候，他的capacity為0，
                    //這個時候給他直接擴容2倍是行不通的，因為2*0 = 0，因此就需要進行判斷 
                    size_type newcapacity = (capacity() == 0)? 1 : 2*capacity();

                    reserve(newcapacity);

                    //這里空間發(fā)生了變化，pos迭代器會失效，因此需要重新對pos進行設(shè)置
                    //reserve不會使vector的成員變量失效
                    pos = begin() + oldpos;
                }
                //2.當(dāng)size() < capacity()時，表明vector未滿，插入直接在pos的位置進行插入
                //需要注意的是插入是在pos指向的位置進行插入，并且插入需要挪動數(shù)據(jù)，
                //將pos位置之后的數(shù)據(jù)全部向后挪動一個,為防止元素被改寫，則需要從后向前進行挪動
                iterator tail = _last;
                while(tail > pos)
                {
                    *tail = *(tail-1);
                    --tail;
                }
                //這里要注意的是挪動數(shù)據(jù)時，因為沒有對pos位置進行操作，所以pos位置的迭代器并沒有失效，
                //但是pos位置之后的迭代器全部失效了，但在這里并沒有關(guān)系，我們并不會用到那些迭代器
               *pos = value;

               //插入完之后，一定要對_last指針+1，因為全部向后挪動了一個元素
               ++_last;

               return pos;
            }

            void insert(size_type n,const _Ty& value)
            {
                for(int i = 0;i < n; ++i)
                {
                    insert(end(),value);
                }
            }
            void insert(iterator f,iterator l)
            {
                while(f!=l)
                {
                    insert(end(),*f);
                    ++f;
                }
            }


            iterator erase(iterator pos)
            {
                assert(pos >= _start || pos < _last);
                //1.刪除pos位置的元素，就是將[pos,end()]這個區(qū)間向前挪動一個即可
                iterator it = pos + 1;
                while(it != _last)
                {
                    *(it-1) = *(it);
                    ++it;
                }

                --_last;
                return pos;

            }

 

            

        private:
            iterator _start;
            iterator _last;
            iterator _end;
    };

};

void Test1()
{
    mytest::vector<int> iv;

    cout << "iv.size() = " << iv.size() << endl;
    cout << "iv.capacity() = " << iv.capacity() << endl;
    iv.push_back(1);
    iv.push_back(2);
    iv.push_back(3);
    iv.push_back(4);
    cout << "iv.size() = " << iv.size() << endl;
    cout << "iv.capacity() = " << iv.capacity() << endl;

    mytest::vector<int>::iterator it = iv.begin();

    while(it != iv.end())
    {
        cout << *it << " ";
        ++it;
    }
    cout << endl;
    iv.pop_back();
    iv.pop_back();
    it = iv.begin();
    while(it != iv.end())
    {
        cout << *it << " ";
        ++it;
    }
    cout << endl;


}

void Test2()
{
    mytest::vector<int> iv(10,2); 
    mytest::vector<int>::iterator it = iv.begin();
    while(it != iv.end())
    {
        cout << *it << " ";
        ++it;
    }
    cout << endl;
}

void Test3()
{
    int ar[] = {1,2,3,3,4,5};
    mytest::vector<int> iv(ar,ar+6);
    mytest::vector<int>::iterator it = iv.begin();
    while(it != iv.end())
    {
        cout << *it << " ";
        ++it;
    }
    cout << endl;

}
int main()
{
//    Test1();
//    Test2();
    Test3();
    return 0;
}

到此這篇關(guān)于C++ STL vector的模擬實現(xiàn)的文章就介紹到這了,更多相關(guān)C++ STL vector內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: