C++STL详解（二）vector的使用及其模拟实现

文章目录

• 1.简介
• 2.常用接口
• • 构造函数
  • 遍历
  • 扩容机制
  • 缩容
  • 插入删除
  • find
  • sort
• 3.vector模拟实现
• • SGI版本源码
  • 构造函数
  • 深拷贝
  • push_back
  • reserve
  • resize
  • insert
  • 迭代器失效
  • erase
  • 更深层次深拷贝
  • 源代码
• 尾声

1.简介

vector官方文档

C++ STL中的verctor好比是C语言中的数组，但是vector又具有数组没有的一些高级功能。

1. vector是可变大小的顺序容器。
2. 就像数组一样，vector也采用的连续存储空间来存储元素。也就是意味着可以采用下标对vector的元素进行访问，和数组一样高效。但是又不像数组，它的大小是可以动态改变的，而且它的大小会被容器自动处理。
3. 本质讲，vector使用动态分配数组来存储它的元素。当新元素插入时候，这个数组需要被重新分配大小为了增加存储空间。其做法是，分配一个新的数组，然后将全部元素移到这个数组。就时间而言，这是一个相对代价高的任务，因为每当一个新的元素加入到容器的时候，vector并不会每次都重新分配大小。
4. vector分配空间策略：vector会分配一些额外的空间以适应可能的增长，因为存储空间比实际需要的存储空间更大。不同的库采用不同的策略权衡空间的使用和重新分配。但是无论如何，重新分配都应该是对数增长的间隔大小，以至于在末尾插入一个元素的时候是在常数时间的复杂度完成的。
5. 因此，vector占用了更多的存储空间，为了获得管理存储空间的能力，并且以一种有效的方式动态增长。
6. 与其它动态序列容器相比（deques, lists and forward_lists）， vector在访问元素的时候更加高效，在末尾添加和删除元素相对高效。对于其它不在末尾的删除和插入操作，效率更低。比起lists和forward_lists统一的迭代器和引用更好

2.常用接口 构造函数

构造函数文档

alloc是空间配置器，暂时先不用理会。

如果vector的元素类型是int，默认初始化为0；如果vector元素类型为string，则默认初始化为空字符串。

vector v1;
vector v3;
vector>;  //这里相当于二维数组int a[n][n];
vector v5 = { 1,2,3,4,5 }; //列表初始化，注意使用的是花括号
vector v6 = { "hi","my","name","is","lee" };
vector v7(5, -1); //初始化为-1,-1,-1,-1,-1。第一个参数是数目，第二个参数是要初始化的值
vector v8(3, "hi");
vector v9(10); //默认初始化为0
vector v10(4); //默认初始化 为空字符串

利用迭代器区间初始化：

void test_vector1()
{
	vector v1;
	v1.push_back(1);
	v1.push_back(2);
	v1.push_back(3);
	v1.push_back(4);

	vector v2;
	v2.push_back(1.1);
	v2.push_back(2.2);
	v2.push_back(3.3);

	vector v3;
	v3.push_back("李白");
	v3.push_back("杜甫");
	v3.push_back("苏轼");
	v3.push_back("白居易");

	vector v4(10, 5); // 10个5初始化v4

	vector v5(++v3.begin(), --v3.end());
    
	string s = "hello world";
	vector v6(s.begin(), s.end());
}

遍历

void test_vector2()
{
	// 遍历
	vector v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.push_back(4);

	// 1、下标+[]
	for (size_t i = 0; i < v.size(); ++i)
	{
		v[i] += 1;
		cout << v[i] << " ";
	}
	cout << endl;

	// 2.迭代器
	vector::iterator it = v.begin();
	while (it != v.end())
	{
		*it -= 1;
		cout << *it << " ";
		++it;
	}
	cout << endl;

	// 3.范围for
	for (auto& e : v)
	{
		e += 1;
		cout << e << " ";
	}
	cout << endl;
}

遍历二维的：

