【C++】STL——vector（万字详解）

男娘i 2024-04-20 06:12 0阅读 0赞

> **🎇C++学习历程：入门**
> 
> --------------------
> 
>  *  **博客主页：**[一起去看日落吗][Link 1]
>  *  **持续分享博主的C++学习历程**
>  *  **`博主的能力有限，出现错误希望大家不吝赐教`**
>  *  **分享给大家一句我很喜欢的话：** 也许你现在做的事情，暂时看不到成果，但不要忘记，树🌿成长之前也要扎根，也要在漫长的时光🌞中沉淀养分。静下来想一想，哪有这么多的天赋异禀，那些让你羡慕的优秀的人也都曾默默地翻山越岭🐾。
> 
> --------------------
> 
> ![在这里插入图片描述][eabca17da9704379a5f15832a495b4cc.jpeg_pic_center]

🎶 🎵

--------------------

## 🎶 1.vector 的介绍及使用 ##

### 🎵 1.1 vector的介绍 ###

[vector 的文档介绍][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的文档介绍][vector]，vector在实际中非常的重要，在实际中我们熟悉常见的接口就可以，下面列出了哪些接口是要重点掌握的。

#### 💨 1.2.1 vector的定义 ####

<table> 
 <thead> 
  <tr> 
   <th>(constructor)构造函数声明</th> 
   <th>接口说明</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>vector()</td> 
   <td>无参构造</td> 
  </tr> 
  <tr> 
   <td>vector(size_type n, const value_type&amp; val = value_type())</td> 
   <td>构造并初始化 n 个 val</td> 
  </tr> 
  <tr> 
   <td>vector(const vector&amp; x)</td> 
   <td>拷贝构造</td> 
  </tr> 
  <tr> 
   <td>vector(InputIterator first, InputIterator last)</td> 
   <td>使用迭代器进行初始化构造</td> 
  </tr> 
 </tbody> 
</table>

![请添加图片描述][a02e082e42964fa3ba953080fc94f792.png]

*  这里的迭代器还是一个函数模板，也就是说这里的迭代器不一定是 vector 的迭代器

--------------------

#### 💨1.2.2 vector iterator 的使用 ####

<table> 
 <thead> 
  <tr> 
   <th>接口</th> 
   <th>说明</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>begin+end</td> 
   <td>获取第一个位置的 iterator/const_iterator，获取最后一个数据的下一个位置的 iterator/const_iterator</td> 
  </tr> 
  <tr> 
   <td>rbegin+rend</td> 
   <td>获取最后一个数据位置的 reverse_iterator，获取第一个数据的前一个位置的 reverse_iterator</td> 
  </tr> 
 </tbody> 
</table>

![请添加图片描述][cd6b8a82347a49bda4bc815c6a236b43.png]  
![在这里插入图片描述][d45a7872752e4c5f897ca5b4656f3b11.png]  
![在这里插入图片描述][7a8136e1c6704344897d12cfad230b7a.png]

--------------------

#### 💨1.2.3 vector 空间增长问题 ####

<table> 
 <thead> 
  <tr> 
   <th>容量空间</th> 
   <th>接口说明</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>size</td> 
   <td>获取数据个数</td> 
  </tr> 
  <tr> 
   <td>capacity</td> 
   <td>获取容量大小</td> 
  </tr> 
  <tr> 
   <td>empty</td> 
   <td>判断是否为空</td> 
  </tr> 
  <tr> 
   <td>resize</td> 
   <td>改变 vector 的 size</td> 
  </tr> 
  <tr> 
   <td>reserve</td> 
   <td>改变 vector 放入 capacity</td> 
  </tr> 
 </tbody> 
</table>

![在这里插入图片描述][f9538c743c27459db325a6b27e33f103.png_pic_center]

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

**测试vector扩容机制：**

#include<iostream>
    #include<vector>
    using namespace std;
    
    void test_vector1()
    {
        
    	vector<int> v;   
    
    	//开空间,改变容量,如果确定知道需要多少空间,reserve可以缓解vector增容所带来的代价
    	v.reserve(10);
    	/* err,错误访问,在之前string里就说明了operator[]会去检查下标是否小于size,[]只能去对size范围内的数据使用
    	for(size_t i = 0; i < 10; ++i)
    	{
    		v[i] = i;	
    	}
    	*/
    	//ok,正确访问
    	for(size_t i = 0; i < 10; ++i)
    	{
        
    		v.push_back(i);	
    	}
    	
    	//开空间+默认初始化,resize会影响size
    	v.resize(20);	
    	//开空间+指定初始化
    	v.resize(20, 1);
    }
    int main()
    {
        
    	test_vector1();
    	return 0;
    }

