vector

本节目标

1. vector的介绍及使用

1.1 vector的介绍

1.2 vector的使用

1.2.1 vector的定义（构造函数）

1.2.2 vector iterator的使用

1.2.3 vector的空间增长问题

1.2.4 vector增删查改

2. vector的模拟实现

2.1 构造函数

2.2 模拟迭代器iterator

2.3 相关空间的接口

2.4 增删查改（注意：迭代器失效）

2.5 其他部分函数

3. 深拷贝问题

3.1 vector<vector< int >>

3.1.1 提出问题

3.1.2 进行分析

3.1.3 解决方式

3.2 vector< string >

3.3 深拷贝问题的总结

4. vector模拟实现的函数汇总

4.1 vector.h

4.2 test.cpp

本节目标

• 了解vector的函数使用
• 模拟实现vector
• 模拟实现中的迭代器失效问题（重要）
• 深拷贝问题（重要）

1.vector的介绍及使用

1.1 vector的介绍

vector是表示可变大小数组的序列容器。

就像数组一样，vector也采用的连续存储空间来存储元素。也就是意味着可以采用下标对vector的元素

进行访问，和数组一样高效。但是又不像数组，它的大小是可以动态改变的，而且它的大小会被容器自动处理。

本质讲，vector使用动态分配数组来存储它的元素。当新元素插入时候，这个数组需要被重新分配大小

为了增加存储空间。其做法是，分配一个新的数组，然后将全部元素移到这个数组。就时间而言，这是一个相对代价高的任务，因为每当一个新的元素加入到容器的时候，vector并不会每次都重新分配大小。

vector分配空间策略：vector会分配一些额外的空间以适应可能的增长，因为存储空间比实际需要的存储空间更大。不同的库采用不同的策略权衡空间的使用和重新分配。但是无论如何，重新分配都应该是对数增长的间隔大小，以至于在末尾插入一个元素的时候是在常数时间的复杂度完成的。

因此，vector占用了更多的存储空间，为了获得管理存储空间的能力，并且以一种有效的方式动态增长。

与其它动态序列容器相比（deque, list and forward_list）， vector在访问元素的时候更加高效，在末尾添加和删除元素相对高效。对于其它不在末尾的删除和插入操作，效率更低。比起list和forward_list统一的迭代器和引用更好。

使用STL的三个境界：能用，明理，能扩展 ，那么下面学习vector，我们也是按照这个方法去学习

1.2vector的使用

vector学习时一定要学会查看文档：vector的文档介绍，vector在实际中非常的重要，在实际中我们熟悉常见的接口就可以，下面列出了哪些接口是要重点掌握的。

此外对于vector内部的成员函数，基本上和string相同，因此本文章在模拟实现之前只介绍大多使用函数的函数名以及功能，具体细节会在模拟实现中解释。

1.2.1vector的定义（构造函数）

我们知道，vector实际上也是内部库中的内部类，因此对于vector也存在构造函数，而对于构造函数vector又有着众多的重载函数，下面就来看一看：

构造函数声明                                                                                 接口说明

vector()（重点）                                                                     无参构造

vector（size_type n, const value_type& val = value_type()）   构造并初始化n个val

vector (const vector& x)（重点）                                        拷贝构造

vector (InputIterator first, InputIterator last);          使用迭代器进行初始化构造

1.2.2vector iterator的使用

/

在上面的本节目标中，明确了会有迭代器失效的问题，在这里先简单的描述一下什么是迭代器失效问题：==对于上图我们发现迭代器可以看成指向某一数据的指针（实际上不一定是指针），但如果出现了扩容的情况（由于我们不能判断是本地扩容还是异地扩容，因此我们统一将其看成异地扩容）那么这个迭代器指向的位置就不再是我们想要进行操作的位置，这就是典型的迭代器失效问题，也就是野指针问题。==具体介绍将会在下面的模拟实现中进行解释。

1.2.3vector的空间增长问题

同样，与string中的函数功能和名字相同

capacity的代码在vs和g++下分别运行会发现，vs下capacity是按1.5倍增长的，g++是按2倍增长的。

这个问题经常会考察，不要固化的认为，vector增容都是2倍，具体增长多少是根据具体的需求定义的。vs是PJ版本STL，g++是SGI版本STL。

reserve只负责开辟空间，如果确定知道需要用多少空间，reserve可以缓解vector增容的代价缺陷问题。(即可以直接将扩容一次性到位)

resize在开空间的同时还会进行初始化，影响size。