void test_vector9()
{
	vector> vv;
	for (size_t i = 0; i < vv.size(); ++i)
	{
		for (size_t j = 0; j < vv[i].size(); ++j)
		{
			cout << vv[i][j] << " ";
		}
		cout << endl;
	}
}

扩容机制

// 查看扩容情况
void test_vector4()
{
	size_t sz;
	std::vector foo;
	//foo.reserve(100); // 如果预知到大概插入多少数据利用reserve开好足够的空间
	sz = foo.capacity();
	std::cout << "making foo grow:n";
	for (int i = 0; i < 100; ++i) {
		foo.push_back(i);
		if (sz != foo.capacity()) {
			sz = foo.capacity();
			std::cout << "capacity changed: " << sz << 'n';
		}
	}
}

Linux下g++版本：

• VS用的STL是PJ版本，大约1.5倍扩容
• Linux下用的是SGI版本，大约2倍扩容

单次增容越多，插入N个值，增容次数越少，效率就越高，但是带来的空间浪费可能也就越多。

单次增容越少，空间浪费较少，但增容次数增多，降低效率。

resize：开空间+初始化。

1. 当所给值大于容器当前的size时，将size扩大到该值，扩大的元素为第二个所给值，若未给出，则默认为0。
2. 当所给值小于容器当前的size时，将size缩小到该值。

void test_vector5()
{
	vector countV;
	countV.resize(10, 1); // 10个1
	for (auto e : countV)
	{
		cout << e << " ";
	}
	cout << endl;

	countV.resize(5); // 只保留下5个1
	for (auto e : countV)
	{
		cout << e << " ";
	}
	cout << endl;

	countV.resize(8, 10); // 5个1后面接上3个10
	for (auto e : countV)
	{
		cout << e << " ";
	}
	cout << endl;

	countV.resize(12); // 最后补上4个0凑足12
	for (auto e : countV)
	{
		cout << e << " ";
	}
	cout << endl;
}

缩容

一般来说，删除数据是不会主动缩容的，缩容代价也比较大。
操作系统就不接受归还一部分内存的，只能整体归还。因此缩容也就变成把要保留的内容拷贝到一个合适的新空间，再把旧的整个空间释放，还给操作系统。

void test_vector6()
{
	std::vector foo;
	foo.reserve(100);
	foo.resize(10); //原来100个空间
	cout << foo.size() << endl;
	cout << foo.capacity() << endl;
	foo.shrink_to_fit(); // 把capacity缩到和size一样大
	cout << foo.size() << endl;
	cout << foo.capacity() << endl;
}

shrink_to_fit()

这个函数慎用，一般来说现代计算机内存是比较充足的。

插入删除

void test_vector7()
{
	// 遍历
	vector v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.push_back(4);

	v.insert(v.begin(), -1);
	v.insert(v.begin(), -2);
	v.insert(v.begin(), -3);
	for (auto e : v)
	{
		cout << e << " ";
	}
	cout << endl;

	v.insert(v.begin() + 7, 300); // 在任意位置插入都行
	//v.insert(v.begin()+8, 300); //越界了 err
	for (auto e : v)
	{
		cout << e << " ";
	}
	cout << endl;

	v.erase(v.begin());
	v.erase(v.begin());
	for (auto e : v)
	{
		cout << e << " ";
	}
	cout << endl;

	v.erase(v.begin() + 1, v.begin() + 4);
	for (auto e : v)
	{
		cout << e << " ";
	}
	cout << endl;
}

find

find文档

vector是没有实现find的，但如果我们非要找某个位置的话，可以用算法里的find()

注意，STL中的迭代器基本都是左闭右开区间。

// find example
#include      // std::cout
#include     // std::find
#include        // std::vector

int main () {
    // using std::find with array and pointer:
    int myints[] = { 10, 20, 30, 40 };
    int * p;

    p = std::find (myints, myints+4, 30);
    if (p != myints+4)
        std::cout << "Element found in myints: " << *p << 'n'; //30
    else
        std::cout << "Element not found in myintsn";

    // using std::find with vector and iterator:
    std::vector myvector (myints,myints+4);
    std::vector::iterator it = find (myvector.begin(), myvector.end(), 30);
    // 也可以用auto替换 std::vector::iterator
    if (it != myvector.end())
        std::cout << "Element found in myvector: " << *it << 'n'; //30
    else
        std::cout << "Element not found in myvectorn";

    return 0;
}