--------------------

#### 💨 1.2.4 vector 增删查改 ####

<table> 
 <thead> 
  <tr> 
   <th>vector 增删查改</th> 
   <th>接口说明</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>push_back</td> 
   <td>尾插</td> 
  </tr> 
  <tr> 
   <td>pop_back</td> 
   <td>尾删</td> 
  </tr> 
  <tr> 
   <td>find</td> 
   <td>查找(注意这个是算法模块的实现，不是 vector 的成员接口)</td> 
  </tr> 
  <tr> 
   <td>insert</td> 
   <td>在 position 之前插入 val</td> 
  </tr> 
  <tr> 
   <td>erase</td> 
   <td>删除 position 位置的数据</td> 
  </tr> 
  <tr> 
   <td>swap</td> 
   <td>交换两个 vector 的数据空间</td> 
  </tr> 
  <tr> 
   <td>operator[]</td> 
   <td>像数组一样访问</td> 
  </tr> 
 </tbody> 
</table>

![请添加图片描述][e925b340436c4dbda106327fba33cd63.png]

--------------------

#### 💨1.2.5 vector 使用演示 ####

#define _CRT_SECURE_NO_WARNINGS
    
    #include <iostream>
    using namespace std;
    #include <vector>
    
    
    //    vector的构造
    
    int TestVector1()
    {
        
        // constructors used in the same order as described above:
        vector<int> first;                                // empty vector of ints
        vector<int> second(4, 100);                       // four ints with value 100
        vector<int> third(second.begin(), second.end());  // iterating through second
        vector<int> fourth(third);                       // a copy of third
    
        // 下面涉及迭代器初始化的部分，我们学习完迭代器再来看这部分
        // the iterator constructor can also be used to construct from arrays:
        int myints[] = {
         16,2,77,29 };
        vector<int> fifth(myints, myints + sizeof(myints) / sizeof(int));
    
        cout << "The contents of fifth are:";
        for (vector<int>::iterator it = fifth.begin(); it != fifth.end(); ++it)
            cout << ' ' << *it;
        cout << '\n';
    
        return 0;
    }
    
    
    
    //  vector的迭代器
    
    void PrintVector(const vector<int>& v)
    {
        
    	// const对象使用const迭代器进行遍历打印
    	vector<int>::const_iterator it = v.begin();
    	while (it != v.end())
    	{
        
    		cout << *it << " ";
    		++it;
    	}
    	cout << endl;
    }
    
    void TestVector2()
    {
        
    	// 使用push_back插入4个数据
    	vector<int> v;
    	v.push_back(1);
    	v.push_back(2);
    	v.push_back(3);
    	v.push_back(4);
    
    	// 使用迭代器进行遍历打印
    	vector<int>::iterator it = v.begin();
    	while (it != v.end())
    	{
        
    		cout << *it << " ";
    		++it;
    	}
    	cout << endl;
    
    	// 使用迭代器进行修改
    	it = v.begin();
    	while (it != v.end())
    	{
        
    		*it *= 2;
    		++it;
    	}
    
    	// 使用反向迭代器进行遍历再打印
    	// vector<int>::reverse_iterator rit = v.rbegin();
    	auto rit = v.rbegin();
    	while (rit != v.rend())
    	{
        
    		cout << *rit << " ";
    		++rit;
    	}
    	cout << endl;
    
    	PrintVector(v);
    }
    
    
    //  vector的resize 和 reserve
    
    // reisze(size_t n, const T& data = T())
    // 将有效元素个数设置为n个，如果时增多时，增多的元素使用data进行填充
    // 注意：resize在增多元素个数时可能会扩容
    void TestVector3()
    {
        
    	vector<int> v;
    
    	// set some initial content:
    	for (int i = 1; i < 10; i++)
    		v.push_back(i);
    
    	v.resize(5);
    	v.resize(8, 100);
    	v.resize(12);
    
    	cout << "v contains:";
    	for (size_t i = 0; i < v.size(); i++)
    		cout << ' ' << v[i];
    	cout << '\n';
    }
    
    // 测试vector的默认扩容机制
    // vs：按照1.5倍方式扩容
    // linux：按照2倍方式扩容
    void TestVectorExpand()
    {
        
    	size_t sz;
    	vector<int> v;
    	sz = v.capacity();
    	cout << "making v grow:\n";
    	for (int i = 0; i < 100; ++i) 
    	{
        
    		v.push_back(i);
    		if (sz != v.capacity()) 
    		{
        
    			sz = v.capacity();
    			cout << "capacity changed: " << sz << '\n';
    		}
    	}
    }
    
    // 往vecotr中插入元素时，如果大概已经知道要存放多少个元素
    // 可以通过reserve方法提前将容量设置好，避免边插入边扩容效率低
    void TestVectorExpandOP()
    {
        
    	vector<int> v;
    	size_t sz = v.capacity();
    	v.reserve(100);   // 提前将容量设置好，可以避免一遍插入一遍扩容
    	cout << "making bar grow:\n";
    	for (int i = 0; i < 100; ++i) 
    	{
        
    		v.push_back(i);
    		if (sz != v.capacity())
    		{
        
    			sz = v.capacity();
    			cout << "capacity changed: " << sz << '\n';
    		}
    	}
    }
    
    
    //  vector的增删改查
    
    // 尾插和尾删：push_back/pop_back
    void TestVector4()
    {
        
    	vector<int> v;
    	v.push_back(1);
    	v.push_back(2);
    	v.push_back(3);
    	v.push_back(4);
    
    	auto it = v.begin();
    	while (it != v.end()) 
    	{
        
    		cout << *it << " ";
    		++it;
    	}
    	cout << endl;
    
    	v.pop_back();
    	v.pop_back();
    
    	it = v.begin();
    	while (it != v.end()) 
    	{
        
    		cout << *it << " ";
    		++it;
    	}
    	cout << endl;
    }
    
    // 任意位置插入：insert和erase，以及查找find
    // 注意find不是vector自身提供的方法，是STL提供的算法
    void TestVector5()
    {
        
    	// 使用列表方式初始化，C++11新语法
    	vector<int> v{
         1, 2, 3, 4 };
    
    	// 在指定位置前插入值为val的元素，比如：3之前插入30,如果没有则不插入
    	// 1. 先使用find查找3所在位置
    	// 注意：vector没有提供find方法，如果要查找只能使用STL提供的全局find
    	auto pos = find(v.begin(), v.end(), 3);
    	if (pos != v.end())
    	{
        
    		// 2. 在pos位置之前插入30
    		v.insert(pos, 30);
    	}
    
    	vector<int>::iterator it = v.begin();
    	while (it != v.end()) 
    	{
        
    		cout << *it << " ";
    		++it;
    	}
    	cout << endl;
    
    	pos = find(v.begin(), v.end(), 3);
    	// 删除pos位置的数据
    	v.erase(pos);
    
    	it = v.begin();
    	while (it != v.end()) {
        
    		cout << *it << " ";
    		++it;
    	}
    	cout << endl;
    }
    
    // operator[]+index 和 C++11中vector的新式for+auto的遍历
    // vector使用这两种遍历方式是比较便捷的。
    void TestVector6()
    {
        
    	vector<int> v{
         1, 2, 3, 4 };
    
    	// 通过[]读写第0个位置。
    	v[0] = 10;
    	cout << v[0] << endl;
    
    	// 1. 使用for+[]小标方式遍历
    	for (size_t i = 0; i < v.size(); ++i)
    		cout << v[i] << " ";
    	cout << endl;
    
    	vector<int> swapv;
    	swapv.swap(v);
    
    	cout << "v data:";
    	for (size_t i = 0; i < v.size(); ++i)
    		cout << v[i] << " ";
    	cout << endl;
    
    	// 2. 使用迭代器遍历
    	cout << "swapv data:";
    	auto it = swapv.begin();
    	while (it != swapv.end())
    	{
        
    		cout << *it << " ";
    		++it;
    	}
    
    	// 3. 使用范围for遍历
    	for (auto x : v)
    		cout << x << " ";
    	cout << endl;
    }