// 测试vector的默认扩容机制
void TestVectorExpand()
{
    size_t sz;
    vector<int> v;
    sz = v.capacity();
    cout << "making v grow:\n";
    for (int i = 0; i < 100; ++i)
    {
        v.push_back(i);
        if (sz != v.capacity())
        {
            sz = v.capacity();
            cout << "capacity changed: " << sz << '\n';
        }
    }
}
vs：运行结果：vs下使用的STL基本是按照1.5倍方式扩容
making foo grow:
capacity changed: 1
capacity changed: 2
capacity changed: 3
capacity changed: 4
capacity changed: 6
capacity changed: 9
capacity changed: 13
capacity changed: 19
capacity changed: 28
capacity changed: 42
capacity changed: 63
capacity changed: 94
capacity changed: 141
g++运行结果：linux下使用的STL基本是按照2倍方式扩容
making foo grow:
capacity changed: 1
capacity changed: 2
capacity changed: 4
capacity changed: 8
capacity changed: 16
capacity changed: 32
capacity changed: 64
capacity changed: 128

1.2.4vector增删查改

vector增删查改         接口说明

push_back（重点）       尾插

pop_back （重点）       尾删

find             查找（注意这个是算法模块实现，不是vector的成员接口）

insert            在position之前插入val

erase              删除position位置的数据

swap              交换两个vector的数据空间

operator[] （重点） 像数组一样访问

2.vector的模拟实现

在此之前，我们需要自己定义一个vector类：(框架)其他自定义的成员函数都在public中。

template<class T>
class vector
{
public:
    typedef T* iterator;//模拟实现时，把迭代器模拟成指针
    typedef const T* const_iterator;
    T& operator[](size_t pos)
    {
        assert(pos < size());
        return _start[pos];//注意
    }
    const T& operator[](size_t pos) const//重载
    {
        assert(pos < size());
        return _start[pos];
    }
private://成员变量和_size _capacity的本质是一样的，只不过表示方法不一样
    iterator _start;//0
    iterator _finish;//size
    iterator _endofstorage;//capacity
};

对于模拟实现的顺序，与上面介绍的顺序一一对应。

对于模拟实现的代码，我们则需要根据源码来进行设计。

2.1构造函数

对于一个类来说，构造函数是必不可少的，对于vector的构造函数，当然也有众多的重载函数：

构造函数声明                                                                          接口说明

vector()（重点）                                                                       无参构造

vector（size_type n, const value_type& val = value_type()） 构造并初始化n个val

vector (const vector& x)（重点）                                             拷贝构造

vector (InputIterator first, InputIterator last);              使用迭代器进行初始化构造

下面，就来逐个模拟实现：

1. 无参构造

vector()//构造
    :_start(nullptr)
        ,_finish(nullptr)
        ,_endofstorage(nullptr)
    {}

2. 拷贝构造

对于拷贝构造来说，我们有传统写法和现代写法之分，传统写法就是所谓的普通操作步骤，即：开空间、赋值，当然传统写法也可以用reserve的方式去写，这也属于传统写法，下面展示用reserve的方式：

//传统写法 v2(v1)
    vector(const vector<T>& v)
    :_start(nullptr)
        , _finish(nullptr)
        , _endofstorage(nullptr)
    {
        reserve(v.capacity());
        for (const auto& e : v)//必须&， 否则会拷贝构造调用拷贝构造，因为如果每一个元素(T)也都是vector，这就会导致拷贝构造调用拷贝构造
        {
            push_back(e);
        }
    }

这样写需要注意的就是T不能是vector类型，这样会导致拷贝套用拷贝，造成死递归。

当然，既然有传统写法，也就有现代写法，我们一般用的也都是现代写法实现拷贝构造：（代码如下）

template <class InputIterator>
vector(InputIterator first, InputIterator last)//迭代器初始化
    :_start(nullptr)
    , _finish(nullptr)
    , _endofstorage(nullptr)
{
    while (first != last)
    {
        push_back(*first);
        ++first;
    }
}
//现代写法
vector(const vector<T>& v)
    :_start(nullptr)
    , _finish(nullptr)
    , _endofstorage(nullptr)
{
    vector<T> tmp(v.begin(), v.end());
    swap(tmp);//this和tmp进行swap
}

即我们可以通过迭代器的初始化构造从而实现拷贝构造，这就是现代写法。

3. 构造并初始化n个val

vector(size_t n, const T& val = T())
    :_start(nullptr)
    , _finish(nullptr)
    , _endofstorage(nullptr)
{
    reserve(n);
    for(size_t i = 0; i < n; i++)
    {
        push_back(val);
    }
}

当我们将第二个拷贝构造的现代写法的拷贝构造和第三个构造并初始化n个val函数重载之后，如果我们用如下例子，看看会发生什么：