sort

注意：默认是ascending order

// sort algorithm example
#include      // std::cout
#include     // std::sort
#include        // std::vector

bool myfunction (int i,int j) { return (i
    bool operator() (int i,int j) { return (i
    int myints[] = {32,71,12,45,26,80,53,33};
    std::vector myvector (myints, myints+8);               // 32 71 12 45 26 80 53 33

    // using default comparison (operator <):
    std::sort (myvector.begin(), myvector.begin()+4);           //(12 32 45 71)26 80 53 33

    // using function as comp
    std::sort (myvector.begin()+4, myvector.end(), myfunction); // 12 32 45 71(26 33 53 80)

    // using object as comp
    std::sort (myvector.begin(), myvector.end(), myobject);     //(12 26 32 33 45 53 71 80)

    // print out content:
    std::cout << "myvector contains:";
    for (std::vector::iterator it=myvector.begin(); it!=myvector.end(); ++it)
        std::cout << ' ' << *it;
    std::cout << 'n';

    return 0;
}

void test_vector8()
{
	vector v;
	v.push_back(1);
	v.push_back(6);
	v.push_back(3);
	v.push_back(9);
	v.push_back(2);
	v.push_back(0);
	v.push_back(8);
	for (auto e : v)
	{
		cout << e << " ";
	}
	cout << endl;

	//排升序
	sort(v.begin(), v.end()); // 默认是小于，就是升序
	for (auto e : v)
	{
		cout << e << " ";
	}
	cout << endl;

	// 排降序 利用仿函数
	// 构造了一个匿名对象 
	//greater g;
	//sort(v.begin(), v.end(), g); // 这样也行
	sort(v.begin(), v.end(), greater()); // > 就是降序
	for (auto e : v)
	{
		cout << e << " ";
	}
	cout << endl;
}

3.vector模拟实现 SGI版本源码

stl_vector.h

欣赏一下核心框架：

构造函数

vector()
    :_start(nullptr)
        , _finish(nullptr)
        , _endofstorage(nullptr)
    {}

template
    vector(InputIterator first, InputIterator last)
    : _start(nullptr)
        , _finish(nullptr)
        , _endofstorage(nullptr)
    {
        while (first != last)
        {
            push_back(*first);
            ++first;
        }
    }
void test_yzq_vector6()
{
    std::string s("hello");
    yzq::vector v;
    v.push_back(1);
    v.push_back(2);
    v.push_back(3);
    v.push_back(4);
    yzq::vector v1(v.begin(), v.end());
    for (auto e : v1)
    {
        cout << e << " ";
    }
    cout << endl;
    yzq::vector v2(s.begin(), s.end());
    for (auto e : v2)
    {
        cout << e << " ";
    }
    cout << endl;
}

再写一个：

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);
        }
    }
void test_yzq_vector8()
{
    yzq::vector v(10, 2);
    for (auto e : v)
    {
        cout << e << " ";
    }
    cout << endl;
}

怎么突然编译错误了呢？

一点一点屏蔽代码，发现错误出现在调用构造函数那一行。

再测一组数据，又能正常使用了？

看一下SGI中是咋写的：

再增加一个重载，就能匹配对了。

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

深拷贝

现代写法。

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

vector(const vector& v)
    : _start(nullptr)
        , _finish(nullptr)
        , _endofstorage(nullptr)
    {
        vector tmp(v.begin(), v.end());
        swap(tmp);
        //this->swap(tmp); 等价
    }

vector& operator=(vector v)
{
    this->swap(v);
    return *this;
}