--------------------

#### 💨1.2.6 vector 迭代器失效问题（重点） ####

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

对于vector可能会导致其迭代器失效的操作有：

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

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

1.  指定位置元素的删除操作–erase

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

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

1.  注意：Linux下，g++编译器对迭代器失效的检测并不是非常严格，处理也没有vs下极端。

#include <iostream>
    #include <vector>
    #include <algorithm>
    using namespace std;
    
    // 1. 扩容之后，迭代器已经失效了，程序虽然可以运行，但是运行结果已经不对了
    int main()
    {
        
    	vector<int> v{
        1,2,3,4,5};
    	for(size_t i = 0; i < v.size(); ++i)
    		cout << v[i] << " ";
    	cout << endl;
    	auto it = v.begin();
    	cout << "扩容之前，vector的容量为: " << v.capacity() << endl;
    	// 通过reserve将底层空间设置为100，目的是为了让vector的迭代器失效
    	v.reserve(100);
    	cout << "扩容之后，vector的容量为: " << v.capacity() << endl;
    	// 经过上述reserve之后，it迭代器肯定会失效，在vs下程序就直接崩溃了，但是linux下不会
    	// 虽然可能运行，但是输出的结果是不对的
    	while(it != v.end())
    	{
        
    		cout << *it << " ";
    		++it;
    	}
    	cout << endl;
    	return 0;
    }