void test_vector8()
{
    std::string str("hello");
    vector<int> v(str.begin(), str.end());
    for (auto e : v)
    {
        cout << e << ' ';
    }
    cout << endl;
    vector<int> v1(10, 1); //就这种会出现问题,因为调用会调用到InputIterator
    //原因：上面的1最好的选择就是利用模板实例化，因此就会last接收1，造成非法的间接寻址
    //解决方案：再加上一个构造的重载函数来解决这种问题；直接改成int的话，不符合库的思想
    //而且通过源代码也可以看出这里用到了：再加上一个重载函数的方式
    //vector<char> v1(10, 'A');//肯定会选择val对应的构造函数
    for (auto e : v1)
    {
        cout << e << ' ';
    }
    cout << endl;
}

看看运行结果：

我们发现，运行失败了，这是什么原因造成的呢？我们将下面的v1的初始化和打印都注释掉之后，再来看看：

这样就运行成功了，因此可以断定是v1在初始化时发生了错误，那我们分析一下是根据什么初始化的。

从主观上来讲，对于v1的初始化，我们想的是第三种方式：构造并初始化n个val，即v1是构造并初始化10个1，那么打印的结果就应该是1 1 1 1 1 1 1 1 1 1。然而事与愿违，并没有成功打印反而运行错误，因此我们可以断定，v1并没有像我们想的那样去调用第三种函数，我们通过观察上面的错误信息，发现，其调用的是迭代器初始化，即构造函数现代写法中的vector(InputIterator first, InputIterator last)，为什么会调用这个函数呢？

那么对其分析，我们知道对于重载函数，传入的参数会根据重载函数的参数进行择优匹配，即与重载函数参数的类型相匹配。对于vector(size_t n, const T& val = T())函数来说，当我们传入都是int类型时，前者n由于是size_t而不是int类型，调用此函数就会发生隐式类型转换，因此v1就会继续观察是否有更好的选择，即观察有没有不需要隐式类型转换的重载函数参数，于是发现了vector(InputIterator first, InputIterator last)，因此，1和10就被传入了此函数中，但由于在这个过程中，有first的解引用，这就造成了first本身不是地址却仍然出现解引用的状况，于是就发生了野指针的问题，因此程序才会崩溃。

于是，我们知道了bug的出处，接下来就是处理的方式了，处理方式实际上不止一种，即我们可以直接在传入10的过程中将其强转成size_t类型的参数，这种方式我只是随口一说，实际上看起来丑丑的，因为有更好的方式：再重载一个函数：vector(int n, const T& val = T())这样就可以传入到这个函数中进行初始化了。那我们为什么不直接将上一个函数的size_t改成int类型呢？因为我们是在模拟实现vector，通过观察，我们发现vector的此处的重载函数的传参类型应有尽有，所以我们可以顺应库中的方式进行实现。

2.2 模拟迭代器iterator

iterator begin()
{
    return _start;
}
iterator end()
{
    return _finish;
}
const_iterator begin() const
{
    return _start;
}
const_iterator end() const
{
    return _finish;
}

2.3 相关空间的接口

对于上面空间增长的函数，有如下几个函数：

通过前面的文档，我们也能够了解到这些成员函数的参数个数和种类，下面就模拟实现一下：

size_t size() const 
{
    return _finish - _start;
}
size_t capacity() const
{
    return _endofstorage - _start;
}
bool empty() const
{
    return _finish == _start;
}
void resize(size_t n, T val = T())//这里的val是缺省
{
    if (n > capacity())
    {
        reserve(n);
    }
    if (n > size())
    {
        while (_finish < _start + n)
        {
            *_finish = val;
            ++_finish;
        }
    }
    else
    {
        _finish = _start + n;
    }
}
void reserve(size_t n)//注意迭代器失效问题
{
    if (n > capacity())
    {
        size_t oldSize = size();
        T* tmp = new T[n];
        if (_start)
        {
            memcpy(tmp, _start, sizeof(T) * size());
            delete[] _start;
        }
        _start = tmp;
        _finish = tmp + oldSize;
        _endofstorage = _start + n;
    }
}

而对于reserve,还是单独说明比较好一些：

在reserve中，我们注释了一个迭代器失效的问题，但已经在代码中得到了解决，即oldSize记录了size()的大小。那如果不记录size()的大小，会发生这样的情况：如果没有oldSize，那么_finish = tmp + size()中的size()由于之前的空间被销毁，因此size()也会被置为0,，因此此时的_finish就与_start相同，这就是此处需要oldSize的原因。

**size()被置为0的原因也是有必要说明的：**我们观察上面自己实现的size()，发现return的是两个迭代器相减，但我们知道，当delete原有空间之后，_finish也将和_start一样，所以二者二者相减会变成0。