void test_yzq_vector7()
{
    std::string s("hello");
    yzq::vector v;
    v.push_back(1);
    v.push_back(2);
    v.push_back(3);
    v.push_back(4);
    yzq::vector v1(v);
    for (auto e : v1)
    {
        cout << e << " ";
    }
    cout << endl;
    yzq::vector v2 = v;
    for (auto e : v2)
    {
        cout << e << " ";
    }
    cout << endl;
}

注意：

在类里面定义的时候，不加上也是可以的，也有人这么写，但是极其不推荐这么做，比较怪异。
统一加上模板参数才好。

push_back

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()
{
    if (_finish > _start)
    {
        --_finish;
    }
}

reserve

注意需要先保存一下size的值，中间涉及到strat的改变。

void reserve(size_t n)
{
    size_t sz = size();
    // 不考虑缩容的问题
    if (n > capacity())
    {
        T* tmp = new T[n];
        if (_start) // 有数据才拷贝
        {
            memcpy(tmp, _start, size() * sizeof(T)); //这里是浅拷贝
            delete[] _start;
        }
        _start = tmp;
    }

    //_finish = _start + size(); // size()的计算出现了错误，_start已经改变了
    //_endofstorage = _start + capacity();
    _finish = _start + sz;
    _endofstorage = _start + n;
}

resize

C++中的内置类型也有有构造函数、析构函数的，这样才能更好的配合模板使用。

// void resize(size_t n, T val = T()) T()是生成匿名对象，调用默认构造函数
// 注意：C++的内置类型也是有默认构造函数的 int的就是0 double的就是0.0
void resize(size_t n, const T& val = T())
{
    // 3种情况
    // 大于capacity
    if (n > capacity())
    {
        reserve(n);
    }
    // 大于size小于capacity
    if (n > size())
    {
        while (_finish < _start + n)
        {
            *_finish = val;
            ++_finish;
        }
    }
    else // 小于size
    {
        _finish = _start + n;
    }
}
void test_yzq_vector2()
{
	yzq::vector v1;
	// 更多的还是利用resize完成初始化
	v1.resize(15, -2);
	for (auto e : v1)
	{
		cout << e << " ";
	}
	cout << endl;
}

insert

void insert(iterator pos, const T& x)
{
    assert(pos >= _start && pos <= _finish);
    // 考虑扩容
    if (_finish == _endofstorage)
    {
        size_t newCapacity = capacity() == 0 ? 4 : capacity() * 2;
        reserve(newCapacity);
    }

    // 挪动数据
    iterator end = _finish - 1;
    while (end >= pos)
    {
        *(end + 1) = *end;
        --end;
    }
    *pos = x;
    ++_finish;
}

一顿操作猛如虎，一下就写好了，测试一下。

感觉没毛病。

欸，这是怎么回事？这就涉及迭代器失效的问题了。

迭代器失效

1. 野指针失效
2. 迭代器指向的意义变了

void insert(iterator pos, const T& x)
{
    assert(pos >= _start && pos <= _finish);
    // 考虑扩容
    // 扩容后pos失效了，利用相对距离更新pos
    if (_finish == _endofstorage)
    {
        size_t n = pos - _start;
        size_t newCapacity = capacity() == 0 ? 4 : capacity() * 2;
        reserve(newCapacity);
        pos = _start + n;
    }

    // 挪动数据
    iterator end = _finish - 1;
    while (end >= pos)
    {
        *(end + 1) = *end;
        --end;
    }
    *pos = x;
    ++_finish;
}

再举个例子

void test_yzq_vector4()
{
	// 在所有的偶数前面插入一个20
	yzq::vector v1;
	v1.push_back(1);
	v1.push_back(2);
	v1.push_back(3);
	v1.push_back(4);
	v1.push_back(5);
	v1.push_back(6);
	yzq::vector::iterator it = v1.begin();
	while (it != v1.end())
	{
		if (*it % 2 == 0)
		{
			v1.insert(it, 20);
		}
		++it;
	}
	for (auto e : v1)
	{
		cout << e << " ";
	}
	cout << endl;
}

调试一下，发现确实已经完成了插入。