![请添加图片描述][cad0a97129104826bb45c09bed1b5527.png]

--------------------

// 2. erase删除任意位置代码后，linux下迭代器并没有失效
    // 因为空间还是原来的空间，后序元素往前搬移了，it的位置还是有效的
    #inlcude <iostream>
    #include <vector>
    #include <algorithm>
    using namespace std;
    
    int main()
    {
        
    	vector<int> v{
        1,2,3,4,5};
    	vector<int>::iterator it = find(v.begin(), v.end(), 3);
    	v.erase(it);
    	cout << *it << endl;
    	while(it != v.end())
    	{
        
    		cout << *it << " ";
    		++it;
    	}
    	cout << endl;
    	return 0;
    }

![请添加图片描述][547cc375e5674a429b39de81beba0c3b.png]

--------------------

// 3: erase删除的迭代器如果是最后一个元素，删除之后it已经超过end
    // 此时迭代器是无效的，++it导致程序崩溃
    #inlcude <iostream>
    #include <vector>
    #include <algorithm>
    using namespace std;
    
    int main()
    {
        
    	vector<int> v{
        1,2,3,4,5};
    	// vector<int> v{1,2,3,4,5,6};
    	auto it = v.begin();
    	while(it != v.end())
    	{
        
    		if(*it % 2 == 0)
    		v.erase(it);
    		++it;
    	}
    	for(auto e : v)
    		cout << e << " ";
    	cout << endl;
    	return 0;
    }

--------------------

*  使用第一组数据时，程序可以运行

![请添加图片描述][a2f6bf01f075443582a8e4e0386fa0a6.png]

--------------------

*  使用第二组数据时，程序最终会崩溃

![在这里插入图片描述][51cf0334961043178cc554cb7cb8c24c.png_pic_center]

从上述三个例子中可以看到：SGI STL中，迭代器失效后，代码并不一定会崩溃，但是运行结果肯定不对，如果it不在begin和end范围内，肯定会崩溃的。

--------------------

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

#include <string>
    void TestString()
    {
        
    	string s("hello");
    	auto it = s.begin();
    	// 放开之后代码会崩溃，因为resize到20会string会进行扩容
    	// 扩容之后，it指向之前旧空间已经被释放了，该迭代器就失效了
    	// 后序打印时，再访问it指向的空间程序就会崩溃
    	//s.resize(20, '!');
    	while (it != s.end())
    	{
        
    		cout << *it;
    		++it;
    	}
    	cout << endl;
    	it = s.begin();
    	while (it != s.end())
    	{
        
    		it = s.erase(it);
    		// 按照下面方式写，运行时程序会崩溃，因为erase(it)之后
    		// it位置的迭代器就失效了
    		// s.erase(it);
    		++it;
    	}
    }

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

--------------------

#### 💨1.2.7 vector 在OJ中的使用 ####

链接：[只出现一次的数字][Link 2]

![请添加图片描述][69845d4aaba442b8b409c842b2cc502f.png]

*  解题思路：使用异或操作符 ^ —— 相同为 0，相异为 1
 *  代码演示：

class Solution {
        
    public:
        int singleNumber(vector<int>& nums) {
        
            int ret = 0;
            //1、operator[]
            /*for(size_t i = 0; i < nums.size(); ++i)
            {
                ret ^= nums[i];
            }*/
            //2、迭代器
            /*vector<int>::iterator it = nums.begin();
            while(it != nums.end())
            {
                ret ^= *it;
                ++it;
            }*/
            //3、范围for
            for(auto e : nums)
            {
        
                ret ^= e;
            }
            return ret;
        }
    };

--------------------

链接：[杨辉三角][Link 3]

![请添加图片描述][1791082881dd4b6cb735733d9f5e51e5.png]

*  解题思路：需要先生成一个杨辉三角，每行的第一个和最后一个是 1，其余设置为 0，如果是 0，则需要计算。这里可以发现规律：1 = 1 + (1 - 1)，这里以第一个要计算的值为例，且这里的数字代表的下标 —— 第 3 行以 1 为下标位置的值是等于第 2 行以 1 为下标的值加上第 2 行以 1 - 1 为下标的值
 *  代码演示：

class Solution {
        
