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

    文章目录

    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.常用接口

    构造函数

    构造函数文档

    image-20220808173620723

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

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

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

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9

    利用迭代器区间初始化：

    image-20220721201216830

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

	vector<double> v2;
	v2.push_back(1.1);
	v2.push_back(2.2);
	v2.push_back(3.3);

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

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

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

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26

    遍历

    void test_vector2()
{
	// 遍历
	vector<int> 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<int>::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;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35

    遍历二维的：

    image-20220722103603875

    void test_vector9()
{
	vector<vector<int>> 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;
	}
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12

    在这里插入图片描述

    扩容机制

    // 查看扩容情况
void test_vector4()
{
	size_t sz;
	std::vector<int> 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';
		}
	}
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16

    image-20220721203301998

    Linux下g++版本：

    在这里插入图片描述

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

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

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

    resize：开空间+初始化。

    1. 当所给值大于容器当前的size时，将size扩大到该值，扩大的元素为第二个所给值，若未给出，则默认为0。
    2. 当所给值小于容器当前的size时，将size缩小到该值。
    void test_vector5()
{
	vector<int> 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;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31

    image-20220721205744898

    缩容

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

    image-20220721210346140

    void test_vector6()
{
	std::vector<int> 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;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11

    image-20220721210640011

    shrink_to_fit()

    image-20220721210822826

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

    插入删除

    image-20220808175252013

    image-20220808175217314

    void test_vector7()
{
	// 遍历
	vector<int> 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;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41

    在这里插入图片描述

    find

    find文档

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

    image-20220721230656311

    注意，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 myints\n";

    // using std::find with vector and iterator:
    std::vector<int> myvector (myints,myints+4);
    std::vector<int>::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 myvector\n";

    return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27

    sort

    在这里插入图片描述

    注意：默认是ascending order

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

bool myfunction (int i,int j) { return (i<j); }

struct myclass {
    bool operator() (int i,int j) { return (i<j);}
} myobject;

int main () {
    int myints[] = {32,71,12,45,26,80,53,33};
    std::vector<int> 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<int>::iterator it=myvector.begin(); it!=myvector.end(); ++it)
        std::cout << ' ' << *it;
    std::cout << '\n';

    return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    void test_vector8()
{
	vector<int> 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<int>()); // > 就是降序
	for (auto e : v)
	{
		cout << e << " ";
	}
	cout << endl;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35

    image-20220721233621890

    3.vector模拟实现

    SGI版本源码

    stl_vector.h

    欣赏一下核心框架：
    image-20220723161939061

    在这里插入图片描述

    构造函数

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

template<class InputIterator>
    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<int> v;
    v.push_back(1);
    v.push_back(2);
    v.push_back(3);
    v.push_back(4);
    yzq::vector<int> v1(v.begin(), v.end());
    for (auto e : v1)
    {
        cout << e << " ";
    }
    cout << endl;
    yzq::vector<char> v2(s.begin(), s.end());
    for (auto e : v2)
    {
        cout << e << " ";
    }
    cout << endl;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39

    再写一个：

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

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20

    怎么突然编译错误了呢？

    image-20220724102933892

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

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

    在这里插入图片描述

    看一下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);
        }
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11

    image-20220724104646772

    深拷贝

    现代写法。

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

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

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

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

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44

    注意：

    image-20220724102039540

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

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

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19

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

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20

    resize

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

    image-20220723162033781

    // 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<int> v1;
	// 更多的还是利用resize完成初始化
	v1.resize(15, -2);
	for (auto e : v1)
	{
		cout << e << " ";
	}
	cout << endl;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35

    insert

    image-20220723165544390

    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
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20

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

    在这里插入图片描述

    感觉没毛病。

    image-20220723164253324

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

    迭代器失效

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

    image-20220723170110128

    image-20220723170118747

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

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23

    再举个例子👇

    void test_yzq_vector4()
{
	// 在所有的偶数前面插入一个20
	yzq::vector<int> 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<int>::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;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25

    image-20220723170934864

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

    image-20220723171802823

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

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

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

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

    image-20220723172551112

    尽管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<int> 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<int>::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;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52

    image-20220723173439300

    不同平台对比：

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

    image-20220723210024890

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

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46

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

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

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

    再来个例子：删除偶数

    void test_vs_vector5()
{
    std::vector<int> 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;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30

    在这里插入图片描述

    VS、Linux下均会出现错误。

    正确代码：

    void test_vs_vector5()
{
    std::vector<int> 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;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34

    image-20220724003228968

    总结：

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

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

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

    更深层次深拷贝

    先用std试一下：

    class Solution3 {
    public:
    std::vector<vector<int>> generate(int numRows) {
        std::vector<vector<int>> 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<vector<int>> 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;
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40

    image-20220724105520790

    再换成我们自己写的：
    image-20220724105613220
    出现了死循环。

    通过验证发现，函数内部是没有问题，问题出在return上面。
    image-20220724111041309
    这是一个传值返回，会进行一次拷贝构造，再进行构造，但被编译器优化以后，直接进行构造了。
    在这里插入图片描述

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

    解决办法：
    不要用memcpy一个一个拷贝数据就行。
    在这里插入图片描述

    image-20220724114044045
    在这里插入图片描述

    源代码

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

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

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

		template<class InputIterator>
		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<T>& v)
		{
			std::swap(_start, v._start);
			std::swap(_finish, v._finish);
			std::swap(_endofstorage, v._endofstorage);
		}

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

		vector<T>& operator=(vector<T> 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)
		{
			/*
			if (_finish == _endofstorage)
			{
				size_t newCapacity = capacity() == 0 ? 4 : capacity() * 2;
				reserve(newCapacity);
			}

			*_finish = x;
			++_finish;
			*/
			// 复用insert
			insert(end(), x);
		}

		void pop_back()
		{
			/*
			if (_finish > _start)
			{
				--_finish;
			}
			*/
			//复用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;
	};
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122
    • 123
    • 124
    • 125
    • 126
    • 127
    • 128
    • 129
    • 130
    • 131
    • 132
    • 133
    • 134
    • 135
    • 136
    • 137
    • 138
    • 139
    • 140
    • 141
    • 142
    • 143
    • 144
    • 145
    • 146
    • 147
    • 148
    • 149
    • 150
    • 151
    • 152
    • 153
    • 154
    • 155
    • 156
    • 157
    • 158
    • 159
    • 160
    • 161
    • 162
    • 163
    • 164
    • 165
    • 166
    • 167
    • 168
    • 169
    • 170
    • 171
    • 172
    • 173
    • 174
    • 175
    • 176
    • 177
    • 178
    • 179
    • 180
    • 181
    • 182
    • 183
    • 184
    • 185
    • 186
    • 187
    • 188
    • 189
    • 190
    • 191
    • 192
    • 193
    • 194
    • 195
    • 196
    • 197
    • 198
    • 199
    • 200
    • 201
    • 202
    • 203
    • 204
    • 205
    • 206
    • 207
    • 208
    • 209
    • 210
    • 211
    • 212
    • 213
    • 214
    • 215
    • 216
    • 217
    • 218
    • 219
    • 220
    • 221
    • 222
    • 223
    • 224
    • 225
    • 226
    • 227
    • 228
    • 229
    • 230
    • 231
    • 232
    • 233
    • 234
    • 235
    • 236
    • 237
    • 238
    • 239
    • 240
    • 241
    • 242
    • 243
    • 244
    • 245
    • 246
    • 247
    • 248
    • 249
    • 250
    • 251
    • 252
    • 253
    • 254
    • 255
    • 256
    • 257
    • 258
    • 259
    • 260
    • 261
    • 262
    • 263
    • 264
    • 265
    • 266
    • 267

    尾声

    🌹🌹🌹

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

    Thanks♪(･ω･)ﾉ🌹🌹🌹

    😘😘😘

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

  • 相关阅读:
    文章解读与仿真程序复现思路——电网技术EI\CSCD\北大核心《适应分布式资源渗透率提高的配电网网元规划方法》
    【面试题】从输入URL到游览器渲染完成，经历了什么
    简单解析hyperf-TCP-RPC-Json请求的数据结构
    【Spark NLP】第 5 章：处理词
    离线数仓（6）：数仓理论之维度模型分类
    使用HTML+CSS技术制作篮球明星介绍网站
    具有 1 个射频链的 OFDM-MIMO 系统的波束训练（Matlab代码实现）
    JavaScript期末大作业 基于HTML+CSS+JavaScript技术制作web前端开发个人博客(48页)
    使用nvm-windows在Windows下轻松管理多个Node.js版本
    Excel如何给数字加双引号或者加单引号加逗号
  • 原文地址：https://blog.csdn.net/a2076188013/article/details/126253679