STL库中的vector的使用和模拟实现

1.初识STL库

STL库即标准模板库，它是一些容器的“集合”，诸如list，vector等。STL可分为容器，迭代器，空间配置器，算法，仿函数，适配器六个部分。本篇文章暂且讨论vector的使用与模拟实现。

2.vector的使用

vector可以理解成一个能够存放任意类型的动态数组，能够增加和删除数据。我们先来看看vector里都有些什么。
一.

首先，肯定有的是构造函数，析构函数，和运算符重载。
二.

接着是它的迭代器，迭代器是用来访问容器的。这里我们暂且只看前4个迭代器，因为有些编译器还没有C++11的版本没有后4个迭代器。迭代器可以把他理解成指针，但实际上它并不是一个指针。
begin（）：返回第一个元素的迭代器。
end（）：返回最后一个元素的迭代器（实际是返回最后一个元素的下一个位置）。
我们可以通过下面的代码来看他们的使用

int main()
{
    int a[] = { 1, 2, 3, 4, 5, 6 };
    vector<int> myvector;
    for (size_t i = 0; i < sizeof(a) / sizeof(a[0]); ++i)
    {
        myvector.push_back(a[i]);
    }

    vector<int>::iterator it;
    for (it = myvector.begin(); it < myvector.end(); it++)
    {
        cout << " " << *it;
    }
    cout << endl;
    system("pause");
    return 0;
}

输出结果为1 2 3 4 5 6，即第二个for循环语句的功能便是输出myvector的第一个元素到最后一个元素，因为end（）指向的是最后一个元素的下一个位置，那么此处便是可以用it小于myvector.end（）。而如果用it<=myvector.end（），程序便会出错。所以从这里可以看出，迭代器总是会给一个左闭右开的区间。

rebegin（）和rend（）是逆序访问vector的意思，看看下面的代码就知道了。

int main()
{
    int a[] = { 1, 2, 3, 4, 5, 6 };
    vector<int> myvector;
    for (size_t i = 0; i < sizeof(a) / sizeof(a[0]); ++i)
    {
        myvector.push_back(a[i]);
    }

    vector<int>::reverse_iterator rit;
    for (rit = myvector.rbegin(); rit < myvector.rend(); rit++)
    {
        cout << " " << *rit;
    }
    cout << endl;
    system("pause");
    return 0;
}

输出结果是6 5 4 3 2 1，可以看到使用的是vector::reverse_iterator迭代器，需要注意与上者的区别。

三.

再来看看vector中与容量有关的一些函数
size（）会直接输出vector中元素的个数；
max_size（）会返回vector所能容纳元素的最大数量，这个并不常用；
两者在这里就举例说明了。
capacity（）会返回vector所能容纳元素的数量（在不重新分配内存的情况下）；
empty（）是一个判断函数，判断vector是否为空（返回true时为空）；

接下来我们对resize和reserve作着重说明。
resize（n）,调整容器的长度大小，使其能容纳n个元素，如果n小于容器的当前size，则会删除多出来的元素，否则会添加采用值初始化的元素。
resize（n，t），多一个参数t，将所有新添加的元素初始化为t。

而reserve（n）只有一种用法，预分配n个元素的存储空间。

resize()函数和容器的size息息相关。调用resize(n)后，容器的size即为n。至于是否影响capacity，取决于调整后的容器的size是否大于capacity。
reserve()函数和容器的capacity息息相关。调用reserve(n)后，若容器的capacity小于n，则重新分配内存空间，从而使得capacity等于n。如果capacity>=n呢？capacity无变化。

从两个函数的用途可以发现，容器调用resize()函数后，所有的空间都已经初始化了，所以可以直接访问。而reserve()函数预分配出的空间没有被初始化，所以不可访问。
我们通过下面的用例来看一下。

int main()
{
    int a[] = { 1, 2, 3, 4, 5, 6 };
    vector<int> myvector;
    for (size_t i = 0; i < sizeof(a) / sizeof(a[0]); ++i)
    {
        myvector.push_back(a[i]);
    }
    cout << myvector.size();
    myvector.resize(8);
    system("pause");
    return 0;
}

我们可以看到，在未使用resize（8）之前，size的大小和capacity的大小都为6，size的大小在resize（8）之后变成了8，而capacity变成了9，所以我们可以知道，resize（）不仅会改变size，还会改变capacity，但是由于新的两个元素并没有初始化，所以新增的两个元素默认初始化为0，若是我们将resize（8）改为resize（8,7），那么新增的两个元素就都被初始化为7，这里就不测试了。

int main()
{
    int a[] = { 1, 2, 3, 4, 5, 6 };
    vector<int> myvector;
    for (size_t i = 0; i < sizeof(a) / sizeof(a[0]); ++i)
    {
        myvector.push_back(a[i]);
    }
    cout << myvector.size();
    myvector.reserve(8);
    system("pause");
    return 0;
}

这里可以看到在使用reserve（8）之后，仅仅只是改变了capacity的值，size的值并没有改变。因为新增的两个空间时未初始化的，所以并不可以被访问。

这里总结一下两者的用法，reserve一般和push_back一起用，而resize（）一般就是和直接赋值的情况下一起用。

四.

再来看一看元素的一些入口。
at（）返回指定位置的元素；
front（）返回第一个元素；
back（）返回最末位置的元素；
这些很简单就不测试了。

五.