    public:
        //vector<vector<int>>就是一个二维数组
        vector<vector<int>> generate(int numRows) {
        
            vector<vector<int>> vv;
            vv.resize(numRows);
            //生成
            for(size_t i = 0; i < vv.size(); ++i)
            {
        
            	//每行有多少个,并初始化为0
                vv[i].resize(i + 1, 0);
                //每一行的第一个和最后一个赋值为1
                /*vv[i].front() = 1;
                vv[i].back() = 1;*/
                vv[i][0] = 1;
                vv[i][vv[i].size() - 1] = 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] + vv[i - 1][j - 1];
                    }
                }
            }
            return vv;
        }
    };

--------------------

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

![在这里插入图片描述][c617c992ef314813bb21d184df10c17b.png]

### 🎵 2.1 std::vector的核心框架接口的模拟实现 ###

//
    //  main.cpp
    //  模拟实现vector
    //
    //  Created by 卜绎皓 on 2022/10/20.
    //
    
    #include<memory.h>
    #include<assert.h>
    #include<algorithm>
    #include<string>
    #include<iostream>
    using namespace std;
    
    #pragma once
    
    namespace byh
    {
        
        template<class T>
        class vector
        {
        
        public:
            // Vector的迭代器是一个原生指针
            typedef T* iterator;
            typedef const T* const_iterator;
            
            // 迭代器相关
            iterator begin()
            {
        
                return _start;
            }
            const_iterator begin() const
            {
        
                return _start;
            }
            iterator end()
            {
        
                return _finish;
            }
            const_iterator end() const
            {
        
                return _finish;
            }
            
            // 构造和销毁
            vector()
                : _start(nullptr)
                , _finish(nullptr)
                , _endofstorage(nullptr)
            {
        }
            //类模板的成员函数还可以再定义模板参数,这样写的好处是first/last可以是list等其它容器的迭代器,只要它解引用后的类型与T匹配
            template<class InputIterator>
            vector(InputIterator first, InputIterator last)
                : _start(nullptr)
                , _finish(nullptr)
                , _endofstorage(nullptr)
            {
        
                //reserve(?)这个构造函数里传的是一段迭代器区间,只有对象才知道你有多少个容量
                while(first != last)
                {
        
                    push_back(*first);
                    ++first;
                }
            }
            //v2(v1)
            //1、传统写法
            /*vector(const vector<T>& v)
            {
                _start = new T[v.capacity()];
                memcpy(_start, v._start, sizeof(T) * v.size());
                _finish = _start + v.size();
                _endofstorage = _start + v.capacity();
            }*/
            //2、传统写法————复用当前的一些接口,本质还是自己开空间,这里相对于现代写法更推荐第二种传统写法,因为它这里提前把空间开好了,并利用
            /*vector(const vector<T>& v)
                : _start(nullptr)
                , _finish(nullptr)
                , _endofstorage(nullptr)
            {
                reserve(v.capacity());//一次性开好空间
                for(const auto& e : v)//引用的作用是为了防止T是string等
                {
                    push_back(e);
                }
            }*/
            //3、现代写法,sring那我们是取_str来构造一个临时对象再交换,但是这里怎么取所有的数据来构造并交换呢,没有法子
            //这里有个法子：vector的构造函数里还提供了一个显示的迭代器(它可以传其它容器或原生指针做迭代器,但是原生指针必须要求指向的空间是连续的)
            //所以这里还需要构造一个函数,这里的现代写法对比上面的传统写法并没有讨到便宜()
            vector(const vector<T>& v)
                : _start(nullptr)
                , _finish(nullptr)
                , _endofstorage(nullptr)
            {
        
                //现代写法里提前开空间没有意义,因为现代写法的空间是tmp去搞的,tmp没办法自己开,因为它不知道有多少个数据,那有人说用last－first,不敢减,因为比如list是不支持减的,它不是一段连续的空间
                vector<T> tmp(v.begin(), v.end());
                swap(tmp);
            }
            void swap(vector<T>& v)
            {
        
                std::swap(_start, v._start);
                std::swap(_finish, v._finish);
                std::swap(_endofstorage, v._endofstorage);
            }
            //v1 = v4;
            //1、传统写法————不推荐(如果你能掌握现代写法,任何容器的深拷贝都推荐现代写法,尤其是赋值操作)
            /*vector<T>& operator=(const vector<T>& v)
            {
                if(this != &v)
                {
                    delete[]_start;
                    _start = _finish = _endofstorage = nullptr;
        
                    reserve(v.capacity());
                    for(const auto& e : v)
                    {
                        push_back(e);
                    }
                }
                return *this;
            }*/
            //2、现代写法,v就是去深拷贝的v4
            vector<T>& operator=(vector<T> v)
            {
        
                //v是v1想要的,所以v1和v交换
                swap(v);
                return *this;
            }
            ~vector()
            {
        
                delete[] _start;
                _start = _finish = _endofstorage = nullptr;
            }
            size_t size() const
            {
        
                return _finish - _start;
            }
            size_t capacity() const
            {
        
                return _endofstorage - _start;
            }
            T& operator[](size_t i)
            {
        
                assert(i < size());
                return _start[i];
            }
            const T& operator[](size_t i) const
            {
        
                assert(i < size());
                return _start[i];
            }
            void reserve(size_t n)
            {
        
                if(n > capacity())
                {
        
                    //备份一份
                    size_t sz = size();
                    T* tmp = new T[n];
                    if(_start)
                    {
        
                        //对于string,memcpy会引发更深层次的浅拷贝问题,具体如下说明
                        //memcpy(tmp, _start, sizeof(T) * size());
                        for(size_t i = 0; i < size(); ++i)
                        {
        
                            //如果T是string,它会调用string的operator=完成深拷贝
                            tmp[i] = _start[i];
                        }
                        delete[] _start;
                    }
                    _start = tmp;
                    _finish = _start + sz;
                    //_finish = _start + size();err,size去计算时,_finish还是旧空间的_finish,而_start却是新空间的_start了,所以_finish-_start就是一个负值,再加_start就是0
                    _endofstorage = _start + n;
                }
            }
            //如果没有给值,就用默认值,如果T是int,那就是int的匿名对象。T是string,那就是stirng的匿名对象。它会调用对应的默认构造函数————int是0,double是0.0,指针就是空指针
            //所以一般写一个类型,一定要提供一个不用参数就可以调的函数
            void resize(size_t n, const T& val = T())
            {
        
                if(n <= size())
                {
        
                    _finish = _start + n;
                }
                else
                {
        
                    if(n > capacity())
                    {
        
                        reserve(n);
                    }
                    while(_finish < _start + n)
                    {
        
                        *_finish = val;
                        ++_finish;
                    }
                }
            }
            void push_back(const T& x)
            {
        
                /*if(_finish == _endofstorage)
                {
                    size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;
                    reserve(newcapacity);
                }
                //这里不用像源码中一样使用定位new,因为使用定位new的原因是finish指向的空间没有初始化,所以使用定位new把对象构造上去。但是我们这里的对象是new出来的,所以这里直接赋值即可
                *_finish = x;
                ++_finish;*/
                insert(end(), x);
            }
            void pop_back()
            {
        
                /*
                //一般情况下--finish就行了,但是特殊情况vector为空时就不好
                //所以一般需要assert
                assert(!empty());
                --_finish;*/
                erase(--end());
            }
            iterator insert(iterator pos, const T& x)
            {
        
                //可以=_finish,因为它相当于尾插
                assert(pos >= _start && pos <= _finish);
                if(_finish == _endofstorage)
                {
        
                    size_t len = pos - _start;
                    size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;
                    //reserve里会更新那三个成员变量,insert返回新插入的那个元素的地址,所以这里的pos需要先备份一下旧空间里与_start之间的长度,然后再在新空间里重新赋值
                    reserve(newcapacity);
                    pos = _start + len;
                }
                iterator end = _finish - 1;
                while(end >= pos)
                {
        
                    *(end + 1) = *end;
                    --end;
                }
                *pos = x;
                ++_finish;
                return pos;
            }
            iterator erase(iterator pos)
            {
        
                assert(pos >= _start && pos < _finish);
                iterator it = pos + 1;
                while(it != _finish)
                {
        
                    *(it - 1) = *it;
                    ++it;
                }
                --_finish;
                return pos;
            }
        private:
            iterator _start;
            iterator _finish;
            iterator _endofstorage;
        };
    
        void print(const vector<int>& v)
        {
        
            vector<int>::const_iterator it = v.begin();
            while(it != v.end())
            {
        
                cout << *it << " ";
                ++it;
            }
            cout << endl;
            
            for(auto e : v)
            {
        
                cout << e << " ";
            }
            cout << endl;
    
            for(size_t i = 0; i < v.size(); ++i)
            {
        
                cout << v[i] << " ";
            }
            cout << endl;
        }
        void test_vector1()
        {
        
            vector<int> v;
            v.push_back(1);
            v.push_back(2);
            v.push_back(3);
            v.push_back(4);
        
            vector<int>::iterator it = v.begin();
            while(it != v.end())
            {
        
                cout << *it << " ";
                ++it;
            }
            cout << endl;
            
            for(auto e : v)
            {
        
                cout << e << " ";
            }
            cout << endl;
    
            for(size_t i = 0; i < v.size(); ++i)
            {
        
                cout << v[i] << " ";
            }
            cout << endl;
    
            print(v);
        }
        void test_vector2()
        {
        
            vector<int> v;
            v.push_back(1);
            v.push_back(2);
            v.push_back(3);
            v.push_back(4);
        
            for(auto e : v)
            {
        
                cout << e << " ";
            }
            cout << endl;
        
            v.resize(2);
            for(auto e : v)
            {
        
                cout << e << " ";
            }
            cout << endl;
            
            v.resize(4);
            for(auto e : v)
            {
        
                cout << e << " ";
            }
            cout << endl;
            
            v.resize(10, 5);
            for(auto e : v)
            {
        
                cout << e << " ";
            }
            cout << endl;
        }
        void test_vector3()
        {
        
            vector<string> v;
            
            string s("hello");
            v.push_back(s);
            
            v.push_back(string("hello"));
    
            v.push_back("hello");
            v.push_back("hello");
            v.push_back("hello");
            v.push_back("hello");
        
            for(auto e : v)
            {
        
                cout << e << " ";
            }
            cout << endl;
        }
        void test_vector4()
        {
        
            vector<int> v;
            v.push_back(1);
            v.push_back(2);
            v.push_back(3);
            v.push_back(4);
        
            vector<int>::iterator pos = find(v.begin(), v.end(), 2);
            if(pos != v.end())
            {
        
                pos = v.insert(pos, 20);
            }
            cout << *pos << endl;
            *pos = 100;
            ++pos;
            for(auto e : v)
            {
        
                cout << e << " ";
            }
            cout << endl;
        }
        void test_vector5()
        {
        
            vector<int> v;
            v.push_back(1);
            v.push_back(2);
            v.push_back(3);
            v.push_back(4);
            vector<int>::iterator pos = find(v.begin(), v.end(), 2);
            if(pos != v.end())
            {
        
                v.erase(pos);
            }
            //这段代码在VS下是会崩溃的,但是在Linux下没有崩,所以这块我们就按Linux下实现
            cout << *pos << endl;
            *pos = 100;
        }
        void test_vector6()
        {
        
            vector<int> v;
            v.push_back(1);
            v.push_back(2);
            v.push_back(3);
            v.push_back(4);
            //删除v中所有偶数
            vector<int>::iterator it = v.begin();
            while(it != v.end())
            {
        
                if(*it % 2 == 0)
                {
        
                    it = v.erase(it);
                }
                else
                {
        
                    ++it;
                }
            }
            for(auto e : v)
            {
        
                cout << e << " ";
            }
            cout << endl;
        }
        void test_vector7()
        {
        
            vector<int> v1;
            v1.push_back(1);
            v1.push_back(2);
            v1.push_back(3);
            v1.push_back(4);
        
            vector<int> v2(v1);
            for(auto e : v2)
            {
        
                cout << e << " ";
            }
            cout << endl;
    
            //为什么现代写法里的构造函数的实现还需要再定义模板,而不使用T*或iterator
            //因为如果是T*的话就写死了,你是其它容器的迭代器就不行了
            string s("abcde");
            vector<int> v3(v1.begin(), v1.end());
            vector<int> v4(s.begin(), s.end());
        
            //赋值
            v1 = v4;
            for(auto e : v1)
            {
        
                cout << e << " ";
            }
            cout << endl;
        }
    }
    
    
    
    
    int main()
    {
        
        byh::test_vector1();
        cout << "-----------------------next-----------------------" << endl;
        byh::test_vector2();
        cout << "-----------------------next-----------------------" << endl;
        byh::test_vector3();
        cout << "-----------------------next-----------------------" << endl;
        byh::test_vector4();
        cout << "-----------------------next-----------------------" << endl;
        byh::test_vector5();
        cout << "-----------------------next-----------------------" << endl;
        byh::test_vector6();
        cout << "-----------------------next-----------------------" << endl;
        byh::test_vector7();
        return 0;
    }