但是我们insert里面不是完成了对pos的更新吗，为啥外面的it还是失效了？

因为这是值传递，形参的改变不影响实参。

那我们引用传递？不行的，加了引用，v1.begin()返回的临时对象（具有常属性）就传不过来了。

即使用reserve开辟足够的空间，不会发生扩容，it没有变成野指针，但是也存在问题。

尽管it++了，但指向的内容还是2，因为还在it的前面也插入了20。
it指向位置的意义发生变化，导致重复插入20，这也是迭代器失效。

解决办法：

Return value：
An iterator that points to the first of the newly inserted elements.

iterator insert(iterator pos, const T& x)
{
    assert(pos >= _start && pos <= _finish);
    // 考虑扩容
    // 扩容后pos失效了，利用相对距离更新pos
    if (_finish == _endofstorage)
    {
        size_t n = pos - _start;
        size_t newCapacity = capacity() == 0 ? 4 : capacity() * 2;
        reserve(newCapacity);
        pos = _start + n;
    }

    // 挪动数据
    iterator end = _finish - 1;
    while (end >= pos)
    {
        *(end + 1) = *end;
        --end;
    }
    *pos = x;
    ++_finish;

    return pos;
}
void test_yzq_vector4()
{
    // 在所有的偶数前面插入一个20
    yzq::vector v1;
    //v1.reserve(20);
    v1.push_back(1);
    v1.push_back(2);
    v1.push_back(3);
    v1.push_back(4);
    v1.push_back(5);
    v1.push_back(6);
    yzq::vector::iterator it = v1.begin();
    while (it != v1.end())
    {
        if (*it % 2 == 0)
        {
            it = v1.insert(it, 20);
            ++it;
        }
        ++it;
    }
    for (auto e : v1)
    {
        cout << e << " ";
    }
    cout << endl;
}

不同平台对比：

看起来在这一点上，MSVC检查比g++更严格。
VS能检查出野指针问题。

erase

一般vector删除数据，都不考虑缩容的方案。

缩容方案：
size < 1/2capacity 时，可以考虑 开辟小一点新空间，拷贝过去，释放旧空间。
缩容方案是用时间来换空间，不太推荐。
实际中比较关注时间效率，现代的空间存储成本相对比较便宜。

Return value：
An iterator pointing to the new location of the element that followed the last element

// 要考虑到实现者有可能对erase实现缩容，而缩容开辟新空间会改变pos位置
// 因此需要返回迭代器
iterator erase(iterator pos)
{
    // 1 2 3 4
    // 1 3 4
    assert(pos >= _start && pos < _finish);
    iterator it = pos + 1;
    while (it != _finish)
    {
        *(it - 1) = *it;
        ++it;
    }
    --_finish;
    return pos;
}

void test_yzq_vector5()
{
    yzq::vector v1;
    //v1.reserve(10);
    v1.push_back(1);
    v1.push_back(2);
    v1.push_back(3);
    v1.push_back(4);
    cout << v1.size() << " " << v1.capacity() << endl;
    for (auto e : v1)
    {
        cout << e << " ";
    }
    cout << endl;
    auto pos = find(v1.begin(), v1.end(), 2);
    if (pos != v1.end())
    {
        v1.erase(pos);
    }
    cout << *pos << endl;
    *pos = 10;
    cout << *pos << endl;
    for (auto e : v1)
    {
        cout << e << " ";
    }
    cout << endl;
    cout << v1.size() << " " << v1.capacity() << endl;
}

erase的失效基本都是意义变了或者不再访问有效数据，除非实现erase时缩容了，才有可能出现野指针的迭代器失效。

erase（pos）以后pos就是失效的了，因为pos的意义变了。

VS会对erase的意义改变造成的失效进行强制检查，报断言错误。
而Linux下就不会检查这种迭代器失效。

再来个例子：删除偶数