最后来看一下当中的操作函数，Modifiers是调节器的意思，调节元素。
assign（）：对vector中的元素赋值，实际开发中很少会用到。
push_back（）：尾插，上面的测试用例中都有用到。
pop_back（）：尾删。
insert（）：在指定位置添加一个元素。
erase（）：删除指定位置的元素。
clear（）：清空vector。
swap（）：交换两个vector，涉及到适配器，暂且先不看它；

下面我们通过测试用例来看一下上面的操作函数

int main()
{
    int a[] = { 1, 2, 3, 4, 5, 6 };
    vector<int> myvector;
    for (size_t i = 0; i < sizeof(a) / sizeof(a[0]); ++i)
    {
        myvector.push_back(a[i]);
    }

    myvector.insert(myvector.begin(), 0);
    myvector.pop_back();
    myvector.erase(myvector.end() - 1);
    system("pause");
    return 0;
}

首先，在一个for循环之后，myvector中push_back了6个元素，此时size为6，capacity为6；之后在begin（）的位置插入了一个元素0，如下

此时，size为7，capacity变成了9；之后进行了一个pop_back（）尾删操作，如下

size又变为了6，capacity还是9，此时，最后一个元素6被删除了；最后我们在end（）-1的位置，也就是最后一个元素的位置，进行了erase删除操作，如下

最后一个元素5被删除，size变为了5，capacity还是9。
可以看出STL库中的vector在要加入元素而空间不够时，默认增加3个元素大小的长度。例子中即是从6变成9。

六.
剩下还有些用的不多的内容。
Operators 对vector进行赋值或比较；
get_allocator() 返回vector的内存分配器；

模拟实现myvector

接下来我们自己写一个vector，STL里的vector是由三个迭代器来维护的：_start(数据存放开始的位置),_finish(数据存放结束位置的下一个),_endofstorage(容量的最后一个位置)。vector里的迭代器其实就是个指针。下面来看看我们的代码。

#pragma once

#include <iostream>
using namespace std;

template <class T>
class MyVector
{
public:
    typedef T* iterator;

    MyVector(size_t n = 3)//构造函数，初始化给3个T类型元素
        :_start(new T[n])
        , _finish(_start)
        , _end_of_storage(_start + n)
    {}

    MyVector(const MyVector<T>& v)//拷贝构造
    {
        if ((v._finish - v._start) > (_finish - _start))
        {
            delete[] _start;
            _start = new T[v._finish - v._start];
            _finish = _start;
        }

        for (iterator tmp = v._start; tmp != v._finish; ++tmp)
        {
            *(_finish) = *tmp;
            _finish++;
        }
        _end_of_storage = _finish;
    }
    void PushBack(const T& x)
    {
        _CheckCapacity();
        Insert(End(), x);
    }

    void Insert(iterator pos, const T& x)
    {
        _CheckCapacity();
        for (iterator tmp = _finish; tmp != pos; tmp--)
        {
            *tmp = *(tmp - 1);
        }
        *pos = x;
        _finish++;
    }

    void PopBack()
    {
        iterator pos = End();
        Erase(--pos);
    }

    void Erase(iterator pos)
    {
        iterator end = End();
        for (iterator tmp = pos; tmp !=(--end); tmp++)
        {
            *tmp = *(tmp + 1);
        }
        _finish--;
    }

    inline size_t Size()
    {
        return _finish - _start;
    }

    inline size_t Capacity()
    {
        return _end_of_storage - _start;
    }

    void Expand(size_t n = 0)//增容
    {
        if (n > Capacity())
        {
            size_t size = Size();
            size_t capacity = Capacity();
            T* tmp = new T[n];
            for (size_t i = 0; i < Size(); ++i)
            {
                tmp[i] = _start[i];
            }
            delete  _start;
            _start = tmp;
            _finish = _start + size;
            _engOfStorage = _start + n;
        }
    }

    void Resize(size_t n, T val = T())//增加size和capacity
    {
        if (n > Capacity())
        {
            Expand(n);
        }
        for (size_t i = Size(); i < n; ++i)
        {
            _start[i] = val;
        }
        _finish = _start + n;

    }

    void Reserve(size_t n)//增加capacity
    {
        if (n > Capacity())
        {
            Expand(n);
        }
    }
    iterator Begin()
    {
        return _start;
    }
    iterator End()
    {
        return _finish;
    }

protected:
    void _CheckCapacity()
    {
        if (_finish == _end_of_storage)//如果需要增加容量
        {
            iterator new_start = new T[2 * Size()];//一次扩容为原来的两倍
            iterator new_finish = new_start;
            for (iterator tmp = Begin(); tmp != End(); ++tmp , ++new_finish)
            {
                *new_finish = *tmp;
            }
            delete[] _start;
            _start = new_start;
            _finish = new_finish;
            _end_of_storage = _start + 2 * Size();
        }
        else//不用增加容量
        {
            return;
        }
    }
protected:
    iterator _start; //(数据存放开始的位置)
    iterator _finish;//(数据存放结束位置的下一个位置)
    iterator _end_of_storage;//(容量的最后一个位置）
};

void TestMyVector()
{
    MyVector<int> v;
    v.PushBack(1);
    v.PushBack(2);
    v.PushBack(3);
    v.PushBack(4);
    MyVector<int> ::iterator it;
    for (it = v.Begin(); it != v.End(); it++)
    {
        cout << *it << " ";
    }
    cout << endl;

    v.PopBack();
    for (it = v.Begin(); it != v.End(); it++)
    {
        cout << *it << " ";
    }
    cout << endl;

    MyVector<int> v1(v);
    for (it = v1.Begin(); it != v1.End(); it++)
    {
        cout << *it << " ";
    }
}