哪个软件制作视频比较好_seo个人博客_黄冈网站推广_天津百度网络推广

向量（$vector$）是 $C$++ 标准模板库（$STL$）中封装的顺序容器（$SequenceContainer$），是一个能够存放任意类型的动态数组，能够增加和压缩数据。

---

前言 —— 序列式容器（sequence containers）

1. 容器的概观

一句话总结：容器，置物之所也。（存放数据 —— 数据结构）

研究数据的特定排序方式，以利于查找或排序或其他特殊目的，这一专门学科我们称为数据结构（$DataStructures$）。几乎可以说，任何特定的数据结构都是为了实现某种特定的算法。

$STL$ 容器即是将运用最广的一些数据结构实现出来：

$array$（数组）、$list$（链表）、$tree$（树）、$stack$（堆栈）、$queue$（队列）、$hashtable$（哈希表）、$set$（集合）、$map$（映射）$\cdot \cdot \cdot \cdot \cdot \cdot$ 等等。

2. 容器的分类

根据 $“$ 数据在容器中的排列 $”$ 特性，将这些数据结构分为序列式（$sequence$）和关联式（$associative$）两种：

序列式容器（$SequenceContainers$）	关联式容器（$AssociativeContainers$）
$array$【$C$++ $11$】	$RB-tree$【非公开】
$vector$	$set$
$heap$【以算法形式呈现 $(xxx\_heap)$】	$map$
$peiority\_queue$	$multiset$
$list$	$multimap$
$forward\_list$【$C$++ $11$】	$hashtable$【$C$++ $11$】
$deque$	$unordered\_set$【$C$++ $11$】
$stack$【配接器】	$unordered\_map$【$C$++ $11$】
$queue$【配接器】	$unordered\_multiset$【$C$++ $11$】
$\cdot \cdot \cdot \cdot \cdot \cdot$	$unordered\_multimap$【$C$++ $11$】

各种容器之间存在内含（$containment$）关系。例如：

1. $heap$ 内含一个 $vector$

2. $priority\_queue$ 内含一个 $heap$

3. $stack$ 和 $queue$ 都含一个 $deque$

4. $set/map/multiset/multimap$ 都内含一个 $RB-tree$

5. $unordered\_x$ 都内含一个 $hashtable$

3. 序列式容器（sequence containers）

所谓序列式容器，其中的元素都可序（$ordered$），但未必有序（$sorted$）。

$C$++ $STL$ 中主要提供了以下序列式容器：

1. $array$（定长数组）

2. $vector$（变长数组）

3. $list$（双向链表）

4. $forward\_list$（单向链表）

5. $deque$（双端队列）

6. $stack$（栈）

7. $queue$（队列）

8. $priority\_queue$（优先队列）

其中，$stack$ 和 $queue$ 由于只是将 $deque$ 改头换面而成，技术上被归类为一种配接器（$adapter$），即其改变了容器的接口，被称为容器配接器（$containeradapter$）。

$array$ 和 $forward\_list$ 都是 $C$++ $11$ 才引入的新容器。

---

一、vector 的介绍

$vector$ 其实就是顺序表。在实际应用中非常的重要且非常的好用。因此我们要熟悉其常用的接口，会使用，再到了解其底层，知其然且知其所以然。一些不常用的或者忘记的内容可以直接去查 $C$++ 官方文档：$vector$ 的文档介绍。

---

二、vector 的使用（常用接口）

下面只列举了 $vector$ 最常用的几个接口，更多详细信息可以自行查官方文档：$vector$。

可以看出 $vector$ 真正采用模板：
$$template<classT,classAlloc=allocator<T>>classvector;$$

1. 常见构造

构造 $(constructor)$ 函数声明	接口说明
$vector()$（重点）	无参构造
$vector(size\_typen,constvalue\_type\&val=value\_type())$	构造并初始化 $n$ 个 $val$
$vector(constvector\&x)$（重点）	拷贝构造
$vector(InputIteratorfirst,InputIteratorlast)$	使用迭代器进行初始化构造