void test_vs_vector5()
{
    std::vector v1;
    v1.push_back(1);
    v1.push_back(2);
    v1.push_back(2);
    v1.push_back(2);
    v1.push_back(3);
    v1.push_back(4);
    cout << v1.size() << " " << v1.capacity() << endl;
    for (auto e : v1)
    {
        cout << e << " ";
    }
    cout << endl;
    auto it = v1.begin();
    while (it != v1.end())
    {
        if (*it % 2 == 0)
        {
            v1.erase(it);
        }
            ++it;
    }
    for (auto e : v1)
    {
        cout << e << " ";
    }
    cout << endl;
}

VS、Linux下均会出现错误。

正确代码：

void test_vs_vector5()
{
    std::vector v1;
    v1.push_back(1);
    v1.push_back(2);
    v1.push_back(2);
    v1.push_back(2);
    v1.push_back(3);
    v1.push_back(4);
    cout << v1.size() << " " << v1.capacity() << endl;
    for (auto e : v1)
    {
        cout << e << " ";
    }
    cout << endl;
    auto it = v1.begin();
    while (it != v1.end())
    {
        if (*it % 2 == 0)
        {
            it = v1.erase(it);
        }
        else
        {
            ++it;
        }
    }
    for (auto e : v1)
    {
        cout << e << " ";
    }
    cout << endl;
    cout << v1.size() << " " << v1.capacity() << endl;
}

总结：

erase(pos)以后，pos失效了，pos的意义发生改变，但是在不同平台下面对于访问pos反应不同。
我们用的时候一定要小心，统一以失效的角度去看待。

对于insert和erase造成的迭代器失效问题：
Linux g++平台检查佛系，基本只是依靠操作系统自身的野指针越界检查机制。
Windows下的VS系列检查更加严格，使用了一些强制检查机制，即使只是意义变了也可能会检查出来。

string也是有迭代器失效的问题的，但我们用string的insert、erase基本都是用的下标版本，因此也就不关心迭代器失效问题。

更深层次深拷贝

先用std试一下：

class Solution3 {
    public:
    std::vector> generate(int numRows) {
        std::vector> vv;
        vv.resize(numRows); // 设置总共的行数，默认都初始化为0
        for (size_t i = 0; i < vv.size(); ++i)
        {
            // 每一行i+1个数
            vv[i].resize(i + 1);
            // vv[i][0] = 1, vv[i][vv[i].size()-1] = 1;
            vv[i].front() = 1, vv[i].back() = 1; //利用函数也行
        }

        for (size_t i = 0; i < vv.size(); ++i)
        {
            for (size_t j = 0; j < vv[i].size(); ++j)
            {
                if (vv[i][j] == 0)
                {
                    vv[i][j] = vv[i - 1][j - 1] + vv[i - 1][j];
                }
            }
        }

        return vv;
    }
};

void test_yzq_vector9()
{
    std::vector> vv = Solution3().generate(5);
    for (size_t i = 0; i < vv.size(); ++i)
    {
        for (size_t j = 0; j < vv[i].size(); ++j)
        {
            cout << vv[i][j] << " ";
        }
        cout << endl;
    }
}

再换成我们自己写的：

出现了死循环。

通过验证发现，函数内部是没有问题，问题出在return上面。

这是一个传值返回，会进行一次拷贝构造，再进行构造，但被编译器优化以后，直接进行构造了。

总结：
vector中，当T是涉及深拷贝的类型，如string、vector等类型时，扩容使用的memcpy拷贝数据是存在浅拷贝问题的。

解决办法：
不要用memcpy一个一个拷贝数据就行。

源代码

#pragma once
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;

namespace yzq
{
	template
	class vector
	{
	public:
		typedef T* iterator;
		typedef const T* const_iterator;

		vector()
			:_start(nullptr)
			, _finish(nullptr)
			, _endofstorage(nullptr)
		{}

