• C++ vector详解及模拟实现

    目录

    1.vector的介绍及使用

    1.1 vector的介绍

     1.2 vector的使用

    2.vector深度剖析及模拟实现

    3.迭代器失效

    4.遗留的浅拷贝问题

    5.完整代码

    1.vector的介绍及使用

    1.1 vector的介绍

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

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

     1.2 vector的使用

    vector学习时一定要学会查看文档：vector的文档介绍

    （cplusplus.com/reference/vector/vector/），vector在实际中非常的重要，在实际中我们熟悉常见的接口就可以，下面列出了哪些接口是要重点掌握的。


    1.定义

    (constructor)构造函数声明接口说明
    vector()（重点）无参构造
    vector（size_type n, const value_type& val = value_type()）构造并初始化n个val
    vector (const vector& x); （重点）拷贝构造
    vector (InputIterator first, InputIterator last);使用迭代器进行初始化构造

    代码演示：

    1. int TestVector1()
    2. {
    3.     //几个初识化的写法
    4.     vector<int> first;                                // empty vector of ints
    5.     vector<int> second(4, 100);                       // four ints with value 100
    6.     vector<int> third(second.begin(), second.end());  // iterating through second
    7.     vector<int> fourth(third);                       // a copy of third
    8.  
    9.     // 下面涉及迭代器初始化的部分，我们学习完迭代器再来看这部分
    10.     // the iterator constructor can also be used to construct from arrays:
    11.     int myints[] = { 16,2,77,29 };
    12.     vector<int> fifth(myints, myints + sizeof(myints) / sizeof(int));
    13.  
    14.     cout << "The contents of fifth are:";
    15.     for (vector<int>::iterator it = fifth.begin(); it != fifth.end(); ++it)
    16.         cout << ' ' << *it;
    17.     cout << '\n';
    18.  
    19.     return 0;
    20. }
    21.  
    22. //  vector的迭代器
    23. void PrintVector(const vector<int>& v)
    24. {
    25.     // const对象使用const迭代器进行遍历打印
    26.     vector<int>::const_iterator it = v.begin();
    27.     while (it != v.end())
    28.     {
    29.         cout << *it << " ";
    30.         ++it;
    31.     }
    32.     cout << endl;
    33. }

    2.vector iterator 的使用

    iterator的使用接口说明
    begin +
    end（重点）    		获取第一个数据位置的iterator/const_iterator， 获取最后一个数据的下一个位置
    的iterator/const_iterator
    rbegin + rend获取最后一个数据位置的reverse_iterator，获取第一个数据前一个位置的
    reverse_iterator

    代码演示：

    1. //  vector的迭代器
    2. void PrintVector(const vector<int>& v)
    3. {
    4.     // const对象使用const迭代器进行遍历打印
    5.     vector<int>::const_iterator it = v.begin();
    6.     while (it != v.end())
    7.     {
    8.         cout << *it << " ";
    9.         ++it;
    10.     }
    11.     cout << endl;
    12. }
    13.  
    14. int main()
    15. {
    16.     int myints[] = { 16,2,77,29 };
    17.     vector<int> ret(myints, myints + sizeof(myints) / sizeof(int));
    18.     PrintVector(ret);
    19.     return 0;
    20. }

    3.vector 空间增长问题

    容量空间接口说明
    size获取数据个数
    capacity获取容量大小
    empty判断是否为空
    resize（重点）改变vector的size
    reserve （重点）改变vector的capacity
    • capacity的代码在vs和g++下分别运行会发现，vs下capacity是按1.5倍增长的，g++是按2倍增长的。这个问题经常会考察，不要固化的认为，vector增容都是2倍，具体增长多少是根据具体的需求定义的。vs是PJ版本STL，g++是SGI版本STL。
    • reserve只负责开辟空间，如果确定知道需要用多少空间，reserve可以缓解vector增容的代价缺陷问题。
    • resize在开空间的同时还会进行初始化，影响size。

    代码演示：

    1. // reisze(size_t n, const T& data = T())
    2. // 将有效元素个数设置为n个，如果时增多时，增多的元素使用data进行填充
    3. // 注意：resize在增多元素个数时可能会扩容
    4. void TestVector3()
    5. {
    6.     vector<int> v;
    7.  
    8.     // set some initial content:
    9.     for (int i = 1; i < 10; i++)
    10.         v.push_back(i);
    11.  
    12.     v.resize(5);
    13.     v.resize(8, 100);
    14.     v.resize(12);
    15.  
    16.     cout << "v contains:";
    17.     for (size_t i = 0; i < v.size(); i++)
    18.         cout << ' ' << v[i];
    19.     cout << '\n';
    20. }

    往vecotr中插入元素时，如果大概已经知道要存放多少个元素

    可以通过reserve方法提前将容量设置好，避免边插入边扩容效率低

    4.vector 增删查改

    vector增删查改接口说明
    push_back（重点）尾插
    pop_back （重点）尾删
    find查找。（注意这个是算法模块实现，不是vector的成员接口）
    insert在position之前插入val
    erase删除position位置的数据
    swap交换两个vector的数据空间
    operator[] （重点）像数组一样访问

    代码演示：

    尾插和尾删：push_back/pop_back

    1. void TestVector4()
    2. {
    3.     vector<int> v;
    4.     v.push_back(1);
    5.     v.push_back(2);
    6.     v.push_back(3);
    7.     v.push_back(4);
    8.  
    9.     auto it = v.begin();
    10.     while (it != v.end())
    11.     {
    12.         cout << *it << " ";
    13.         ++it;
    14.     }
    15.     cout << endl;
    16.  
    17.     v.pop_back();
    18.     v.pop_back();
    19.  
    20.     it = v.begin();
    21.     while (it != v.end())
    22.     {
    23.         cout << *it << " ";
    24.         ++it;
    25.     }
    26.     cout << endl;
    27. }

    任意位置插入：insert和erase，以及查找find

    注意find不是vector自身提供的方法，是STL提供的算法

    1. void TestVector5()
    2. {
    3.     // 使用列表方式初始化，C++11新语法
    4.     vector<int> v{ 1, 2, 3, 4 };
    5.  
    6.     // 在指定位置前插入值为val的元素，比如：3之前插入30,如果没有则不插入
    7.     // 1. 先使用find查找3所在位置
    8.     // 注意：vector没有提供find方法，如果要查找只能使用STL提供的全局find
    9.     auto pos = find(v.begin(), v.end(), 3);
    10.     if (pos != v.end())
    11.     {
    12.         // 2. 在pos位置之前插入30
    13.         v.insert(pos, 30);
    14.     }
    15.  
    16.     vector<int>::iterator it = v.begin();
    17.     while (it != v.end())
    18.     {
    19.         cout << *it << " ";
    20.         ++it;
    21.     }
    22.     cout << endl;
    23.  
    24.     pos = find(v.begin(), v.end(), 3);
    25.     // 删除pos位置的数据
    26.     v.erase(pos);
    27.  
    28.     it = v.begin();
    29.     while (it != v.end()) {
    30.         cout << *it << " ";
    31.         ++it;
    32.     }
    33.     cout << endl;
    34. }

    operator[]+index 和 C++11中vector的新式for+auto的遍历

    vector使用这两种遍历方式是比较便捷的。

    1. void TestVector6()
    2. {
    3.     vector<int> v{ 1, 2, 3, 4 };
    4.  
    5.     // 通过[]读写第0个位置。
    6.     v[0] = 10;
    7.     cout << v[0] << endl;
    8.  
    9.     // 1. 使用for+[]小标方式遍历
    10.     for (size_t i = 0; i < v.size(); ++i)
    11.         cout << v[i] << " ";
    12.     cout << endl;
    13.  
    14.     vector<int> swapv;
    15.     swapv.swap(v);
    16.  
    17.     cout << "v data:";
    18.     for (size_t i = 0; i < v.size(); ++i)
    19.         cout << v[i] << " ";
    20.     cout << endl;
    21.  
    22.     // 2. 使用迭代器遍历
    23.     cout << "swapv data:";
    24.     auto it = swapv.begin();
    25.     while (it != swapv.end())
    26.     {
    27.         cout << *it << " ";
    28.         ++it;
    29.     }
    30.  
    31.     // 3. 使用范围for遍历
    32.     for (auto x : v)
    33.         cout << x << " ";
    34.     cout << endl;
    35. }

    5.vector 迭代器失效问题。

    迭代器的主要作用就是让算法能够不用关心底层数据结构，其底层实际就是一个指针，或者是对指针进行了封装，比如：vector的迭代器就是原生态指针T* 。因此迭代器失效，实际就是迭代器底层对应指针所指向的空间被销毁了，而使用一块已经被释放的空间，造成的后果是程序崩溃(即如果继续使用已经失效的迭代器，程序可能会崩溃)。

    对于vector可能会导致其迭代器失效的操作有：
    1. 会引起其底层空间改变的操作，都有可能是迭代器失效，比如：resize、reserve、insert、assign、push_back等。
     

    1. #include 
    2. using namespace std;
    3. #include 
    4. int main()
    5. {
    6.     vector<int> v{1, 2, 3, 4, 5, 6};
    7.     auto it = v.begin();
    8.     // 将有效元素个数增加到100个，多出的位置使用8填充，操作期间底层会扩容
    9.     // v.resize(100, 8);
    10.     // reserve的作用就是改变扩容大小但不改变有效元素个数，操作期间可能会引起底层容量改变
    11.     // v.reserve(100);
    12.     // 插入元素期间，可能会引起扩容，而导致原空间被释放
    13.     // v.insert(v.begin(), 0);
    14.     // v.push_back(8);
    15.     // 给vector重新赋值，可能会引起底层容量改变
    16.     v.assign(100, 8);
    17.     /*
    18.     出错原因：以上操作，都有可能会导致vector扩容，也就是说vector底层原理旧空间被释放掉，
    19.     而在打印时，it还使用的是释放之间的旧空间，在对it迭代器操作时，实际操作的是一块已经被释放的
    20.     空间，而引起代码运行时崩溃。
    21.     解决方式：在以上操作完成之后，如果想要继续通过迭代器操作vector中的元素，只需给it重新
    22.     赋值即可。
    23.     */
    24.     while (it != v.end())
    25.     {
    26.         cout << *it << " ";
    27.         ++it;
    28.     }
    29.     cout << endl;
    30.     return 0;
    31. }

    2. 指定位置元素的删除操作--erase
     

    1. #include 
    2. using namespace std;
    3. #include 
    4. int main()
    5. {
    6.     int a[] = { 1, 2, 3, 4 };
    7.     vector<int> v(a, a + sizeof(a) / sizeof(int));
    8.     // 使用find查找3所在位置的iterator
    9.     vector<int>::iterator pos = find(v.begin(), v.end(), 3);
    10.     // 删除pos位置的数据，导致pos迭代器失效。
    11.     v.erase(pos);
    12.     cout << *pos << endl; // 此处会导致非法访问
    13.     return 0;
    14. }

    erase删除pos位置元素后，pos位置之后的元素会往前搬移，没有导致底层空间的改变，理论上讲迭代器不应该会失效，但是：如果pos刚好是最后一个元素，删完之后pos刚好是end的位置，而end位置是没有元素的，那么pos就失效了。因此删除vector中任意位置上元素时，vs就认为该位置迭代器失效了。

    3.与vector类似，string在插入+扩容操作+erase之后，迭代器也会失效

    1. void TestString()
    2. {
    3.     string s("hello");
    4.     auto it = s.begin();
    5.     // 放开之后代码会崩溃，因为resize到20会string会进行扩容
    6.     // 扩容之后，it指向之前旧空间已经被释放了，该迭代器就失效了
    7.     // 后序打印时，再访问it指向的空间程序就会崩溃
    8.     //s.resize(20, '!');
    9.     while (it != s.end())
    10.     {
    11.         cout << *it;
    12.         ++it;
    13.     }
    14.     cout << endl;
    15.     it = s.begin();
    16.     while (it != s.end())
    17.     {
    18.         it = s.erase(it);
    19.         // 按照下面方式写，运行时程序会崩溃，因为erase(it)之后
    20.         // it位置的迭代器就失效了
    21.         // s.erase(it);
    22.         ++it;
    23.     }
    24. }

    迭代器失效解决办法：在使用前，对迭代器重新赋值即可。
     

    2.vector深度剖析及模拟实现

    下图是根据vector原码所抽象出来的存储逻辑，我们将根据此逻辑对vector进行模拟实现：

    1.初步实现vector：

    1. namespace my_vector
    2. {
    3. 	template<class T>
    4. 	class vector
    5. 	{
    6. 	public:
    7. 		typedef T* iterator;
    8. 		typedef const T* const_iterator;
    9.  
    10. 		iterator begin()
    11. 		{
    12. 			return _start;
    13. 		}
    14.  
    15. 		iterator end()
    16. 		{
    17. 			return _finish;
    18. 		}
    19.  
    20. 		const_iterator begin() const
    21. 		{
    22. 			return _start;
    23. 		}
    24.  
    25. 		const_iterator end() const
    26. 		{
    27. 			return _finish;
    28. 		}
    29. 		size_t size() const
    30. 		{
    31. 			return _finish - _start;
    32. 		}
    33.  
    34. 		size_t capacity() const
    35. 		{
    36. 			return _endofstorage - _start;
    37. 		}
    38.  
    39. 		void reserve(size_t n)
    40. 		{
    41. 			if (n > capacity())
    42. 			{
    43. 				size_t old = size();
    44. 				T* tmp = new T[n];
    45. 				if (_start)
    46. 				{
    47. 					memcpy(tmp, _start, old * sizeof(T));
    48. 					delete[] _start;
    49. 				}
    50.  
    51. 				_start = tmp;
    52. 				_finish = _start + old;
    53. 				_endofstorage = _start + n;
    54. 			}
    55. 		}
    56.  
    57. 		void push_back(const T& x)
    58. 		{
    59. 			if (_finish == _endofstorage)
    60. 			{
    61. 				size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;
    62. 				reserve(newcapacity);
    63. 			}
    64.  
    65. 			*_finish = x;
    66. 			++_finish;
    67. 		}
    68.  
    69. 	private:
    70. 		iterator _start = nullptr;
    71. 		iterator _finish = nullptr;
    72. 		iterator _endofstorage = nullptr;
    73. 	};
    74. }

    这段代码是对C++中的vector进行初步模拟实现的一部分。下面是其实现逻辑的简要描述：

    1. 在 my_vector 命名空间下定义了一个模板类 vector ，用于模拟实现类似于STL中的vector容器。
    2. 类模板 vector 中定义了 iterator 和 const_iterator 类型，分别表示迭代器和常量迭代器。
    3. 提供了 begin() 和 end() 成员函数用于返回指向vector起始位置和结束位置的迭代器。
    4. 实现了 reserve(size_t n) 函数，用于预留至少能容纳n个元素的存储空间，如果需要扩容则会重新分配更大的存储空间。
    5. 实现了 push_back(const T& x) 函数，用于在vector尾部添加元素x。如果当前存储空间不足，会调用 reserve 函数进行扩容。
    6. 私有成员包括三个指针 _start 、 _finish 和 _endofstorage ，分别表示起始位置、结束位置和存储空间结束位置。

    7.此外还有size（）和capacity（）。

    上面的内容都十分简单，但reserve的实现有需要注意的地方：

    下面是其实现逻辑的简要描述：

    1. 首先检查传入的参数n是否大于当前vector的容量（capacity）。
    2. 如果n大于当前容量，则执行以下操作：
    - 记录当前vector中的元素个数old。
    - 创建一个新的大小为n的临时数组tmp，用来存储扩容后的元素。
    - 如果vector中已经有元素（即_start不为空），则将原有元素拷贝到临时数组tmp中。
    - 释放原有的_start指针指向的数组内存。
    - 将临时数组tmp赋值给_start，表示扩容后的新数组。
    - 更新_finish指针指向新数组中原有元素的末尾位置。
    - 更新_endofstorage指针指向新数组的末尾位置，表示新的存储空间结束位置。
    3. 如果n不大于当前容量，则不执行任何操作。

    我们思考一下，这里为什么要保存之前元素个数？

    我们在实现这一步的时候：_finish = _start + old; old直接替换成size（）不就好了吗，为什么要单独保存以前的size大小呢？我们在这里实现size（）的逻辑是_finish - _start，但是_start此时被tmp更新，而finish没有，这里使用size（）得出来的值就是一个错误的值了，如下图所示：

    模拟实现初步测试：

    1. 	void test_vector1()
    2. 	{
    3. 		vector<int> v;
    4. 		v.push_back(1);
    5. 		v.push_back(2);
    6. 		v.push_back(3);
    7. 		v.push_back(4);
    8. 	
    9. 		vector<int>::iterator it = v.begin();
    10. 		while (it != v.end())
    11. 		{
    12. 			cout << *it << " ";
    13. 			++it;
    14. 		}
    15. 		cout << endl;
    16. 	}

    2.任意位置的插入

    1. 		iterator insert(iterator pos, const T& x)
    2. 		{
    3. 			assert(pos >= _start && pos <= _finish);
    4.  
    5. 			if (_finish == _endofstorage)
    6. 			{
    7. 				size_t len = pos - _start;
    8. 				reserve(capacity() == 0 ? 4 : capacity() * 2);
    9. 				pos = _start + len;
    10. 			}
    11.  
    12. 			iterator end = _finish - 1;
    13. 			while (end >= pos)
    14. 			{
    15. 				*(end + 1) = *end;
    16. 				--end;
    17. 			}
    18.  
    19. 			*pos = x;
    20.  
    21. 			++_finish;
    22.  
    23. 			return pos;
    24. 		}

    代码演示：

    1. 	void test_vector1()
    2. 	{
    3. 		vector<int> v;
    4. 		v.push_back(1);
    5. 		v.push_back(2);
    6. 		v.push_back(3);
    7. 		v.push_back(4);
    8. 		v.insert(v.begin()+1, 100);
    9. 		vector<int>::iterator it = v.begin();
    10. 		while (it != v.end())
    11. 		{
    12. 			cout << *it << " ";
    13. 			++it;
    14. 		}
    15. 		cout << endl;
    16. 	}

    任意位置的插入，我们使用迭代器的是pos，方便我们更灵活的传参。

    在这里，会计算出pos相对于_start的偏移量len，并调用reserve函数来扩容vector的容量。接着，重新计算pos的位置，确保在扩容后插入的位置仍然正确（因为此时pos仍然指向的是旧的空间，所以我们需要通过begin重新指定pos的空间）

     然后，通过将插入位置之后的元素向后移动一个位置，为新元素腾出空间。接着，将x插入到pos位置，然后将_finish指针向后移动一个位置，表示成功插入一个新元素。

    3.尾删&&任意位置删除

    1. 		void pop_back()
    2. 		{
    3. 			assert(size() > 0);
    4. 			--_finish;
    5. 		}

    代码演示：

    1. 	void test_vector1()
    2. 	{
    3. 		vector<int> v;
    4. 		v.push_back(1);
    5. 		v.push_back(2);
    6. 		v.push_back(3);
    7. 		v.push_back(4);
    8. 		v.insert(v.begin()+1, 100);
    9. 		v.pop_back();
    10. 		vector<int>::iterator it = v.begin();
    11. 		while (it != v.end())
    12. 		{
    13. 			cout << *it << " ";
    14. 			++it;
    15. 		}
    16. 		cout << endl;
    17. 	}

    任意位置的删除

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

    这段代码是一个 C++ 中的 erase 函数的实现。它的实现思路是：

    1. 首先，通过 assert 函数来确保要删除的位置 pos 在有效范围内（即在 [_start, _finish) 区间内）。
    2. 创建一个迭代器 it，指向要删除元素的下一个位置（pos + 1）。
    3. 通过 while 循环，将 it 位置的元素赋值给前一个位置，实现向前移动元素的操作，直到 it 到达末尾位置 _finish。
    4. 最后，将 vector 的结束迭代器 _finish 往前移动一个位置，表示删除了一个元素。
    5. 最后返回被删除元素的位置 pos。

    这段代码的功能是在 vector 中删除指定位置的元素，并将后续元素向前移动一个位置。

    4.默认构造，拷贝构造，赋值，迭代器区间构造，析构

    1. 	template<class T>
    2. 	class vector
    3. 	{
    4. 	public:
    5. 		typedef T* iterator;
    6. 		typedef const T* const_iterator;
    7.  
    8. 		vector()
    9. 		{}
    10.  
    11. 		/*vector(const vector& v)
    12. 		{
    13. 			_start = new T[v.capacity()];
    14. 			memcpy(_start, v._start, v.size()* sizeof(T));
    15. 			_finish = _start + v.size();
    16. 			_endofstorage = _start + v.capacity();
    17. 		}*/
    18.  
    19. 		// v2(v1)
    20. 		vector(const vector& v)
    21. 		{
    22. 			reserve(v.capacity());
    23. 			for (const auto& e : v)
    24. 			{
    25. 				push_back(e);
    26. 			}
    27. 		}
    28. 	
    29. 		void swap(vector& v)
    30. 		{
    31. 			std::swap(_start, v._start);
    32. 			std::swap(_finish, v._finish);
    33. 			std::swap(_endofstorage, v._endofstorage);
    34. 		}
    35.  
    36. 		// v1 = v3
    37. 		vector& operator=(vector v)
    38. 		{
    39. 			swap(v);
    40. 			return *this;
    41. 		}
    42.  
    43. 		template <class InputIterator>
    44. 		vector(InputIterator first, InputIterator last)
    45. 		{
    46. 			while (first != last)
    47. 			{
    48. 				push_back(*first);
    49. 				++first;
    50. 			}
    51. 		}
    52.  
    53. 		~vector()
    54. 		{
    55. 			if (_start)
    56. 			{
    57. 				delete[] _start;
    58. 				_start = _finish = _endofstorage = nullptr;
    59. 			}
    60. 		}
    61.  
    62. 	private:
    63. 		iterator _start = nullptr;
    64. 		iterator _finish = nullptr;
    65. 		iterator _endofstorage = nullptr;
    66. 	};

    默认构造，我们直接提供缺省参数。

    拷贝有两种写法，一种是最传统的，先开同样大小的空间，然后依次赋值就好了；第二种是，先提前开好同样大小的空间，然后我们复用尾插。

    赋值操作直接复用swap函数就好了，需要注意的是，这里传参不要传引用，否则就改变了所传对象的值了。

    迭代器区间构造：它接受两个输入迭代器 first 和 last ，并用这两个迭代器定义的范围内的元素来初始化vector。代码通过迭代这个范围，将每个元素依次添加到vector中，直到到达 last 指定的结尾位置。

    代码演示：

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

    迭代器区间构造用法：

    1.  
    2. 	void test_vectori()
    3. 	{
    4. 		vector<int> v1;
    5. 		v1.push_back(1);
    6. 		v1.push_back(2);
    7. 		v1.push_back(3);
    8. 		v1.push_back(4);
    9. 		v1.push_back(5);
    10.  
    11. 		vector<int> v2(v1.begin(), v1.end());
    12. 		for (auto e : v2)
    13. 		{
    14. 			cout << e << " ";
    15. 		}
    16. 		cout << endl;
    17. 	}

    5.resize的实现

    1.  
    2. 	void resize(size_t n, T val = T())
    3. 	{
    4. 		if (n > size())
    5. 		{
    6. 			reserve(n);
    7. 			while (_finish < _start + n)
    8. 			{
    9. 				*_finish = val;
    10. 				++_finish;
    11. 			}
    12. 		}
    13. 		else
    14. 		{
    15. 			_finish = _start + n;
    16. 		}
    17. 	}

    1. 检查传入的大小 n 是否大于当前的 vector 大小。
    2. 如果 n 大于当前大小，先调用 reserve 函数来确保 vector 有足够的容量可以存放 n 个元素。
    3. 然后通过 while 循环，将值 val 赋给新增的元素，直到达到 n 个元素的数量。
    4. 如果 n 小于等于当前大小，直接将 _finish 指针指向 _start + n，即改变 vector 的大小为 n。

    如果需要扩大，则填充新元素；如果需要缩小，则直接截断元素。

    3.迭代器失效

    场景一：我们在进行insert的时候，如果空间不够就会进行扩容操作，并且将旧的空间给释放掉，这里就会导致迭代器失效。在实现insert函数的时候，扩容后，我们会将pos指向新的位置这就在内部解决了迭代器失效的问题，但是在外部被传的it此时是失效的，因此在这里是要加返回值的

    场景二：我们在前面实现了erase函数，想一想我们为什么在这里要加返回值，不加会有什么后果。

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

    我们使用库里面的erase函数：

    1. 	void test_vector6()
    2. 	{
    3. 		std::vector<int> v;
    4. 		v.push_back(1);
    5. 		v.push_back(2);
    6. 		v.push_back(3);
    7. 		v.push_back(4);
    8. 		v.push_back(4);
    9. 		v.push_back(4);
    10. 		v.push_back(5);
    11. 		v.push_back(6);
    12. 		//v.push_back(7);
    13.  
    14. 		for (auto e : v)
    15. 		{
    16. 			cout << e << " ";
    17. 		}
    18. 		cout << endl;
    19.  
    20. 		// 要求删除所有的偶数
    21. 		std::vector<int>::iterator it = v.begin();
    22. 		while (it != v.end())
    23. 		{
    24. 			if (*it % 2 == 0)
    25. 			{
    26. 				v.erase(it);
    27. 			}
    28. 			else
    29. 			{
    30. 				++it;
    31. 			}
    32. 		}
    33.  
    34. 		for (auto e : v)
    35. 		{
    36. 			cout << e << " ";
    37. 		}
    38. 		cout << endl;
    39. 	}

    我们在进行删除操作的时候，我们直接删除，没有保存it的位置，这就出现了报错，这是因为没有返回值，it指向被删除元素的所有迭代器都会变得无效。然而，指向被删除元素之后元素的迭代器仍然有效。因此返回值的效果，就是让下一个位置的迭代器，返回给当前pos，让it重新有效。

    正确的写法：需要返回下一个位置的迭代器

    1. 		while (it != v.end())
    2. 		{
    3. 			if (*it % 2 == 0)
    4. 			{
    5. 				it=v.erase(it);
    6. 			}
    7. 			else
    8. 			{
    9. 				++it;
    10. 			}
    11. 		}

    4.遗留的浅拷贝问题

    我们来看这样一个示例：

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

    编译报错了，这是为什么呢？

            在这里，我们插入了五份数据，在第五次的时候发生了扩容。扩容的逻辑是将start开始指向的空间，通过memcpy拷贝给tmp，然后delete start指向的内容，但这里的类型是string，delete不仅释放了start指向的空间，同时还会调用string的析构，将str指向的串给释放掉，这导致的问题就是：tmp中string的str指向为空，造成了野指针，因此这里的拷贝是一个浅拷贝。

            因此我们的拷贝操作就不能使用memcpy来实现了，而是使用赋值操作，一个一个的进行拷贝。

    1. 		void reserve(size_t n)
    2. 		{
    3. 			if (n > capacity())
    4. 			{
    5. 				size_t old = size();
    6. 				T* tmp = new T[n];
    7. 				if (_start)
    8. 				{
    9. 					for (size_t i = 0; i < old; i++)
    10. 					{
    11. 						tmp[i] = _start[i];
    12. 					}
    13. 					delete[] _start;
    14. 				}
    15.  
    16. 				_start = tmp;
    17. 				_finish = _start + old;
    18. 				_endofstorage = _start + n;
    19. 			}
    20. 		}

    再运行上面代码就没问题了

    5.完整代码

    1. namespace my_vector
    2. {
    3. 	template<class T>
    4. 	class vector
    5. 	{
    6. 	public:
    7. 		typedef T* iterator;
    8. 		typedef const T* const_iterator;
    9.  
    10. 		vector()
    11. 		{}
    12.  
    13. 		/*vector(const vector& v)
    14. 		{
    15. 			_start = new T[v.capacity()];
    16. 			memcpy(_start, v._start, v.size()* sizeof(T));
    17. 			_finish = _start + v.size();
    18. 			_endofstorage = _start + v.capacity();
    19. 		}*/
    20.  
    21. 		// v2(v1)
    22. 		vector(const vector& v)
    23. 		{
    24. 			reserve(v.capacity());
    25. 			for (const auto& e : v)
    26. 			{
    27. 				push_back(e);
    28. 			}
    29. 		}
    30.  
    31. 		template <class InputIterator>
    32. 		vector(InputIterator first, InputIterator last)
    33. 		{
    34. 			while (first != last)
    35. 			{
    36. 				push_back(*first);
    37. 				++first;
    38. 			}
    39. 		}
    40.  
    41. 		vector(size_t n, const T& val = T())
    42. 		{
    43. 			resize(n, val);
    44. 		}
    45.  
    46. 		vector(int n, const T& val = T())
    47. 		{
    48. 			resize(n, val);
    49. 		}
    50.  
    51. 		void swap(vector& v)
    52. 		{
    53. 			std::swap(_start, v._start);
    54. 			std::swap(_finish, v._finish);
    55. 			std::swap(_endofstorage, v._endofstorage);
    56. 		}
    57.  
    58. 		vector& operator=(vector v)
    59. 		{
    60. 			swap(v);
    61. 			return *this;
    62. 		}
    63.  
    64. 		~vector()
    65. 		{
    66. 			if (_start)
    67. 			{
    68. 				delete[] _start;
    69. 				_start = _finish = _endofstorage = nullptr;
    70. 			}
    71. 		}
    72.  
    73. 		iterator begin()
    74. 		{
    75. 			return _start;
    76. 		}
    77.  
    78. 		iterator end()
    79. 		{
    80. 			return _finish;
    81. 		}
    82.  
    83. 		const_iterator begin() const
    84. 		{
    85. 			return _start;
    86. 		}
    87.  
    88. 		const_iterator end() const
    89. 		{
    90. 			return _finish;
    91. 		}
    92.  
    93. 		void reserve(size_t n)
    94. 		{
    95. 			if (n > capacity())
    96. 			{
    97. 				size_t old = size();
    98. 				T* tmp = new T[n];
    99. 				if (_start)
    100. 				{
    101. 					for (size_t i = 0; i < old; i++)
    102. 					{
    103. 						tmp[i] = _start[i];
    104. 					}
    105. 					delete[] _start;
    106. 				}
    107.  
    108. 				_start = tmp;
    109. 				_finish = _start + old;
    110. 				_endofstorage = _start + n;
    111. 			}
    112. 		}
    113.  
    114. 		void resize(size_t n, T val = T())
    115. 		{
    116. 			if (n > size())
    117. 			{
    118. 				reserve(n);
    119. 				while (_finish < _start + n)
    120. 				{
    121. 					*_finish = val;
    122. 					++_finish;
    123. 				}
    124. 			}
    125. 			else
    126. 			{
    127. 				_finish = _start + n;
    128. 			}
    129. 		}
    130.  
    131. 		void push_back(const T& x)
    132. 		{
    133. 			if (_finish == _endofstorage)
    134. 			{
    135. 				size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;
    136. 				reserve(newcapacity);
    137. 			}
    138.  
    139. 			*_finish = x;
    140. 			++_finish;
    141. 		}
    142.  
    143. 		void pop_back()
    144. 		{
    145. 			assert(size() > 0);
    146. 			--_finish;
    147. 		}
    148.  
    149. 		iterator insert(iterator pos, const T& x)
    150. 		{
    151. 			assert(pos >= _start && pos <= _finish);
    152.  
    153. 			if (_finish == _endofstorage)
    154. 			{
    155. 				size_t len = pos - _start;
    156. 				reserve(capacity() == 0 ? 4 : capacity() * 2);
    157. 				pos = _start + len;
    158. 			}
    159.  
    160. 			//memmove(pos + 1, pos, sizeof(T) * (_finish - pos));
    161. 			iterator end = _finish - 1;
    162. 			while (end >= pos)
    163. 			{
    164. 				*(end + 1) = *end;
    165. 				--end;
    166. 			}
    167.  
    168. 			*pos = x;
    169.  
    170. 			++_finish;
    171.  
    172. 			return pos;
    173. 		}
    174.  
    175. 		void erase(iterator pos)
    176. 		{
    177. 			assert(pos >= _start);
    178. 			assert(pos < _finish);
    179.  
    180. 			iterator it = pos + 1;
    181. 			while (it < _finish)
    182. 			{
    183. 				*(it - 1) = *it;
    184. 				++it;
    185. 			}
    186. 			_finish--;
    187.  
    188. 			//return pos;
    189. 		}
    190.  
    191. 		size_t size() const
    192. 		{
    193. 			return _finish - _start;
    194. 		}
    195.  
    196. 		size_t capacity() const
    197. 		{
    198. 			return _endofstorage - _start;
    199. 		}
    200.  
    201. 		T& operator[](size_t pos)
    202. 		{
    203. 			assert(pos < size());
    204.  
    205. 			return _start[pos];
    206. 		}
    207.  
    208. 		const T& operator[](size_t pos) const
    209. 		{
    210. 			assert(pos < size());
    211.  
    212. 			return _start[pos];
    213. 		}
    214.  
    215. 	private:
    216. 		iterator _start = nullptr;
    217. 		iterator _finish = nullptr;
    218. 		iterator _endofstorage = nullptr;
    219. 	};
    220.  
    221. 	
    222. }


     

  • 相关阅读:
    Java Spring Boot 目录结构介绍
    Qt | QSplitter(分离器或分隔符)、QSplitterHandle 类(分界线)
    【Git】快速入门安装及使用&git与svn的区别&常用命令
    3415: 【提高】小 X 的佛光
    MySQL面试题——MySQL常见查询
    Rust 错误处理
    JavaScript 的常量和变量
    [datawhale202211]跨模态神经搜索实践：环境配置
    反转链表（链表的逆置）
    uni-app、Vue3 + ucharts 图表 H5 无法渲染
  • 原文地址：https://blog.csdn.net/2301_76618602/article/details/136632160