void test1()
{//1.无参构造vector<int> v1;//2.带参构造vector<int> v2(10);//3.构造+初始化（10个1）vector<int> v3(10, 1);//4.迭代器构造vector<int> v4(v2.begin() + 2, v2.end() - 3);//5.拷贝构造vector<int> v5(v3);cout << "v1：";for (auto i : v1) cout << i;cout << endl << "v2：";for (auto i : v2) cout << i;cout << endl << "v3：";for (auto i : v3) cout << i;cout << endl << "v4：";for (auto i : v4) cout << i;cout << endl << "v5：";for (auto i : v5) cout << i;cout << endl;
}

2. iterator 的使用

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

void test2()
{vector<int> v;for (int i = 0; i < 10; i++) v.push_back(i);//正向迭代器vector<int>::iterator it = v.begin();cout << "iterator：        ";while (it != v.end()){cout << *it << " ";it++;}cout << endl;vector<int>::const_iterator cit = v.begin();cout << "const_iterator：  ";while (cit != v.end()){cout << *cit << " ";cit++;}cout << endl;//反向迭代器vector<int>::reverse_iterator rit = v.rbegin();cout << "reverse_iterator：";while (rit != v.rend()){cout << *rit << " ";rit++;}cout << endl;
}

3. 容量操作

容量空间	接口说明
$size$	获取数据个数
$capacity$	获取容量大小
$empty$	判断是否为空
$clear$	清空 $vector$ 的有效数据（$capacity$ 不变，$size$ 置为 $0$）
$resize$（重点）	改变 $vector$ 的 $size$
$reserve$（重点）	改变 $vector$ 的 $capacity$

void print(const vector<int>& v)
{cout << "size：" << v.size() << endl;cout << "v：";for (int i = 0; i < v.size(); i++) cout << v[i] << " ";v.empty() == true ? cout << endl << "empty true" : cout << endl << "empty false";cout << endl << endl;
}void test3()
{vector<int> v;for (int i = 0; i < 10; i++) v.push_back(i);print(v);v.resize(5);	print(v);v.resize(8, 10);print(v);v.resize(12);	print(v);v.resize(0);	print(v);
}

void test4()
{vector<int> v;int size = v.capacity();cout << "making v grow：" << endl;for (int i = 0; i < 100; i++){v.push_back(i);if (size != v.capacity()){size = v.capacity();cout << "capacity changed：" << size << endl;}}
}

$vs$ 下使用的 $STL$ 基本是按照 $1.5$ 倍方式扩容：

直接使用 $reserve$ 预留空间来避免 $/$ 减少扩容：

void test5()
{vector<int> v;//使用reserve预留空间，减少扩容v.reserve(100);int size = v.capacity();cout << "making vector grow：" << endl;for (int i = 0; i < 100; i++){v.push_back(i);if (size != v.capacity()){size = v.capacity();cout << "capacity changed：" << size << endl;}}
}

$reserve$ 既不会缩容，也不会改变大小：

void test6()
{vector<int> v(10, 1);cout << "size：    " << v.size() << endl;cout << "capacity：" << v.capacity() << endl << endl;//会增容且不改变大小v.reserve(20);cout << "size：    " << v.size() << endl;cout << "capacity：" << v.capacity() << endl << endl;//不会缩容且不改变大小v.reserve(5);cout << "size：    " << v.size() << endl;cout << "capacity：" << v.capacity() << endl << endl;
}

总结：

1. $capacity$ 的代码在 $vs$ 和 $g$++ 下分别运行会发现：$vs$ 下 $capacity$ 是按 $1.5$ 倍增长的，$g$++ 是按 $2$ 倍增长的。

注意：$vs$ 是 $PJ$ 版本 $STL$，$g$++ 是 $SGI$ 版本 $STL$（具体增长多少是根据具体的需求定义的，思维不要固化）。