--------------------

### 🎵 2.2 使用memcpy拷贝问题 ###

假设模拟实现的vector中的reserve接口中，使用memcpy进行的拷贝，以下代码会发生什么问题？

vector<string> v;
    		
    v.push_back(1111);
    		
    v.push_back(2222);
    
    v.push_back(3333);
    
    return 0;

*  问题分析：

1.  memcpy是内存的二进制格式拷贝，将一段内存空间中内容原封不动的拷贝到另外一段内存空间中
2.  如果拷贝的是自定义类型的元素，memcpy既高效又不会出错，但如果拷贝的是自定义类型元素，并且自定义类型元素中涉及到资源管理时，就会出错，因为memcpy的拷贝实际是浅拷贝。

![请添加图片描述][d1fa9a5f75f14d13a4c3c649b2c875c6.png]  
![在这里插入图片描述][abbc6d4cd9544e5fb43d4440390e450e.png_pic_center]

![请添加图片描述][d3e29776d53b414ba457ce626f5a540f.png]

![请添加图片描述][432dd805f1224b24bd09de859be48bc5.png]

*  **结论：如果对象中涉及到资源管理时，千万不能使用memcpy进行对象之间的拷贝，因为memcpy是浅拷贝，否则可能会引起内存泄漏甚至程序崩溃。**