		template
		vector(InputIterator first, InputIterator last)
			: _start(nullptr)
			, _finish(nullptr)
			, _endofstorage(nullptr)
		{
			while (first != last)
			{
				push_back(*first);
				++first;
			}
		}

		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);
			}
		}

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

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

		vector(const vector& v)
			: _start(nullptr)
			, _finish(nullptr)
			, _endofstorage(nullptr)
		{
			vector tmp(v.begin(), v.end());
			swap(tmp);
			//this->swap(tmp); 等价
		}

		vector& operator=(vector v)
		{
			this->swap(v);
			return *this;
		}

		~vector()
		{
			if (_start)
			{
				delete[] _start;
				_start = _finish = _endofstorage = nullptr;
			}
		}

		iterator begin()
		{
			return _start;
		}

		iterator end()
		{
			return _finish;
		}

		const_iterator begin() const
		{
			return _start;
		}

		const_iterator end() const
		{
			return _finish;
		}

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

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

		void reserve(size_t n)
		{
			size_t sz = size();
			// 不考虑缩容的问题
			if (n > capacity())
			{
				T* tmp = new T[n];
				if (_start) // 有数据才拷贝
				{
					//mcpy(tmp, _start, size() * sizeof(T)); 存在浅拷贝问题 要一个一个拷贝
					for (size_t i = 0; i < size(); ++i)
					{
						tmp[i] = _start[i]; // 如果涉及深拷贝，会去调用自己的赋值重载完成深拷贝
					}
					delete[] _start;
				}
				_start = tmp;
			}

			//_finish = _start + size(); // size()的计算出现了错误，_start已经改变了
			//_endofstorage = _start + capacity();
			_finish = _start + sz;
			_endofstorage = _start + n;
		}

		//void resize(size_t n, T val = T()) T()是生成匿名对象，调用默认构造函数
		// 注意：C++的内置类型也是有默认构造函数的 int的就是0 double的就是0.0
		void resize(size_t n, const T& val = T())
		{
			// 3种情况
			// 大于capacity
			if (n > capacity())
			{
				reserve(n);
			}
			// 大于size小于capacity
			if (n > size())
			{
				while (_finish < _start + n)
				{
					*_finish = val;
					++_finish;
				}
			}
			else // 小于size
			{
				_finish = _start + n;
			}
		}

		// 传引用减少开销，不改变就加const
		void push_back(const T& x)
		{
			
			// 复用insert
			insert(end(), x);
		}

		void pop_back()
		{
			
			//复用erase
			erase(end() - 1);
			// 不能--end() end返回的临时对象具有常性
		}

		T& operator[](size_t pos)
		{
			assert(pos < size());
			return _start[pos];
		}

		const T& operator[](size_t pos) const
		{
			assert(pos < size());
			return _start[pos];
		}

		iterator insert(iterator pos, const T& x)
		{
			assert(pos >= _start && pos <= _finish);
			// 考虑扩容
			// 扩容后pos失效了，利用相对距离更新pos
			if (_finish == _endofstorage)
			{
				size_t n = pos - _start;
				size_t newCapacity = capacity() == 0 ? 4 : capacity() * 2;
				reserve(newCapacity);
				pos = _start + n;
			}

			// 挪动数据
			iterator end = _finish - 1;
			while (end >= pos)
			{
				*(end + 1) = *end;
				--end;
			}
			*pos = x;
			++_finish;

			return pos;
		}

		// 要考虑到实现者有可能对erase实现缩容，而缩容开辟新空间会改变pos位置
		// 因此需要返回迭代器
		iterator erase(iterator pos)
		{
			assert(pos >= _start && pos < _finish);
			iterator it = pos + 1;
			while (it != _finish)
			{
				*(it - 1) = *it;
				++it;
			}
			--_finish;
			return pos;
		}

		void clear()
		{
			_finish = _start;
		}

	private:
		iterator _start;
		iterator _finish;
		iterator _endofstorage;
	};
}

尾声



写文不易，如果有帮助烦请点个赞~ 

Thanks♪(･ω･)ﾉ



由于笔者水平有限，在今后的博文中难免会出现错误之处，本人非常希望您如果发现错误，恳请留言批评斧正，希望和大家一起学习，一起进步ヽ(￣ω￣(￣ω￣〃)ゝ，期待您的留言评论。
附GitHub仓库链接