2. $reserve$ 只负责开辟空间，如果确定知道需要用多少空间，$reserve$ 可以缓解 $vector$ 增容的代价缺陷问题。

3. $resize$ 在开空间的同时还会进行初始化，影响 $size$。

4. 增删查改

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

使用 $push\_back()$ 和 $pop\_back()$ 插入删除：

void test7()
{vector<int> v;//尾插v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);for (int i = 0; i < v.size(); i++) cout << v[i] << " ";cout << endl;//尾删v.pop_back();v.pop_back();for (int i = 0; i < v.size(); i++) cout << v[i] << " ";cout << endl;
}

使用 $insert()$ 和 $erase()$ 在指定位置插入删除（只能使用迭代器）：

void test8()
{//C++11新语法：使用列表方式初始化vector<int> v{ 1,2,3,4,5 };for (auto i : v) cout << i << " "; cout << endl << endl;// 在指定位置前插入值为val的元素，比如：3之前插入30,如果没有则不插入// 注意：vector没有提供find方法，如果要查找只能使用STL提供的全局find// 1.先使用find查找3所在位置vector<int>::iterator pos = find(v.begin(), v.end(), 3);// 如果没有找到会返回 v.end()if (pos != v.end()){// 2.在pos位置之前插入10v.insert(pos, 10);					}for (auto i : v) cout << i << " "; cout << endl << endl;// 在0位置（头删）删除元素v.erase(v.begin());for (auto i : v) cout << i << " "; cout << endl << endl;//删除所有元素v.erase(v.begin(), v.end());v.empty() == true ? cout << "empty true" << endl : cout << "empty false" << endl;
}

注意：$C$++ $11$ 之后支持列表初始化：vector<int> v{ 1,2,3,4,5 };，非常方便。

---

三、vector 迭代器失效问题（重点）

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

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

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

vector<int> v{ 1,2,3,4,5,6 };
for (auto i : v) cout << i << " ";
cout << endl;int x; cin >> x;
auto p = find(v.begin(), v.end(), x);
if (p != v.end())
{//insert以后pos就失效了，不要直接访问//v.insert(p, 10);//*p *= 10;//要访问就要更新这个失效迭代器的值p = v.insert(p, 10);	//insert要返回新pos*(p+1) *= 11;
}
for (auto i : v) cout << i << " ";
cout << endl;

因此，如 $insert$ 操作在标准库中的实现是返回一个迭代器指向插入位置的元素，就是为了避免迭代器失效的问题，所以以后如果要访问 $pos$ 位置元素，要更新一下再访问：pos = insert(pos,val);。

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

vector<int> v{ 1,2,3,4 };auto pos = find(v.begin(), v.end(), 3);// 删除pos位置的数据，导致pos迭代器失效。
v.erase(pos);cout << *pos << endl; // 此处会导致非法访问

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

以下代码的功能是删除 $vector$ 中所有的偶数，请问那个代码是正确的，为什么？

//要求删除所有的偶数
void test1()
{vector<int> v{ 1,2,3,4 };auto it = v.begin();while (it != v.end()){if (*it % 2 == 0)v.erase(it);++it;}for(auto i : v) cout << i << " "; cout << endl;
}

$test1$ 报错：

//要求删除所有的偶数
void test2()
{vector<int> v{ 1,2,3,4 };auto it = v.begin();while (it != v.end()){if (*it % 2 == 0)it = v.erase(it);else++it;}for(auto i : v) cout << i << " "; cout << endl;
}

$test2$ 正常运行：

因此，$erase$ 在标准库中的实现是返回一个迭代器指向删除位置的下一个元素，就是为了避免迭代器失效的问题，所以如果以后要访问 $pos$ 位置元素，要更新一下再访问：pos = erase(pos);。

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

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