--------------------

### 🎵 2.3 动态二维数组理解 ###

//以杨辉三角的前n行为例:假设n为5
    void test5(size_t n) 
    {
        
    	//使用vector定义二维数组vv,vv中的每个元素都是vector<int>
    	vector<vector<int>> vv(n);
     
    	//将二维数组每一行中的vecotr<int>中的元素全部设置为1
    	for (size_t i = 0; i < n; ++i)
    		vv[i].resize(i + 1, 1);
    	//给杨辉三角中第一列和对角线的所有元素赋值
    	for (int i = 2; i < n; ++i)
    	{
        
    		for (int j = 1; j < i; ++j)
    		{
        
    			vv[i][j] = vv[i - 1][j] + vv[i - 1][j - 1];
    		}
    	}
    }

vector<vector> vv(n) ： 构造一个vv动态二维数组，vv中总共有n个元素，每个元素都是vector类型的，每行没有包含任何元素，如果n为5时如下所示：

![在这里插入图片描述][61c0f474fab0430eb7e141ccfef361e3.png]  
vv中元素填充完成之后，如下图所示：

![在这里插入图片描述][f9f3dd5c23094d50a1cc0cb5b384134a.png]  
使用标准库中vector构建动态二维数组时与上图实际是一致的

--------------------

[Link 1]: https://blog.csdn.net/m0_60338933?type=blog
[eabca17da9704379a5f15832a495b4cc.jpeg_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/499139490b2248ed96b4ff53b842fd39.jpeg
[vector]: https://cplusplus.com/reference/vector/vector/
[a02e082e42964fa3ba953080fc94f792.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/25c37a9e428e468b8c55d8ae8f55a551.png
[cd6b8a82347a49bda4bc815c6a236b43.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/af224981060348189d736b1380a8be18.png
[d45a7872752e4c5f897ca5b4656f3b11.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/583c6d27e6644b43bc8b6f5530cb93e5.png
[7a8136e1c6704344897d12cfad230b7a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/e71852885e144c40bb1429ffa3c93f10.png
[f9538c743c27459db325a6b27e33f103.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/4c61ed71c0b6424f9eb593e3d4e293e1.png
[e925b340436c4dbda106327fba33cd63.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/1482c22224274d2d9208b10ea705c0ee.png
[cad0a97129104826bb45c09bed1b5527.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/62cdfe5f70644381b779db5bccab1e97.png
[547cc375e5674a429b39de81beba0c3b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/7e5b2d5d705249a791871ea89cff4508.png
[a2f6bf01f075443582a8e4e0386fa0a6.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/2635ce11082740128728a25c14e14f33.png
[51cf0334961043178cc554cb7cb8c24c.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/91cbde7ffaac44b1a0a6e755016684af.png
[Link 2]: https://leetcode.cn/problems/single-number/submissions/
[69845d4aaba442b8b409c842b2cc502f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/9de91cce095a4ff8907786c6076f2c6c.png
[Link 3]: https://leetcode.cn/problems/pascals-triangle/description/
[1791082881dd4b6cb735733d9f5e51e5.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/f07b1e78021643c086f06e9453876a58.png
[c617c992ef314813bb21d184df10c17b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/019d004308324092a21f906c112b0428.png
[d1fa9a5f75f14d13a4c3c649b2c875c6.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/47b4e8a4dbce480e998c661846584052.png
[abbc6d4cd9544e5fb43d4440390e450e.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/28f2f13839df49f9bde499ae0af5a025.png
[d3e29776d53b414ba457ce626f5a540f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/fc5bc05211a84d95a7761197a71f8986.png
[432dd805f1224b24bd09de859be48bc5.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/7ce05e2358714f82bef7e44267bebba9.png
[61c0f474fab0430eb7e141ccfef361e3.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/9297f76a25a94490b02f0b0fa7faa3ea.png
[f9f3dd5c23094d50a1cc0cb5b384134a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/ab3ec6654da0427dac217676ee1fc0f4.png