• C++ vector的使用和简单模拟实现（超级详细！！！）

    目录

    前言

    1.STL是什么

    2.vector使用

    2.1 vector简介

    2.2 常用接口函数

    1. 构造函数

    2.operator[ ]和size，push_back

    3. 用迭代器进行访问和修改

    4. 范围for遍历

    5.修改类型函数 pop_back find insert erase

    6. 容量相关函数capacity resize reserve

    3. vector模拟实现

    3.1 模版问题

    3.2 vector成员变量和迭代器

    3.3 capacity，size，operator[ ]

    3.3 push_back和reserve函数

    3.5 构造函数，析构函数

    3.6 拷贝构造函数和赋值拷贝函数

    3.7 insert和erase

    3.8 迭代器失效问题

    总结

    前言

    今天将开启对C++STL的学习，STL作为强大的模版库，十分值得我们学习！在此途中，提升自己的C++代码能力。

    1.STL是什么

    标准模板库（Standard Template Library，STL）是惠普实验室开发的一系列软件的统称。它是由Alexander Stepanov、Meng Lee和David R Musser在惠普实验室工作时所开发出来的。STL是C++标准库的重要组成部分，不仅是一个可复用的组件库，而且是一个包罗数据结构与算法的软件框架。

    STL版本

    • 原始版本：Alexander Stepanov、Meng Lee 在惠普实验室完成的原始版本，并且是开源的，HP 版本--所有STL实现版本的始祖。
    • P. J. 版本：由P. J. Plauger开发，继承自HP版本，不开源。
    • RW版本：由Rouge Wage公司开发，继承自HP版本，不开源。
    • SGI版本：由Silicon Graphics Computer Systems，Inc公司开发，继承自HP版 本。被GCC(Linux)采用，是开源的。

    STL有六大组件：

    2.vector使用

    2.1 vector简介

    vector是表示可变大小数组的序列容器。就像数组一样，vector也采用的连续存储空间来存储元素。也就意味着可以采用下标对vector的元素进行访问，和数组一样高效。但是又不像数组，它的大小是可以动态改变的，而且它的大小会被容器自动处理。

    因为vector内部实现没有使用具体类型，而是给出模版，所以实例化一个vector变量时需要给出具体类型。记得包含头文件。

    2.2 常用接口函数

    1. 构造函数

    1. vector(const allocator_type& alloc = allocator_type());//函数原型
    2.  
    3. void test_vector()
    4. {
    5.     vector<int> v1;
    6. }
    • 默认构造函数：构造一个没有元素的空容器。在test_vector函数内定义一个int类型的空容器。

    tip：其中的allocator是空间适配器，用于分配内存空间的，暂时不用深究。

    1. vector (size_type n, const value_type& val = value_type(),
    2.         const allocator_type& alloc = allocator_type());
    3.  
    4. void test_vector()
    5. {
    6.     vector<int> v1(10, 1);
    7. }
    • 填充构造函数:构造一个包含n个元素的容器。每个元素都是val的一个副本。
    • test_vector函数中，实例化了一个int类型的vector容器，里面有10个1整型变量。

    1. template <class InputIterator>
    2.          vector (InputIterator first, InputIterator last,
    3.                  const allocator_type& alloc = allocator_type());
    4.  
    5. void test_vector()
    6. {
    7.     vector<int> v1(10, 1);
    8.     vector<int> v2(v1.begin(), v1.end());
    9. }
    • 迭代器构造函数：构造一个包含与[first,last)范围相同数量元素的容器，每个元素以相同的顺序从该范围内的相应元素构造。

    1. vector (const vector& x);
    2.  
    3. void test_vector()
    4. {
    5.     vector<int> v1(10, 1);
    6.     vector<int> v2(v2);
    7. }
    •  拷贝构造函数：用x中每个元素的副本按相同顺序构造一个容器。

    2.operator[ ]和size，push_back

    vector是一个类似数组的容器，物理存储上是连续的，那自然少不了下标访问。

    • push_back函数，望文生义就是在尾部插入一个元素。
    • size函数是获取当前容器元素个数。
    • [ ]是可以访问填入下标的元素，并进行修改。
    1. void test_vector1()
    2. {
    3.     vector<int> v1;
    4. 	v1.push_back(1);
    5. 	v1.push_back(2);
    6. 	v1.push_back(3);
    7. 	v1.push_back(4);
    8.  
    9. 	for (size_t i = 0; i < v1.size(); i++)
    10. 	{
    11. 		cout << v1[i] << " ";
    12. 	}
    13. 	cout << endl;
    14. }

     运行结果如下：

    3. 用迭代器进行访问和修改

    使用迭代器前，我们需要了解什么是迭代器。

    在C++中，迭代器（Iterator）是一种检查容器中元素并遍历元素的数据类型。迭代器提供了一种通用的方式来访问容器中的元素，而不需要关心容器底层的具体数据结构。通过迭代器，可以对容器进行遍历、读取、修改和删除元素等操作。

    • 使用迭代器时，需要定义一个变量，变量类型就是int类型下的vector容器中的iterator类。不管vector容器中具体类型是什么。在vector中，约定俗成迭代器类型名是iterator。
    • 定义迭代器变量后，赋值为vector成员函数begin，在vector中，指向第一个元素。还有end函数，表示最后一个元素的下一个位置。
    • 还有!=，前置++，!=和*操作符，++表示往后指向下一个元素，*操作类似于指针的解引用操作，代表该元素。但是自定义类型没有这些操作，都是通过运算符重载的方式，将其的行为编程跟指针变量相类似的操作。
    • 你可以类比成指针，但是iterator这个类型不一定是指针，可能还是一个类。
    1. void test_vector2()
    2. {
    3.     vector<int> v1;
    4. 	v1.push_back(1);
    5. 	v1.push_back(2);
    6. 	v1.push_back(3);
    7. 	v1.push_back(4);
    8.  
    9. 	vector<int>::iterator it1 = v1.begin();
    10. 	while (it1 != v1.end())
    11. 	{
    12. 		cout << *it1 << " ";
    13. 		++it1;
    14. 	}
    15. 	cout << endl;
    16.  
    17.     it1 = v1.begin();
    18.     while (it1 != v1.end())
    19. 	{
    20.         ++*it1;//对容器元素进行修改
    21. 		cout << *it1 << " ";
    22. 		++it1;
    23. 	}
    24. 	cout << endl;
    25.  
    26.     //全部展开成运算符重载函数
    27. 	it1.operator=(v1.begin());
    28. 	while (it1.operator!=(v1.end()))
    29. 	{
    30. 		cout << it1.operator*() << " ";
    31. 		it1.operator++();
    32. 	}
    33. 	cout << endl;
    34. }

     上面最后一段代码将这些运算符写成调用函数的形式，也可以进行遍历，但是代码的可读性比较差。运行结果如下：

    但是有些情况下，只是遍历数据进行打印，不想修改元素。如果使用一般迭代器iterator，会导致权限放大，误改其中的元素。我们可以使用const_iterator，对该类型的容器进行访问，即使不小心修改，系统也会报错。

    1. void test_vector3()
    2. {
    3. 	vector<int> v1;
    4. 	v1.push_back(1);
    5. 	v1.push_back(2);
    6. 	v1.push_back(3);
    7. 	v1.push_back(4);
    8.  
    9. 	vector<int>::const_iterator it1 = v1.begin();
    10. 	while (it1 != v1.end())
    11. 	{
    12.         //*it = 5  error,不可以修改
    13. 		cout << *it1 << " ";
    14. 		++it1;
    15. 	}
    16. 	cout << endl;
    17. }

    运行结果如下：

    迭代器不仅可以正向遍历，还有反向迭代器，倒着遍历。跟正向迭代器类似，也有可修改和不可修改两种反向迭代器。

    1. void test_vector4()
    2. {
    3. 	vector<int> v1;
    4. 	v1.push_back(1);
    5. 	v1.push_back(2);
    6. 	v1.push_back(3);
    7. 	v1.push_back(4);
    8.  
    9. 	vector<int>::reverse_iterator it1 = v1.rbegin();
    10. 	while (it1 != v1.rend())
    11. 	{
    12. 		*it1 += 4;
    13. 		cout << *it1 << " ";
    14. 		++it1;
    15. 	}
    16. 	cout << endl;
    17.  
    18. 	vector<int>::const_reverse_iterator it2 = v1.rbegin();
    19. 	while (it2 != v1.rend())
    20. 	{
    21. 		//*it2 = 1  error
    22. 		cout << *it2 << " ";
    23. 		++it2;
    24. 	}
    25. 	cout << endl;
    26. }

    运行结果如下：

    4. 范围for遍历

    范围for是一个比较实用的语法，支持遍历各种容器，但是只能正向遍历。

    • 范围for看起来十分高级，但是最终的底层逻辑，还是跟迭代器相关，只要相关容器提供了begin和end函数，就支持遍历。
    1. void Test()
    2. {
    3. 	vector<int> v1;
    4. 	v1.push_back(1);
    5. 	v1.push_back(2);
    6. 	v1.push_back(3);
    7. 	v1.push_back(4);
    8.  
    9. 	for (auto e : v1)
    10. 	{
    11. 		cout << e << " ";
    12. 	}
    13. 	cout << endl;
    14.  
    15.     //想要修改内容需要使用引用
    16. 	for (auto& e : v1)
    17. 	{
    18. 		e++;
    19. 		cout << e << " ";
    20. 	}
    21. 	cout << endl;
    22. }

    运行结果如下：

    5.修改类型函数 pop_back find insert erase

    • pop_back函数，是删除最后一个元素，效率高。如果容器为空继续删除，会直接终止程序。发出断言警告。

    之后的Print函数就是正向输出容器中的所有元素。

    1. void Print(vector<int>& v)
    2. {
    3. 	vector<int>::iterator it1 = v.begin();
    4. 	while (it1 != v.end())
    5. 	{
    6. 		cout << *it1 << " ";
    7. 		++it1;
    8. 	}
    9. 	cout << endl;
    10. }
    11.  
    12. void test_vector5()
    13. {
    14. 	vector<int> v1;
    15. 	v1.push_back(1);
    16. 	v1.push_back(2);
    17. 	v1.push_back(3);
    18. 	v1.push_back(4);
    19. 	Print(v1);
    20.  
    21. 	v1.pop_back();
    22. 	v1.pop_back();
    23. 	Print(v1);
    24. }

    运行结果如下：

    find，insert和erase 

    1. template <class InputIterator, class T>
    2. InputIterator find (InputIterator first, InputIterator last, const T& val);
    •  find函数，给两个相同的类型的迭代器，范围是从first位置的元素到last前一个位置的元素，是一个左闭右开的区间[first, last)，寻找与val相同的元素，并返回该元素位置的迭代器。如果没有找到，返回last迭代器。

    1. //1.
    2. iterator insert (iterator position, const value_type& val);
    3. //2.
    4. void insert (iterator position, size_type n, const value_type& val);
    5. //3.
    6. template <class InputIterator>
    7. void insert (iterator position, InputIterator first, InputIterator last);

    insert函数原型如下，有三种类型。

    • 第一种是传插入位置的迭代器变量，插入值为val。
    • 第二种是传插入位置的迭代器变量，但是插入n个val元素进去。
    • 第三种是传插入位置的迭代器变量，但插入的元素是别的容器的元素，范围是从first位置的元素到last前一个位置的元素，是一个左闭右开的区间[first, last)。

    1. //1.
    2. iterator erase (iterator position);
    3. //2.
    4. iterator erase (iterator first, iterator last);
    • erase函数有两种类型
    • 第一种是删除一个指定位置的元素，只用传该元素位置的迭代器。
    • 第二种是删除某个范围内的元素，传入first迭代器和last迭代器，是一个左闭右开的区间[first, last)。
    1. void test_vector6()
    2. {
    3. 	int arr[] = { 1,2,3,4,5,6,};
    4. 	vector<int> v1(arr, arr + 6);
    5. 	Print(v1);
    6.  
    7. 	vector<int>::iterator pos = find(v1.begin(), v1.end(), 4);
    8. 	v1.insert(pos, 20);
    9. 	Print(v1);
    10.  
    11. 	pos = find(v1.begin(), v1.end(), 5);
    12. 	v1.insert(pos, 2, 10);
    13. 	Print(v1);
    14.  
    15. 	vector<int> v2;
    16. 	v2.insert(v2.begin(), v1.begin(), v1.end());
    17. 	Print(v2);
    18.  
    19. 	pos = find(v1.begin(), v1.end(), 6);
    20. 	v1.erase(pos);
    21. 	Print(v1);
    22.  
    23. 	v2.erase(v2.begin(), --v2.end());
    24. 	Print(v2);
    25. }

    运行结果如下：

    6. 容量相关函数capacity resize reserve

    • capacity函数是获取该容器的容量大小。我们设计一个函数测试vector的扩容机制，分别在VS和Linux环境下进行测试。
    1. void TestExpand()
    2. {
    3. 	size_t sz;
    4. 	vector<int> v;
    5. 	sz = v.capacity();
    6. 	cout << "making v grow:\n";
    7. 	for (int i = 0; i < 100; ++i)
    8. 	{
    9. 		v.push_back(i);
    10. 		if (sz != v.capacity())
    11. 		{
    12. 			sz = v.capacity();
    13. 			cout << "capacity changed: " << sz << '\n';
    14. 		}
    15. 	}
    16. }

    在VS环境下，扩容情况如下图所示。一开始，插入四个元素时，每次扩容只增加一个容量。插入第五个元素开始就是1.5倍扩容的速度。

    在Linux环境下，我们可以看到是遵循2倍扩容的原则进行扩容。

    void resize (size_type n, value_type val = value_type());
    • resize可以调整容器元素个数的大小，使其包含n个元素。
    • 如果n小于当前容器元素个数，则内容减少到前n个元素，并删除超出的元素。
    • 如果n大于当前容器元素个数，则通过尾插插入所需元素，扩展内容，以达到n的大小。如果有给定val，插入元素就为val，否则将其进行值初始化（自定义类型调用默认构造函数，自定义类型也有自己的初始化）。如果超过容器容量大小，会扩容。

    比如说，你创建了一个含有四个元素容器。如果用下标访问该容器元素，下标值范围是0~3，不能超出这个范围。当你想使用下标给第五个元素赋值，就会断言报错。此时就可以使用resize函数，将容器元素个数扩充，便可以使用下标给之后的元素赋值。

    1. void test_vector7()
    2. {
    3. 	int arr[] = { 1,2,3,4 };
    4. 	int size = sizeof(arr) / sizeof(int);
    5. 	vector<int> v1(arr, arr + size);
    6.  
    7. 	//v1[4] = 0; //error
    8.  
    9. 	v1.resize(8);
    10. 	v1[4] = 1;
    11. 	v1[5] = 2;
    12. 	v1[6] = 3;
    13. 	v1[7] = 4;
    14. 	Print(v1);
    15. }

    运行结果如下：

    void reserve (size_type n);
    • reserve是调整容器容量大小。
    • 只用传一个无符号整型参数。如果n大于当前容器的容量，会给该容器重新分配存储空间，将其容量增加到n。在其他情况下，函数调用不会导致重新分配，容器容量不变。
    • reserve不会对容器里的元素做出改变，容器元素个数不变。

    在上面测试不同平台下vector的扩容机制，扩容的本质是开辟新空间，将原来容器的内容拷贝过去，再释放原有的空间。如果要频繁插入数据，就会频繁的扩容，会造成许多消耗，所以如果知道要插入数据个数，可以一次性扩容完毕，减少不必要的消耗。

    1. void TestExpand()
    2. {
    3. 	size_t sz;
    4. 	vector<int> v;
    5. 	sz = v.capacity();
    6. 	v.reserve(100); // 提前将容量设置好，可以避免一遍插入一遍扩容
    7. 	cout << "making v grow:\n";
    8. 	for (int i = 0; i < 100; ++i)
    9. 	{
    10. 		v.push_back(i);
    11. 		if (sz != v.capacity())
    12. 		{
    13. 			sz = v.capacity();
    14. 			cout << "capacity changed: " << sz << '\n';
    15. 		}
    16. 	}
    17. }

    在VS中，运行结果如下：

    3. vector模拟实现

    3.1 模版问题

    1. 模拟实现vector会用到类型模版，一般建议将实现的函数内容都放在一个头文件中。因为给定一个参数类型实例化vector容器时，这个过程发生编译的期间，如果函数的声明和定义分离，放在两个文件中，编译器无法根据这个类型进行代码分发。
    2. 直接创建一个vector.h的头文件。还有为了不和C++标准库里面的vector发生命名冲突，可以自己创建一个命名空间User。再包含上需要的头文件。
    1. #include 
    2.  
    3. namespace User
    4. {
    5.     template <class T>
    6.     class vector
    7.     {
    8.         //...
    9.     };
    10.  
    11. }

    3.2 vector成员变量和迭代器

    • vector类内部通常有三个迭代器类型的成员变量。
    • _start指向第一个元素，_finish指向末尾元素的后一位，_end_of_storage表示容器容量末尾。
    1. #include 
    2.  
    3. namespace User
    4. {
    5.     template <class T>
    6.     class vector
    7.     {
    8.  
    9.     private:
    10. 	    iterator _start;
    11. 	    iterator _finish; 
    12. 	    iterator _end_of_storage; 
    13.     };
    14.  
    15. }

    因为vector物理存储和逻辑存储都是连续的，所以我们可以将他的迭代器类型用原生指针实现。

    1. typedef T* iterator;
    2. typedef const T* const_iterator;

    再提供begin和end函数，返回容器第一个元素的位置和末尾元素的后一位。其中const_iterator类型的迭代器，需要保证容器元素不能被修改，需要在函数后加上const，成为const成员函数。

    1. const_iterator begin() const
    2. {
    3. 	return _start;
    4. }
    5.  
    6. const_iterator end() const
    7. {
    8. 	return _finish;
    9. }
    10.  
    11. iterator begin()
    12. {
    13. 	return _start;
    14. }
    15.  
    16. iterator end()
    17. {
    18. 	return _finish;
    19. }

    3.3 capacity，size，operator[ ]

    • 指针相减可以得到其中该类型元素个数之差。因此size和capacity，分别用_finish和 _end_of_storage指针减去_start指针，就可以实现。
    1. size_t size() const
    2. {
    3. 	return _finish - _start;
    4. }
    5.  
    6. size_t capacity() const
    7. {
    8. 	return _end_of_storage - _start;
    9. }
    • operator[ ]实际上返回_start指针用下标访问的元素即可，及得要先检查i的大小，是否符合要求。还提供了const类型的[ ]重载。
    1. T& operator[](size_t i)
    2. {
    3. 	assert(i < size());
    4.  
    5. 	return _start[i];
    6. }
    7.  
    8. T& operator[](size_t i) const
    9. {
    10. 	assert(i < size());
    11.  
    12. 	return _start[i];
    13. }

    3.3 push_back和reserve函数

    我们先完成一个尾插和扩容的函数，之后的构造函数就依靠这个接口进行初始化。

    • push_back是在末尾插入元素，一开始需要检查容器容量大小够不够在插入多一个元素。如果_finish指针与_end_of_storage指针相等时，说明容量不够，需要扩容。扩容时先判断capacity是否为零，为零还没插入数据，给四个元素空间，之后就是两倍扩容。
    • 再讲一下扩容的逻辑，首先判断传递的参数n是否大于当前容量，如果大于才能继续扩容，出现其他情况不做处理。扩容一般动态开辟一块为n个T类型参数大小的内存空间，然后将原有的数据拷贝过来，在释放原有空间内存。
    • 其重要注意需要先记录之前空间的元素个数，方便之后调整_finish指针的位置。
    1. void reserve(size_t n)
    2. {
    3. 	if (n > capacity())
    4. 	{
    5. 		T* tmp = new T[n];
    6. 		size_t oldsize = size();
    7. 		if (_start)
    8. 		{
    9. 			memcpy(tmp, _start, sizeof(T) * size());
    10. 			delete[] _start;
    11. 		}
    12.  
    13. 		_start = tmp;
    14. 		_finish = _start + oldsize;
    15. 		_end_of_storage = _start + n;
    16. 	}
    17. }
    18.  
    19. void push_back(const T& x)
    20. {
    21. 	if (_finish == _end_of_storage)
    22. 	{
    23. 		//两倍速扩容
    24. 		size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;
    25. 		reserve(newcapacity);
    26. 	}
    27.  
    28. 	*_finish = x;
    29. 	++_finish;
    30. }

    写一个测试函数，测试一下之前实现的各种接口函数，用正常的for循环遍历，迭代器遍历，还有范围for进行遍历。

    1. void test_vector1()
    2. {
    3. 	vector<int> v1;
    4. 	v1.push_back(1);
    5. 	v1.push_back(2);
    6. 	v1.push_back(3);
    7. 	v1.push_back(4);
    8.  
    9. 	for (size_t i = 0; i < v1.size(); i++)
    10. 	{
    11. 		cout << v1[i] << " ";
    12. 	}
    13. 	cout << endl;
    14.  
    15. 	vector<int>::iterator it = v1.begin();
    16. 	while (it != v1.end())
    17. 	{
    18. 		cout << *it << " ";
    19. 		++it;
    20. 	}
    21. 	cout << endl;
    22.  
    23. 	for (auto e : v1)
    24. 	{
    25. 		cout << e << " ";
    26. 	}
    27. 	cout << endl;
    28. }

    测试结果如下：

     但是reserve函数实现就没有问题吗？看看下面的测试函数

    1. void test_vector2()
    2. {
    3. 	vector v1;
    4. 	v1.push_back("xxxxxxxxxx");
    5. 	v1.push_back("xxxxxxxxxx");
    6. 	v1.push_back("xxxxxxxxxx");
    7. 	v1.push_back("xxxxxxxxxx");
    8. 	v1.push_back("xxxxxxxxxx");
    9.  
    10. 	for (auto e : v1)
    11. 	{
    12. 		cout << e << " ";
    13. 	}
    14. 	cout << endl;
    15. }

    当你运行这段代码的时候，打印前面四个元素会出现乱码。这是为什么呢？

    如下图所示，tmp拷贝过来的内容，把指针变量也原封不动按字节拷贝，导致_start和tmp中的_str指针指向同一块空间。之后，会delete[ ] _start，而delete释放空间之前，会调用里面自定义类型的析构函数，再释放这个空间，这就会造成我们数据的丢失。

    • 所以要进行一个深拷贝，写一个for循环，传统写法是赋值，如果是内置类型直接赋值，如果是自定义类型，调用该类型的赋值拷贝函数。
    • 现代的写法是直接将tmp[i]与_start[i]进行交换，直接调用C++标准库里的交换函数，交换的好处是不用再拷贝值，并且delete掉_start里面没有自定义类型，不用调用析构函数。
    1. void reserve(size_t n)
    2. {
    3. 	if (n > capacity())
    4. 	{
    5. 		T* tmp = new T[n];
    6. 		size_t oldsize = size();
    7. 		if (_start)
    8. 		{
    9. 			for (size_t i = 0; i < oldsize; i++)
    10. 			{
    11. 				//tmp[i] = _start[i];//传统写法
    12. 				std::swap(tmp[i], _start[i]);
    13. 			}
    14. 			delete[] _start;
    15. 		}
    16.  
    17. 		_start = tmp;
    18. 		_finish = _start + oldsize;
    19. 		_end_of_storage = _start + n;
    20. 	}
    21. }

    3.5 构造函数，析构函数

    vector构造函数我们三个，其中一个是给定个数n，给定T类型的x变量，进行初始化。

    • 为什么这个会重载成两个呢？因为有的时候传参可能是int或者size_t类型,编译器无法判断，需要重载成两个构造函数。
    • 我们可以用传统的方式，开辟空间，进行赋值，然后再赋值成员变量。不过也可以使用我们实现好的push_back函数接口，因为符合尾插的特点，不过在尾插时，可以先扩容，这样就不会频繁扩容，提升效率。
    1. vector(size_t n, const T& x = T())
    2. {
    3. 	reserve(n);
    4. 	for (size_t i = 0; i < n; i++)
    5. 	{
    6. 		push_back(x)
    7. 	}
    8. }
    9.  
    10. vector(int n, const T& val = T())
    11. {
    12. 	reserve(n);
    13. 	for (int i = 0; i < n; i++)
    14. 	{
    15. 		push_back(val);
    16. 	}
    17. }

    写一个测试函数，用一个Print函数实现打印整个容器元素，之后打印就用这个Print函数。

    1. template <class T>
    2. void Print(const vector& v)
    3. {
    4. 	for (auto e : v)
    5. 	{
    6. 		cout << e << " ";
    7. 	}
    8. 	cout << endl;
    9. }
    10.  
    11. void test_vector3()
    12. {
    13. 	vector<int> v1(4, 10);
    14. 	Print(v1);
    15.  
    16. }

    • vector构造函数还有，给定一个容器迭代器区间进行初始化，也是跟上面的类似，复用push-back函数。不过需要再使用一个函数模版，定义first和last变量，用while循环，类似我们使用迭代遍历容器一样，其他的容器都会对!=，*和++进行重载。
    1. template<class InputIterator>
    2. vector(InputIterator first, InputIterator last)
    3. {
    4. 	while (first != last)
    5. 	{
    6. 		push_back(*first);
    7. 		++first;
    8. 	}
    9. }

    写一个测试函数。

    1. void test_vector4()
    2. {
    3. 	vector<int> v1(4, 10);
    4. 	Print(v1);
    5.  
    6. 	vector<int> v2(v1.begin(), v1.end());
    7. 	Print(v2);
    8. }

    我们来看看这段代码，在STL的Vector可以支持带花括号的初始化。

    1. void test_vector5()
    2. {
    3. 	std::vector<int> v1 = { 1,2,3,4,5,6 };
    4. 	for (auto e : v1)
    5. 	{
    6. 		cout << e << " ";
    7. 	}
    8. 	cout << endl;
    9. }

    结果如下：

    这是为什么呢？因为C++有一个类型叫做initializer_list，如下面的代码实例，任何一个带花括号的里面是相同元素，用逗号分隔，就会是该类型。这个类型里面只有两个指针维护，一个指向第一个元素，另外一个指向最后一个元素。

    1. void Test()
    2. {
    3. 	auto il = { 1,2,3,4,5,6 };
    4. 	initializer_list<int> il1 = { 1,2,3,4,5,6 };
    5.  
    6. 	cout << typeid(il).name() << endl;
    7. 	cout << sizeof(il) << endl;
    8. }

    这个构造函数跟之前也是类似，只是传递的参数是initializer_list，直接用范围for尾插。

    1. vector(initializer_list il)
    2. {
    3. 	reserve(il.size());
    4. 	for (auto e : il)
    5. 	{
    6. 		push_back(e);
    7. 	}
    8. }

    •  最后别忘了实现默认构造函数,可以使用关键字default，强制生成默认构造函数，还有可以给成员变量一个缺省值。
    1. class vector
    2. {
    3.     public:
    4.         vector() = default;
    5.  
    6. 	private:
    7. 		iterator _start = nullptr;
    8. 		iterator _finish = nullptr;
    9. 		iterator _end_of_storage = nullptr;
    10. }

    • 析构函数，先判断_start是否不为空，然后再释放空间，成员变量赋值为空指针。
    1. ~vector()
    2. {
    3. 	if (_start)
    4. 	{
    5. 		delete[] _start;
    6. 		_start = _finish = _end_of_storage = nullptr;
    7. 	}
    8. }

    3.6 拷贝构造函数和赋值拷贝函数

    拷贝构造函数，跟之前的构造函数类似，先扩容，再复用push_back函数。

    1. vector(const vector& v)
    2. {
    3. 	reserve(v.capacity());
    4. 	for (auto e : v)
    5. 	{
    6. 		push_back(e);
    7. 	}
    8. }

    • 赋值拷贝函数，可以借鉴上面写reserve的现代写法，可以实现一个swap函数，专门交换vector类型的变量，里面套用标准库里的swap函数，直接交换成员变量，不需要再开辟新空间并拷贝数据。
    • 然后赋值拷贝函数参数写成一个普通vector类型的变量，传递参数过来就会调用vector的拷贝构造函数，然后再用我们刚实现swap，进行交换，不会涉及浅拷贝的问题。并且v还是个临时变量，出了作用域自动调用析构函数，并销毁变量。
    1. void swap(vector& v)
    2. {
    3. 	std::swap(_start, v._start);
    4. 	std::swap(_finish, v._finish);
    5. 	std::swap(_end_of_storage, v._end_of_storage);
    6. }
    7.  
    8. vector& operator=(vector v)
    9. {
    10. 	swap(v);
    11. 	return *this;
    12. }

    3.7 insert和erase

    • insert和erase函数实现跟顺序表类似，都需要移动数据。
    • insert中，当容量不足要扩容时，需要先记录pos相对于_start差多少个元素个数，因为扩容之后，原有空间被释放，pos指向的就是一块被释放的空间，变成野指针。
    1. void insert(iterator pos, const T& x)
    2. {
    3. 	assert(pos >= _start);
    4. 	assert(pos <= _finish);
    5. 	if (_finish == _end_of_storage)
    6. 	{
    7. 		size_t len = pos - _start;//记录pos相对于start的位置
    8. 		size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;
    9. 		reserve(newcapacity);
    10. 		pos = _start + len;
    11. 	}
    12.  
    13. 	iterator end = _finish;
    14. 	while (end > pos)
    15. 	{
    16. 		*end = *(end - 1);
    17. 		--end;
    18. 	}
    19. 	*pos = x;
    20. 	++_finish;
    21. }
    22.  
    23. void erase(iterator pos)
    24. {
    25. 	assert(pos >= _start && pos < _finish);
    26.  
    27. 	iterator end = pos + 1;
    28. 	while (end < _finish)
    29. 	{
    30. 		*(end - 1) = *end;
    31. 		++end;
    32. 	}
    33. 	--_finish;
    34. }

    3.8 迭代器失效问题

    1. void test_vector2()
    2. {
    3. 	vector<int> v1;
    4. 	v1.push_back(1);
    5. 	v1.push_back(2);
    6. 	v1.push_back(3);
    7. 	v1.push_back(4);
    8.  
    9. 	int x;
    10. 	cin >> x;
    11. 	std::vector<int>::iterator pos = find(v1.begin(), v1.end(), x);
    12. 	if (pos != v1.end())
    13. 	{
    14. 		v1.insert(pos, 1000);
    15. 	}
    16.  
    17. 	for (auto& e : v1)
    18. 	{
    19. 		cout << e << " ";
    20. 	}
    21. 	cout << endl;
    22. }
    • 我们运行下面的代码，会发现程序崩溃了，这是为什么呢？
    • 这是因为当再插入一个元素的话，会发生扩容。扩容时，我们insert扩容时注意到pos指向一块被释放的空间，更新了pos。但是在insert函数中，会创建一个形参pos，形参是实参的一份临时拷贝，改变形参不会对外部的pos实参有影响，因此pos迭代器失效。
    • 解决的办法就是，让insert函数的返回类型为iterator，像下面一样更新pos的值。
    1.     //...
    2. 	if (pos != v1.end())
    3. 	{
    4. 		pos = v1.insert(pos, 1000);
    5. 	}
    6.     //...

     所以insert的函数返回参数需要修改，返回第一个新插入的元素。

    1. iterator insert(iterator pos, const T& x)
    2. {
    3. 	assert(pos >= _start);
    4. 	assert(pos <= _finish);
    5. 	if (_finish == _end_of_storage)
    6. 	{
    7. 		size_t len = pos - _start;//记录pos相对于start的位置
    8. 		size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;
    9. 		reserve(newcapacity);
    10. 		pos = _start + len;
    11. 	}
    12.  
    13. 	iterator end = _finish;
    14. 	while (end > pos)
    15. 	{
    16. 		*end = *(end - 1);
    17. 		--end;
    18. 	}
    19. 	*pos = x;
    20. 	++_finish;
    21. }

    再看一下下面的代码，与insert类似，我们删除一个元素，会造成迭代器失效吗？

    • pos指向的位置不变，但是某些平台会缩容，或者造成野指针现象，所以一般认为是erase迭代器失效的，erase后会返回被删除元素的后一位。
    1. void test_vector3()
    2. {
    3. 	std::vector<int> v1;
    4. 	v1.push_back(1);
    5. 	v1.push_back(2);
    6. 	v1.push_back(3);
    7. 	v1.push_back(4);
    8. 	for (auto& e : v1)
    9. 	{
    10. 		cout << e << " ";
    11. 	}
    12. 	cout << endl;
    13.  
    14.  
    15. 	int x;
    16. 	cin >> x;
    17. 	std::vector<int>::iterator pos = find(v1.begin(), v1.end(), x);
    18. 	if (pos != v1.end())
    19. 	{
    20. 		v1.erase(pos);
    21. 		cout << *pos << endl;
    22. 	}
    23.  
    24. 	for (auto& e : v1)
    25. 	{
    26. 		cout << e << " ";
    27. 	}
    28. 	cout << endl;
    29. }

    erase函数也需要修改一下，返回删除元素的后一个位置。

    1. iterator erase(iterator pos)
    2. {
    3. 	assert(pos >= _start && pos < _finish);
    4.  
    5. 	iterator end = pos + 1;
    6. 	while (end < _finish)
    7. 	{
    8. 		*(end - 1) = *end;
    9. 		++end;
    10. 	}
    11. 	--_finish;
    12.  
    13.     return pos + 1; 
    14. }

    总结

    通过这篇文章，你应该了解了vector的使用，和一些简单的底层模拟实现。不过纸上得来终觉浅，绝知此事要躬行，需要多加练习！

    创作不易，希望这篇文章能给你带来启发和帮助，如果喜欢这篇文章，请留下你的三连，你的支持的我最大的动力！！！

    ee192b61bd234c87be9d198fb540140e.png

  • 相关阅读:
    MapReduce序列化【用户流量使用统计】
    MySQL事务详解
    在微信公众平台 设置小程序域名白名单
    模型剪枝介绍
    Android-Firebase快速解决合规问题第4篇，解决FirebaseAnalytics库违规获取应用列表问题
    类与对象(十一)----构造器
    Nginx__基础入门篇
    外国科学家有哪些黑历史？ - 易智编译EaseEditing
    MybatisPlus主键生成策略与自动填充
    C 语言简单入门
  • 原文地址：https://blog.csdn.net/2301_79171011/article/details/139168296