程序输出：
1 2 3 4 5
扩容之前，vector的容量为: 5
扩容之后，vector的容量为: 100
0 2 3 4 5 409 1 2 3 4 5

// 2. erase删除任意位置代码后，linux下迭代器并没有失效
// 因为空间还是原来的空间，后序元素往前搬移了，it的位置还是有效的
#include <vector>
#include <algorithm>
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;
}

程序可以正常运行，并打印：
4
4 5

// 3: erase删除的迭代器如果是最后一个元素，删除之后it已经超过end
// 此时迭代器是无效的，++it导致程序崩溃
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;
}

========================================================
// 使用第一组数据时，程序可以运行
[sly@VM-0-3-centos 20220114]$ g++ testVector.cpp -std=c++11
[sly@VM-0-3-centos 20220114]$ ./a.out
1 3 5
=========================================================
// 使用第二组数据时，程序最终会崩溃
[sly@VM-0-3-centos 20220114]$ vim testVector.cpp
[sly@VM-0-3-centos 20220114]$ g++ testVector.cpp -std=c++11
[sly@VM-0-3-centos 20220114]$ ./a.out
Segmentation fault

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

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

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

虽然 $string$ 也会有迭代器失效的问题，但是我们一般使用 $string$ 都是通过下标访问，不经常用迭代器。

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

---

四、vector 的深度剖析

在 《$STL$源码剖析》 这本书中，根据 $SGISTL$ 源代码 <stl_vector.h> 分析出 $vector$ 的实现如下：

$vector$ 所采用的数据结构非常简单：线性连续空间。

它以两个迭代器 $start$ 和 $finish$ 分别指向配置得来的连续空间中目前已被使用的范围，并以迭代器 $end\_of\_storage$ 指向整块连续空间（含备用空间）的尾端：

template <class T, class Alloc = alloc>
class vector
{
public:typedef T 			value_type;typedef value_type*	iterator;
...
protected:iterator start;				//表示目前使用空间的头iterator finish;			//表示目前使用空间的尾iterator end_of_storage;	//表示目前可用空间的尾
...
};

运用 $start$，$finish$，$end\_of\_storage$ 三个迭代器，便可轻松提供首尾标识begin()+end()、大小size()、容量capacity()、空容器判断empty()、注标运算子[] ··· 等机能：

template <class T, class Alloc = alloc>
class vector
{
...
public:typedef T 			value_type;typedef value_type*	iterator;typedef value_type& reference;typedef size_t 		size_type;iterator begin() { return start; }iterator end() { return finish; }size_type size() const { return end() - begin(); }size_type capacity() const { return end_of_storage - begin(); }bool empty() const { return begin() == end(); }reference operator [] (size_type n) { return *(begin() + n); }
...
};

1. 内置类型构造函数

对于模板类型变量给缺省值的时候为了考虑类类型变量，因此缺省值会直接给默认构造函数（匿名对象），如 $resize$ 函数：void resize (size_t n, T val = T());

此时，对于类类型可以有默认构造函数，那么 $T$ 也有可能是内置类型，这个时候编译器会自动优化：

/*内置类型*/int i(1);						//构造函数
int j = int();					//默认构造->匿名对象->拷贝构造
int k = int(2);					//构造函数->匿名对象->拷贝构造
cout << i << " " << j << " " << k << endl;char ic('a');					//构造函数
char jc = char();				//默认构造->匿名对象->拷贝构造
char kc = char('b');			//构造函数->匿名对象->拷贝构造
cout << ic << " " << jc << " " << kc << endl;double id(1.1);					//构造函数
double jd = double();			//默认构造->匿名对象->拷贝构造
double kd = double(2.2);		//构造函数->匿名对象->拷贝构造
cout << id << " " << jd << " " << kd << endl;/*自定义类型*/string is("hello");				//构造函数
string js = string();			//默认构造->匿名对象->拷贝构造
string ks = string("world");	//构造函数->匿名对象->拷贝构造
cout << is << " " << js << " " << ks << endl;