2.4增删查改（注意：迭代器失效）

对于这些接口，上述提到过：迭代器失效与扩容机制息息相关，而增删查改会频繁的调用扩容机制，因此在这里也就详细的介绍关于迭代器失效的场景以及解决的方法。

首先我们来实现一下不涉及迭代器失效的问题的成员函数：

void push_back(const T& x)
{
    if (_finish == _endofstorage)
    {
        size_t newCapacity = capacity() == 0 ? 4 : capacity() * 2;
        reserve(newCapacity);
    }
    *_finish = x;
    ++_finish;
}
void pop_back()
{
    assert(!empty());
    --_finish;
}

即尾插和尾删的成员函数实际上并不需要什么特殊的细节处理。那下面看看需要考虑迭代器失效问题的成员函数:

1. insert

这里不废话，直接上正确的代码，然后再进行讨论分析：

//迭代器失效问题：野指针问题：异地扩容导致
iterator insert(iterator pos, const T& val)//不传引用是因为有左值的影响：常量、v.begin()
{
    assert(pos >= _start);
    assert(pos < _finish);
    if (_finish == _endofstorage)
    {
        size_t len = pos - _start; // 处理失效问题，记录相对位置
        size_t newCapacity = capacity() == 0 ? 4 : capacity() * 2;
        reserve(newCapacity);
        //扩容导致pos迭代器失效，需要更新处理一下
        pos = _start + len;
    }
    //挪动数据
    iterator end = _finish - 1;
    while (end >= pos)
    {
        *(end + 1) = *end;
        end--;
    }
    *pos = val;
    ++_finish;
    return pos;
}

对于前插，是一定要考虑扩容问题的，而我们实现的方式也只有异地扩容，因此当我们触发了扩容机制后，就会引起迭代器失效的问题：

当扩容之后，如果我们不对pos的位置进行更新，那么我们通过图上图就会发现，pos指向的位置已经不是再是我们想要插入的位置，而且上面的空间已经被释放掉，即pos就会像无头苍蝇一样空有位置，但实际上并没有空间，这就造成了野指针的问题。因此为了处理这个迭代器失效的问题，我们提前记录pos与_start的相对位置，即通过len = pos - _start记录，最后更新pos = _start + len,就可以解决这里迭代器失效的问题。

虽然函数内部的迭代器失效问题解决了，但我们知道，在这个函数中的pos只是外部pos的一份临时拷贝，改变这里的pos外部的pos并不会改变，因此外部的pos也会由于异地扩容之后导致野指针，那么我们也需要解决这个问题。事实上，对于我们模拟实现的功能来说，有两种方式可以解决这个问题，1就是引用，2就是给一个返回值（代码中就是返回值的方式），通过引用和返回值的方式可以更新外部的pos，但在库中的insert也是返回值的方式，这里不用引用是有原因的，提一旦涉及到左值的问题，用引用就是错误的。这里举两个简单的例子来说明左值：如果我们传入的是常量，v.begin()这种，这几种实际上是不可修改的，但我们知道参数中引用的变量不能被这种常量赋值，会出现错误（C++第一篇讲过引用），因此我们采取和库中一样的实现方式：返回值更新pos。

2. erase

同样，我们展示正确代码：

iterator erase(iterator pos)
{
    assert(pos >= _start && pos < _finish);
    iterator begin = pos + 1;
    while (begin < _finish)
    {
        *(begin-1) = *begin;
        ++begin;
    }
    --_finish;
    return pos;
}

对于erase模拟实现，我们所需要避免的，并不是异地扩容的问题，因为erase是不需要扩容的，但是有可能会发生一些找不到的问题，即如果在最后一个位置删除，亦或者连续的偶数需要删除，这都是我们需要在代码中处理的细节问题，因此对于这些问题，我们在模拟实现时只需要记住一件事，一定要留意pos的指向，即我们必须在函数用过后及时更新pos的值，这也与库中的处理方法相同，通过返回值的方法。

此外，对于出现这种情况，vs库中的和Linux是不一样的，这个需要了解即可，我们只需要记住，返回值，并在调用时时刻注意更新它就好。

3. swap

这里就直接实现了，很简单：

void swap(vector<T>& v)
{
    std::swap(_start, v._start);
    std::swap(_finish, v._finish);
    std::swap(_endofstorage, v._endofstorage);
}

2.5 其他部分函数

~vector()//析构
{
    delete[] _start;
    _start = _finish = _endofstorage = nullptr;
}
vector<T>& operator=(vector<T> v)//由于直接swap，因此不能传引用
{
    swap(v);
    return *this;
}
void clear()
{
    _finish = _start;//不能置空，会发现内存泄漏
}