欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

STL中vector的使用以及模拟实现

程序员文章站 2024-02-11 19:31:40
...

vector:vector是一个动态增长的一个数组,它和数组是非常相似的。
vector与数组的区别在于空间运用的灵活性。
数组是静态空间,一旦配置了就不能改变,如果要增大空间,就需要重新开辟一个更大的空间,把原来数组的元素拷贝进去,然后在把原来的空间释放还给操作系统。
而vector是动态增长的,它会随着元素的增加而增大空间。

下面我们看一下vector的主要函数功能

判断容器的大小

int size() const:返回容器中元素的个数

int capacity() const:返回当前容器所能容纳的最大元素值

int max_size() const:返回最大可允许的vector元素数量值

    vector<int> arr(10, 5);
    //声明一个初始大小为10且值都是5的对象. 

    cout << "该容器元素个数为:" << arr.size() << endl;

    cout << "该容器当前最大容量为:" << arr.capacity() << endl;

    cout << "该容器最大可以允许vector的元素数量为:" << arr.max_size() << endl;

运行结果为:
STL中vector的使用以及模拟实现

初始化

int main()
{
    //声明一个int类型变量 
    vector<int> arr1;  

    //声明一个 初始化大小为5,且值都为10的对象                                      
    vector<int> arr2(5, 10); 

    //用对象arr1的第0个到第2个值初始化arr3;    
    vector<int> arr3(arr1.begin(), arr1.begin() + 3);

    //利用一个vector对象初始化自己
    vector<int> arr4(arr3);            
    return 0;

}

插入删除

int main()
{

    vector<int> arr1;       //声明一个int类型变量  
    //插入
    arr1.push_back(1);
    arr1.push_back(2);
    arr1.push_back(3);
    arr1.push_back(4);

    //输出
    vector<int>::iterator it = arr1.begin();
    while(it != arr1.end())
    {
        cout << *it << " ";
        ++it;
    }
    cout << endl;

    //删除
    arr1.pop_back();
    arr1.pop_back();


    //输出
    vector<int>::iterator it1 = arr1.begin();
    while (it1 != arr1.end())
    {
        cout << *it1 << " ";
        ++it1;
    }
    cout << endl;
    system("pause");
    return 0;

}

输出结果
STL中vector的使用以及模拟实现

resize()和reserve()

这是我们vector中相对重要的函数:

reserve()作用:
vector增容代价太大了,如果已知要插入多少数据就用reserve()。reserve()只改变capacity,但capacity只增加不减小,通过push_back增加size.
reserve()+push_back——顺序插入。

resize()作用:实现初始化(可以不按顺序)
resize()+operator[]:不按顺序初始化。
而resize()改变的是size和capacity,且capacity只增大不减小。

用代码验证一下

vector<int> arr1(5,2);       
    cout << "该容器元素个数为:" << arr1.size() << endl;
    cout << "该容器当前最大容量为:" << arr1.capacity() << endl;


    arr1.reserve(3);//改变capacity
    cout << "该容器元素个数为:" << arr1.size() << endl;
    cout << "该容器当前最大容量为:" << arr1.capacity() << endl;


    arr1.reserve(8);//改变capacity
    cout << "该容器元素个数为:" << arr1.size() << endl;
    cout << "该容器当前最大容量为:" << arr1.capacity() << endl;

运行结果:
STL中vector的使用以及模拟实现
我们可以看到当我们减小capacity时,capacity不变
增大capacity时,capacity增大
所以这是reserve的特点。

下来看一下resize

vector<int> arr1(5,2);
    vector<int>::iterator it = arr1.begin();
    while (it != arr1.end())
    {
        cout << *it << " ";
        ++it;
    }
    cout << "该容器元素个数为:" << arr1.size() << endl;
    cout << "该容器当前最大容量为:" << arr1.capacity() << endl;
    cout << endl;

    arr1.resize(3);
    vector<int>::iterator it1 = arr1.begin();
    while (it1 != arr1.end())
    {
        cout << *it1 << " ";
        ++it1;
    }
    cout << "该容器元素个数为:" << arr1.size() << endl;
    cout << "该容器当前最大容量为:" << arr1.capacity() << endl;
    cout << endl;

    arr1.resize(8,5);//8的位置为5
    vector<int>::iterator it2 = arr1.begin();
    while (it2 != arr1.end())
    {
        cout << *it2 << " ";
        ++it2;
    }
    cout << "该容器元素个数为:" << arr1.size() << endl;
    cout << "该容器当前最大容量为:" << arr1.capacity() << endl;
    cout << endl;

运行结果:
STL中vector的使用以及模拟实现

我们可以看到减小size时capacity不变,而增加size时capacity增大。

模拟实现vector

template <class T>
class Vecter
{
public:
    typedef T* Iterator;
    typedef const T* ConstIterator;
    Vecter()
        :_start(NULL)
        , _finish(NULL)
        , _endofstorage(NULL)
    {}
    inline size_t Size()//有循环调用,写为内联函数,减小开销
    {
        return _finish - _start;
    }
    inline size_t Capacity()
    {
        return _endofstorage - _start;
    }
    Iterator Begin()
    {
        return _start;
    }
    Iterator End()
    {
        return _finish;
    }
    ConstIterator Begin() const
    {
        return _start;
    }

    ConstIterator End() const
    {
        return _finish;
    }


    void Resize(size_t n, const T& val = T())
    {
        if (n > Capacity())
        {
            Expand(n);
        }
        size_t size = Size();
        if (n < size)
        {
            _finish = _start+n;
        }
        else
        {
            for (size_t i = 0; i < n - size; i++)
            {
                PushBack(val);
            }
        }
    }
    void Reserve(size_t n)
    {
        Expand(n);
    }
    void Expand(size_t n)//增容
    {
        size_t capacity = Capacity();
        size_t size = Size();
        if (n < Capacity())
            return;
        T* tmp = new T[n];//失败会抛异常
        for (size_t i = 0; i < size; i++)
        {
            tmp[i] = _start[i];
        }
        delete[] _start;
        _start = tmp;
        _finish = _start + size;
        _endofstorage = _start + n;
    }

    T& operator[](size_t index)
    {
        assert(index<Size());
        return _start[index];
    }
    void PushBack(const T&x)//尾插
    {
        if (_finish == _endofstorage)//若相等则需要增容
        {
            size_t capacity = Capacity();       
            size_t n = capacity == 0 ? 3 : 2 * capacity;
            Expand(n);
        }
        *_finish = x;
        ++_finish;
    }
    void PushFront(const T& x)//头插
    {
        if (_finish == _endofstorage)
        {
            size_t capacity = Capacity();
            size_t n = capacity == 0 ? 3 : 2 * capacity;
            Expand(n);
        }
        size_t end = Size();
        while (end > 0)
        {
            _start[end] = _start[end - 1];
            --end;
        }
        _start[0] = x;
        ++_finish;

    }
    void PopBack()//尾删
    {
        --_finish;
    }
    void PopFront()//头删
    {
        size_t i = 0;
        while (i < Size()-1)
        {
            _start[i] = _start[i + 1];
            ++i;
        }
        --_finish;
    }

    void Print()
    {
        Vecter<int>::Iterator it = Begin();
        while (it != End())
        {
            cout << *it << " ";
            ++it;
        }
        cout << endl;
    }

protected:
    Iterator _start;
    Iterator _finish;//最后一个数据的下一个位置
    Iterator _endofstorage;//空间的下一个位置

};
相关标签: stl