可见，为了适配模板类型函数给缺省值时要调用构造函数初始化，对于内置类型，编译器自动优化（相当于给内置类型一个构造函数）。

2. 使用 memcpy 拷贝问题

当我们自己实现一个 $vector$ 的成员函数 $reserve$ 时，会用到 $memcpy$ 将原来需要扩容的空间直接拷贝给重新动态开辟的一块空间 $tmp$：

void reserve(size_t n)
{if (n > capacity()){size_t old_size = size();T* tmp = new T[n];memcpy(tmp, _start, sizeof(T) * old_size);delete[] _start;_start = tmp;_finish = tmp + old_size;_end_of_storage = tmp + n;}
}

这时就造成了这么一个问题 —— $memcpy$ 是浅拷贝，如果拷贝前的空间有指针指向其他的空间（需要深拷贝），如：$string$ 类型，在拷贝完后原来指针所指向的空间会直接释放掉，因此拷贝到的指针指向的空间就被释放掉了。

namespace bite	//bite代表自己实现的vector的reserve版本（使用memcpy拷贝）
{int main(){vector<string> v;v.push_back("1111");v.push_back("2222");v.push_back("3333");return 0;}
}

问题分析：

1. $memcpy$ 是内存的二进制格式拷贝，将一段内存空间中内容原封不动的拷贝到另外一段内存
   空间中（浅拷贝）。

2. 如果拷贝的是内置类型的元素，$memcpy$ 既高效又不会出错，但如果拷贝的是自定义类型元素，并且自定义类型元素中涉及到资源管理时（需要深拷贝），就会出错，因为 $memcpy$ 的拷贝实际是浅拷贝。

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

3. 动态二维数组理解

vector<T> 是模板类型，因此 $T$ 不仅可以是内置类型，也可以是自定义类型，如：string、vector $\cdot \cdot \cdot$ 等。当 $T$ 这个类型为 vector<T> v 的时候，vector<vector<T>> vv 就代表了 $vv$ 里面每一个元素存放的都是一个 vector<T> v（地址），即可以理解为二维数组。

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

$vv$ 中元素填充完成之后，如下图所示：

二维数组的遍历（$3$ 种方式）：

1. $operator[]$ 遍历：

vector<vector<int>> vv1(5, vector<int>(5, 1));	//匿名对象赋值
for (int i = 0; i < vv1.size(); i++)
{for (int j = 0; j < vv1[i].size(); j++){cout << vv1[i][j] << " ";//cout << vv1.operator[](i).operator[](j) << " ";}cout << endl;
}
cout << endl;

2. 迭代器遍历：

vector<vector<int>> vv2(5, vector<int>(5, 2));	//匿名对象赋值
for (auto it = vv2.begin(); it != vv2.end(); ++it)
{for (auto _it = it->begin(); _it != it->end(); ++_it){cout << *_it << " ";}cout << endl;
}
cout << endl;

3. 范围 $for$ 遍历：

vector<vector<int>> vv3(5, vector<int>(5, 3));	//匿名对象赋值
for (auto& v : vv3)
{for (auto& i : v){cout << i << " ";}cout << endl;
}
cout << endl;

运行结果如下：

---

五、vector 的模拟实现

因为 $vector$ 隶属于 $C$++ $STL$ 容器，即标准模板库。因此，由于模板不能分开写到两个文件里，所以之前对于类的声明和定义分离写到两个文件中是不可取的。从今往后，只要带模板的类，都只能写到一个文件中，但是声明和定义可以分离：声明写到类里面（类外要重新写模板参数），定义写到类外面，或者把所有东西都写到类里面（类内部默认为内联 $inline$）。

因此，总共分为两个文件：$vector.h$ 用来存放 $vector$ 的定义和实现；$test.cpp$ 用来测试。

注意：这里两个文件中的 $vector$ 都是自己定义的，为了和 $std::vector$ 作区分，我们要单独创建一个命名空间，这里我用的是 $namespaceybc$ 。

1. $vector.h$

#pragma once
#include<iostream>
#include<vector>
#include<list>
#include<string>
#include<assert.h>using namespace std;namespace ybc
{template<class T>class vector{public:typedef T* iterator;typedef const T* const_iterator;/*vector(){}*/// C++11 前置生成默认构造vector() = default;//类模板的成员函数，还可以继续是函数模板template<class InputIterator>	//任意类型的迭代器初始化vector(InputIterator first, InputIterator last){while (first != last){this->push_back(*first);++first;}}vector(int n, const T& val = T()){reserve(n);for (size_t i = 0; i < n; i++){push_back(val);}}vector(const vector<T>& v){reserve(v.size());for (auto& i : v){push_back(i);//this->push_back(i);}}void clear(){_finish = _start;}/*//传统写法vector<T>& operator = (const vector<T>& v){if (this != &v){clear();reserve(v.size());for (auto& i : v){push_back(i);//this->push_back(i);}}return *this;}*/void swap(vector<T>& v){std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_end_of_storage, v._end_of_storage);}//现代写法vector<T>& operator = (vector<T> v){swap(v);	//拷贝构造传参直接交换（编译器甚至会优化）return *this;}~vector(){if (_start != nullptr){delete[] _start;_start = _finish = _end_of_storage = 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 _end_of_storage - _start;}bool empty() const{return _start == _finish;}void reserve(size_t n){if (n > capacity()){size_t old_size = size();T* tmp = new T[n];//memcpy(tmp, _start, sizeof(T) * old_size); //浅拷贝for (size_t i = 0; i < old_size; i++){tmp[i] = _start[i];	//类类型会调用赋值重载（深拷贝）}delete[] _start;_start = tmp;_finish = tmp + old_size;_end_of_storage = tmp + n;}}//主要是用来初始化void resize(size_t n, const T& val = T())	//调用默认构造构造一个匿名对象给缺省值（不确定T的类型）{											//编译器会优化：内置类型也有构造函数的概念if (n < size()){_finish = _start + n;}else{reserve(n);while (_finish < _start + n){*_finish = val;++_finish;}}}void push_back(const T& x){//扩容if (_finish == _end_of_storage){reserve(capacity() == 0 ? 4 : capacity() * 2);}*_finish = x;++_finish;}void pop_back(){assert(!empty());--_finish;}iterator insert(iterator pos, const T& x){assert(pos >= _start && pos <= _finish);//扩容if (_finish == _end_of_storage){//迭代器失效size_t len = pos - _start;reserve(capacity() == 0 ? 4 : capacity() * 2);pos = _start + len;}iterator end = _finish;while (end > pos){*end = *(end - 1);--end;}*pos = x;++_finish;return pos;}iterator erase(iterator pos){assert(pos >= _start && pos < _finish);iterator it = pos;while (it != end() - 1){*it = *(it + 1);++it;}--_finish;return pos;}T& operator [] (size_t i){assert(i < size());return _start[i];}const T& operator [] (size_t i) const{assert(i < size());return _start[i];}private:iterator _start = nullptr;iterator _finish = nullptr;iterator _end_of_storage = nullptr;};
}

2. $test.cpp$

#include"vector.h"namespace ybc
{template<class T>void print_vector(const vector<T>& v){//规定：没有实例化的类模板里面取东西，编译器不能区分这里的const_iterator是类型还是静态成员变量//typename vector<T>::const_iterator it = v.begin()//1.迭代器遍历for (auto it = v.begin(); it != v.end(); it++){cout << *it << " ";}cout << endl;//2.范围for遍历for (const auto& i : v){cout << i << " ";}cout << endl;}void test1(){vector<int> v;//下标遍历for (int i = 0; i < 10; ++i){v.push_back(i);cout << v[i] << " ";}cout << endl;print_vector(v);cout << endl;vector<double> vd;//下标遍历for (int i = 0; i < 10; ++i){vd.push_back(i * 1.1);cout << vd[i] << " ";}cout << endl;print_vector(vd);}void test2(){std::vector<int> v{ 1,2,3,4,5,6 };for (auto i : v) cout << i << " ";cout << endl;int x; cin >> x;auto p = find(v.begin(), v.end(), x);if (p != v.end()){//insert以后pos就失效了，不要直接访问//v.insert(p, 10);//*p *= 10;//要访问就要更新这个失效迭代器的值p = v.insert(p, 10);	//insert要返回新pos*(p + 1) *= 11;}for (auto i : v) cout << i << " ";cout << endl;}void test3(){vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);for (auto i : v) cout << i << " "; cout << endl;//要求删除所有的偶数for (auto it = v.begin(); it != v.end();){if (*it % 2 == 0)it = v.erase(it);else++it;}for (auto i : v) cout << i << " "; cout << endl;}void test4(){/*内置类型*/int i(1);		//构造函数int j = int();	//默认构造->匿名对象->拷贝构造int k = int(2);	//构造函数->匿名对象->拷贝构造cout << "int：   " << i << " " << j << " " << k << endl;char ic('a');		//构造函数char jc = char();	//默认构造->匿名对象->拷贝构造char kc = char('b');//构造函数->匿名对象->拷贝构造cout << "char：  " << ic << " " << jc << " " << kc << endl;double id(1.1);			//构造函数double jd = double();	//默认构造->匿名对象->拷贝构造double kd = double(2.2);//构造函数->匿名对象->拷贝构造cout << "double：" << id << " " << jd << " " << kd << endl;/*自定义类型*/string is("hello");			//构造函数string js = string();		//默认构造->匿名对象->拷贝构造string ks = string("world");//构造函数->匿名对象->拷贝构造cout << "string：" << is << " " << js << " " << ks << endl;}void test5(){vector<int> v;v.resize(10, 2);v.reserve(20);cout << "size：    " << v.size() << endl;cout << "capacity：" << v.capacity() << endl;cout << endl;for (auto i : v) cout << i << " "; cout << endl;}template<class Containers>void print(const Containers& v){for (const auto& i : v){cout << i << " ";}cout << endl;}void test6(){//默认构造vector<int> v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);v1.push_back(5);cout << "v1："; print(v1);//拷贝构造vector<int> v2 = v1;cout << "v2："; print(v1);//赋值重载vector<int> v3;v3 = v1;cout << "v3："; print(v1);//迭代器构造vector<int> v4(v1.begin(), v1.end());cout << "v4："; print(v4);list<int> l{ 1,2,3,4 };vector<int> v5(l.begin(), l.end());cout << "v5："; print(v5);//n个val初始化vector<string> v6(10, "hi");cout << "v6："; print(v6);vector<int> v7(10, 1);	//会调用参数最匹配的构造函数：这里10和1默认为int类型cout << "v7："; print(v7);//memcpy拷贝问题vector<string> v8;v8.push_back("111111");v8.push_back("222222");v8.push_back("333333");v8.push_back("444444");v8.push_back("555555");cout << "v8："; print(v8);v8.push_back("666666");v8.push_back("777777");cout << "v8："; print(v8);}
}int main()
{//ybc::test1();//ybc::test2();//ybc::test3();//ybc::test4();//ybc::test5();ybc::test6();return 0;
}

---

总结

$vector$ 是 $STL$ 封装好的一块能够动态开辟连续空间的模板类。随着元素的加入，它的内部机制会自行扩充空间以容纳新元素。因此，$vector$ 的运用对于内存的合理利用与运用的灵活性有很大的帮助，我们再也不必因为害怕空间不足而一开始就要求使用定长数组，或者遭受自己动态开辟释放空间的麻烦，我们可以安心使用 $vector$，用多少开辟多少。