---

1️⃣vector的概念

vector是C++在STL库中提供的一个模板类，是一个容器（container），通过指定类模板类型可以用来存储不同类型的数据，它有连续和动态的两个特点。

1. 连续(contiguous)：开辟一块连续的空间用于存储数据，类比数组。
2. 动态(dynamic)：根据存储需求，所开辟的空间可以动态变化

(本文暂且不讨论空间配置器allocator)

🔎特性：

1. vector与数组一样采用连续存储，意味着它也具有随机访问的特点，可以通过操作符[]加下标来访问某个位置的元素，十分高效。与数组不同的是，它的容量会根据元素个数的增加而自动改变。

2. vector内部的扩容机制也十分有讲究。vector的扩容是一个比较耗费时间的过程，不是简单的原地扩容（即在原有的空间后面追加新空间），而是重新开辟一块新的大小合适的空间，将原空间的数据转移过去，再将原空间回收的一个过程。就时间而言，这个过程的代价很高，因此vector不可能每新增一个元素就扩一次容，而是会分配一些额外的空间以适应可能的增长（这可能会导致空间浪费），因此存储空间往往比实际需要的空间要大。

（假设将上图的vector进行扩容）

3. 综上所述，vector扩容采取的策略是空间换时间。不同编译器下每次自动扩容增长的倍数有所不同，例如vs2019下扩容的倍数约为1.5，g++下扩容的倍数则为2。
4. 与其它动态序列容器相比（deque, list and forward_list），vector在访问元素的时候更加高效，在末尾添加和删除元素相对高效。对于其它不在末尾的删除和插入操作，效率更低（因为需要挪动数据）。

---

2️⃣STL中vector的使用

💭学习STL不同容器时，包括学习vector，查看官方的文档最为重要（点击查看：vector官方文档），追根溯源方能修行成道。vector在我们日常使用中十分场景，也十分重要，因此我们需要掌握vector的一些常用的接口。

2.1 vector的定义

构造函数（constructor）的声明	接口说明
vector()	无参构造
vector( size_type n, const value_type& val = value_type() )	构造并用n个val初始化（如果val没有传值，缺省调用val的默认构造函数，内置类型也有默认构造函数，如：int的默认构造将其初始化为0）
vector(InputIterator first, InputIterator last)	迭代器范围初始化构造
vector(const vector<value_type>& other)	拷贝构造

💬测试代码

// 定义一个函数模板PrintVector，方便我们观察测试用例
template <class T>
void PrintVector(const vector<T>& v)
{for (auto e : v){cout << e << " ";}cout << endl;
}void test1()
{// 1.vector<int> v1; // 类模板，注意指定类型PrintVector(v1);// 2.vector<int> v2(10, 2);PrintVector(v2);vector<int> vv2(10);PrintVector(vv2);// 3.vector<int> v3(v2.begin(), v2.end()); // v2.begin()和v2.end()是v2的迭代器，下文会提到PrintVector(v3);string s("abcde");vector<int> v4(s.begin(), s.end()); // 试试用指向不同类型元素的迭代器范围初始化PrintVector(v4);// 4.vector<int> v5(v4);PrintVector(v5);
}

⭕运行结果

---

2.2 iterator的使用

接口	使用说明
begin	获取第一个元素位置的iterator
end	获取最后一个元素下一个位置的iterator
rbegin	获取最后一个元素位置的reverse_iterator
rend	获取第一个元素前一个位置reverse_iterator

图片来源：cppreference.com

💦迭代器的各种操作与指针类似，解引用操作用操作符 *，自增自减用 ++ --，但迭代器并不一定等于指针
💦迭代器的类型有四种，iterator相当于普通迭代器，而加上了const_表示iterator指向的元素不可修改，加上reverse_表示该迭代器是反向迭代器，++和–的方向与iterator相反。

begin接口有不带const和带const两个重载，当const类型的vector对象调用begin时，传入const类型的this指针，调用的就是带const的begin。其他几个iterator接口同理。

💬 测试

---

2.3 vector的空间问题

接口	接口说明
size	返回容器中的数据个数
capacity	返回容器的容量
empty	判断容器是否为空
resize( size_type n, const value_type& val = value_type() )	改变容器的数据个数
reserve( size_type n )(重点)	改变容器的容量

🔎 关于reserve和resize

• reserve
  💭reserve可以改变容器的容量，分为两种情况：
  n > capacity：改变capacity为n，这里的改变是重新开辟一块大小为n的新空间，将数据挪到新空间并释放原空间
  n <= capacity：不做任何事

If new_cap is greater than the current capacity(), new storage is allocated, otherwise the function does nothing.（引用自cppreference.com）

• resize
  💭resize不仅仅是更改容器的数据个数，还可以往容器里填充数据。具体情况根据resize的参数n和容器的size而定。

看如下数轴：

💬测试代码

// 为了方便观察每次resize后的size和capacity变化，定义一个PrintVectorSizeCap函数模板
template <class T>
void PrintVectorSizeCap(const vector<T>& v)
{for (auto e : v){cout << e << " ";}printf("size:%d capacity:%d\n", v.size(), v.capacity());
}void test3()
{vector<int> v1(10, 1);v1.resize(4);PrintVectorSizeCap(v1);v1.resize(8);PrintVectorSizeCap(v1);v1.resize(16, 1);PrintVectorSizeCap(v1);
}

⭕运行结果

📌注意：有关capacity扩容的代码在vs和g++下分别运行会发现，vs下capacity是按1.5倍增长的，g++是按2倍增长的。这个问题经常会考察，不要固化的认为，vector增容都是2倍，具体增长多少是根据具体的需求定义的。vs是PJ版本STL，g++是SGI版本STL。

验证：

// 观察这段代码在vs和g++下的运行情况
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';}}
}

vs

g++

---

2.4 vector的增删查改

接口	接口说明
push_back	尾插
pop_back	尾删
insert	在某位置插入
erase	在某位置删除
find( iterator first, iterator last, value_type val )	查找（算法模块实现，并不是vector的成员函数）
swap	交换两个vector
[ ]	像数组一样通过下标随机访问容器数据

💭这些接口都比较简单，不再过多介绍，这里主要注意一些insert和erase

• insert有几种不同的接口，在pos位置插入一个元素、n个元素、也可以插入一段区间

// 1个val
iterator insert( const_iterator pos, const T& val );// n个val
iterator insert( const_iterator pos, size_type n, const T& val );// range
template< class InputIt >
iterator insert( const_iterator pos, InputIt first, InputIt last );

• erase

// 删除pos迭代器指向的元素
iterator erase( iterator pos );// 删除区间[first, last)
iterator erase( iterator first, iterator last );

---

2.5 迭代器失效问题

2.5.1 什么是迭代器？

💡 迭代器设计的本意就是为了给所有容器提供一种通用的访问方式，让使用者无需关注底层的数据结构。迭代器本质上就是一个指针，或是将指针封装成一个类，按照需要控制它的行为。 例如：vector的迭代器就是一个原生指针value_type*，因为vector的空间是连续的，原生指针恰好能满足其访问需求。

2.5.2 迭代器失效

💡 指针会有野指针问题，类似的，迭代器存在失效的问题。迭代器失效实际就是迭代器底层对应指针所指向的空间被销毁了，或使用一块已经被释放的空间，造成的后果是程序崩溃(即如果继续使用已经失效的迭代器，程序可能会崩溃)

造成迭代器失效的行为有以下几种：reserve、insert、erase、push_back等，下面具体分析这几种行为如何导致迭代器失效。

1. reserve

reserve导致的迭代器失效很好理解，因为reserve的扩容机制是重新开辟一块空间，所以指向原空间的迭代器就会失效。

假设容器vector有一个迭代器it

2. insert

insert主要有两种情况。第一种是需要扩容的insert，第二种是不需要扩容的insert。

• 情况一：当insert插入数据需要扩容时，很显然迭代器肯定会失效，道理和reserve相同。
• 情况二：当insert插入数据不需要扩容时，插入后迭代器依然指向原空间，按理说应该不会失效。我们通过画图分析一下。

假设我们现在有下面这样一个容器，迭代器it指向它的begin位置，it1在it后两个位置

该容器目前capacity>size，进行insert操作不会扩容。若在it位置插入元素0，如下

插入后it、it1虽然指向的内容发生变化，但是依然指向的是有效空间，那么这到底算不算失效呢？我们来看看编译器怎么说

// 实现代码模拟上图过程，分别在vs和g++下编译
void test4()
{vector<int> v;// 先开好足够的空间v.reserve(9);// 填入数据v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);v.push_back(6);// 定义迭代器it、it1vector<int>::iterator it = v.begin();vector<int>::iterator it1 = it + 2;v.insert(it, 0);// 试着访问一下迭代器指向内容cout << *it << endl;cout << *it1 << endl;
}

vs下引发异常，在vector头文件中的*运算符重载函数出现断点，解引用访问失败，说明在vs下这种做法是不允许的，认为迭代器失效了。

同样的代码在g++下运行，检查并没有那么严格，运行成功，打印出it和it1指向的新元素0和2

所以insert第二种情况在不同编译器下会产生不同结果。

3. erase
   erase不会开辟新空间，都是在原空间上删除数据，erase操作前后迭代器都指向未被释放的空间，但是和insert的第二种情况一样，在不同编译器下有不同的结果。

⭕结论
不同库版本的STL对迭代器失效问题的判别有所差异（vs是PJ版本，g++是SGI版本），因此，为了保证代码的可移植性，我们默认insert和erase函数在任何情况下都会导致迭代器失效（若有扩容则所有迭代器失效，若没有则插入、删除位置及之后的迭代器失效）。失效后就不能再对迭代器进行*、++、--等操作了
而解决这一问题的方法STL已经帮我们提供了，insert和erase的返回值是插入和删除后的第一个位置的迭代器，因此每次插入或删除后，下次使用迭代器之前，接收函数返回值更新一下迭代器即可。

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

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

---

3️⃣vector的模拟实现

🧿掌握了STL中vector的使用，我们可以尝试模拟实现一下vector。模拟失效不是为了造出更好的“轮子”，而是在摸清底层实现逻辑后，更好地使用vector，达到融会贯通的效果。

// 整体框架
template <class T>
class vector
{
public:// definitiontypedef T* iterator;typedef const T* const_iterator;typedef T* pointer;typedef T value_type;// Member functions// ...private:// 与string不同的是，vector用了三个指针来控制空间iterator start; // 指向目前使用空间的头iterator finish; // 指向目前使用空间的尾iterator end_of_storage; // 指向目前可用空间的尾
};

3.1 迭代器

// Iterators:iterator begin(){return start;}const_iterator begin() const{return start;}iterator end(){return finish;}const_iterator end() const{return finish;}

3.2 构造函数

// Constructors:// 1.无参构造vector():start(nullptr),finish(nullptr),end_of_storage(nullptr){}// 2.n个valvector(size_t n, const value_type& val = value_type()) // 缺省值用匿名对象，调用了类value_type的默认构造函数{// 开辟空间start = new value_type[n];// 导入数据for (size_t i = 0;i < n;++i){start[i] = val;}// 值处理finish = start + n;end_of_storage = finish;}// 3.copy// 拷贝构造vector(const vector<value_type>& v){// 开辟空间size_t n = v.capacity();start = new value_type[n];// 传输数据//memcpy(start, v.start, n * sizeof(value_type));//err// 这种写法是错误的，这里涉及到一个深浅拷贝的问题// 下面这种写法才是正确的for (size_t i = 0;i < v.size();++i){start[i] = v.start[i];}// 值处理finish = start + v.size();end_of_storage = start + n;}// 赋值重载vector<value_type>& operator=(const vector<value_type>& v){// 开辟空间size_t n = v.capacity();pointer newStart = new value_type[n];// 传输数据size_t len = v.size();for (size_t i = 0;i < len;++i){newStart[i] = v.start[i];}// 释放旧空间delete[] start;//值处理start = newStart;finish = newStart + len;end_of_storage = newStart + n;return *this;}

🔎memcpy的拷贝异常问题

传输数据为什么不能用memcpy?

📃先来看看memcpy函数的文档介绍

读完文档我们知道，memcpy是按内存的二进制格式拷贝的，也就是source指向的内存里面存着什么它就原封不动地拷贝到destination上。若是存储内置类型的vector，尚且能够完成传输数据的工作。如下图。

⭕但若容器中存放的是自定义类型， 且自定义类型的元素涉及内存空间管理，事情就没那么简单了。
例如，vector<vector<int>>类，vector中存放的类型是vector<int>，就会出错，因为memcpy其实是浅拷贝。如下图。

vector<int>类的成员变量是三个指针，所以vector<int>类在内存空间里存放的是三个指针。那么，vector<vector<int>>类若用memcpy来传输数据，就会直接将每个vector<int>类元素的指针传过去，传输成功后，就会出现两个指针同时指向一块空间的情况。这样一来，不仅两个容器不能独立开来进行各种操作，而且会导致析构同一块空间两次，出现错误。

💡 为了解决这个问题，我们可以采用下面这个方法来传输数据，无论是容器装的是什么类型，如果是自定义类型，只要该类型有赋值重载，就不会出现错误。

// 传输数据
for (size_t i = 0;i < v.size();++i)
{start[i] = v.start[i];
}

3.3 析构函数

// Destructor:
~vector()
{delete[] start;start = finish = end_of_storage = nullptr;
}

💭其实上面实现的构造函数都过于冗余，我们称之为传统写法。我们可以借助vector的其它成员函数的复用来优化构造函数，也就是构造函数的现代写法。那废话不多说，先把vector的其它成员函数都是实现了，再来看怎么运用它们优化构造函数。

---

3.4 有关空间的接口

// Capacity:size_t capacity() const{return end_of_storage - start;}size_t size() const{return finish - start;}bool empty() const{return finish == start;}// !!!很重要的一个!!!void reserve(size_t n){// 要注意新旧指针位置不匹配问题if (n > capacity()){// 开辟新空间pointer newStart = new value_type[n];// 传输数据size_t len = size();//memcpy(newStart, start, len * sizeof(value_type));//err// 这里同样不能用memcpy传输数据,就拿vector<vector<int>>举例// 用memcpy传输后，释放旧空间后，容器内部的vector元素指向的空间就被释放掉了// 而传到新空间上的指针自然也失效了for (size_t i = 0;i < len;++i){newStart[i] = start[i];}// 释放旧空间delete[] start;// 值处理start = newStart;finish = newStart + len; // 不能finish = newStart + size(),size()函数内部会出问题,// finish还在旧空间,而start已经在新空间了end_of_storage = newStart + n;}}void resize(size_t n, const value_type& val = value_type()){if (n > size()){reserve(n); // reserve会自动判断需不需要扩容while (finish < start + n){*(finish++) = val;}}else{finish = start + n;}}

---

3.5 增删查改

		// Modifiers:value_type& operator[](size_t pos){assert(pos < size()); // 检查pos的合法性return *(start + pos);}void push_back(const value_type& val){// 当finish == end_of_storage为满额状态，需要扩容才能插入数据if (finish == end_of_storage){size_t newCapacity = capacity() == 0 ? 4 : 2 * capacity();// 当capacity为0时，给一个初始值为4reserve(newCapacity);}// 尾插数据*finish = val;++finish;}void pop_back(){assert(!empty());--finish;}void swap(vector<value_type>& v){std::swap(start, v.start);std::swap(finish, v.finish);std::swap(end_of_storage, v.end_of_storage);}iterator insert(iterator pos, const value_type& val){assert(pos < finish && pos >= start);// check capacityif (finish == end_of_storage){size_t lentoPos = pos - start;size_t newCapacity = capacity() == 0 ? 4 : 2 * capacity();reserve(newCapacity);// 扩容会导致迭代器失效，要更新迭代器pos = start + lentoPos;}// 挪动数据iterator tmp = finish;while (tmp > pos){*tmp = *(tmp - 1);--tmp;}// 值处理*pos = val;++finish;return pos;}void insert(iterator pos, size_t n, const value_type& val){size_t lentoPos = pos - start;// check capacityif (finish + n > end_of_storage){reserve(capacity() + n);pos = start + lentoPos;}// 挪动数据iterator it = finish - 1;while (it >= pos){*(it + n) = *it;--it;}// 导入数据iterator end = pos + n;while (pos < end){*(pos++) = val;			}// 值处理finish += n;}iterator erase(iterator pos){assert(pos < size());// 挪动数据，直接覆盖预删除数据iterator tmp = pos;while (tmp < finish - 1){*tmp = *(tmp + 1);++tmp;}--finish;return pos;}iterator erase(iterator first, iterator last){iterator tmp = first;while (last < finish){*(first++) = *(last++);}finish = first;return tmp;}

🔎 A little problem:
为什么库里面已经有一个swap函数了，vector不选择直接用，而是设计一个属于自己的swap呢？

查阅文档了解到库里面swap的实现是这样的。

💡若T是vector类，这里还要调用一次拷贝构造+两次赋值重载，效率比较低。而vector自己实现的swap则是直接交换两个vector的指针，即交换两个vector指向的空间，效率很高。

---

3.6 构造函数的现代写法

        // 1.n个valvector(size_t n, const value_type& val = value_type()):start(nullptr),finish(nullptr),end_of_storage(nullptr){reserve(n);while (n--){push_back(val); // 在push_back函数中发生变化}}// 复用了reserve和push_back函数，// finish和end_of_storage两个指针都在成员函数中处理了// 代码简洁了很多。// 为了实现拷贝构造的现代写法，先实现一个迭代器范围构造函数template <class InputIterator>vector(InputIterator first, InputIterator last):start(nullptr),finish(nullptr),end_of_storage(nullptr){while (first != last){push_back(*first); // *first传入push_back会有一个隐式类型转换// *first的类型会转换成value_type++first;}}

🔎range构造和fill构造的冲突问题

问题：

⭕要特别注意一个问题。我们将迭代器范围构造函数称为range构造，n个val构造函数称为fill构造。这两个构造函数会发生意想不到的冲突，看下面代码。

void test6()
{vector<int> v(10, 'a');for (auto e : v){cout << e << " ";}cout << endl;
}

用10个字符'a'去构造一个vector<int>类对象，除了'a'存入时会发生一个小小的类型转换之外，没有任何问题。

⭕运行结果

再看这个代码

void test6()
{vector<int> v(10, 1);for (auto e : v){cout << e << " ";}cout << endl;
}

程序运行出错，并且报了非法的间接寻址这个错误。

原因：

观察fill构造和range构造的参数列表。

// fill
vector (size_type n, const value_type& val = value_type()）// range
template <class InputIterator>
vector (InputIterator first, InputIterator last)

• 当实例化对象时是：vector<int> v(10,'a')

第一个参数10的类型是int，第二个参数'a'的类型是char，构造函数中有两个参数的只有range构造和fill构造。range构造是函数模板，要求两个参数必须是同类型。显然，这里只能调用fill构造，传参时会发生隐式类型转换，int->size_t，char->value_type。

• 当实例化对象时是：vector<int> v(10,1)

第一个参数10的类型是int，第二个参数1的类型也是int，两个参数类型一样，而传入fill构造又要隐式类型转换，编译器会偷懒，调用它觉得最省事的那个构造函数，那就是range构造了。传入range构造函数模板后，本来InputIterator希望得到迭代器类型，这下传入了int类型，range构造函数内部解引用first时就会引发非法的间接寻址的错误。

解决方法：

// 效仿PJ库版STL的做法，重载两个fill构造函数即可，n的类型一个为size_t一个为intvector(int n, const value_type& val = value_type()) // 两个参数类型都为int时，调用该构造函数:start(nullptr),finish(nullptr),end_of_storage(nullptr){reserve(n);while (n--){push_back(val);}}vector(size_t n, const value_type& val = value_type()):start(nullptr),finish(nullptr),end_of_storage(nullptr){reserve(n);while (n--){push_back(val);}}

⭕ 运行通过

🧐OK，解决了这个棘手的问题，继续我们的构造函数现代写法。

        // copy// 构造函数vector(const vector<value_type>& v):start(nullptr),finish(nullptr),end_of_storage(nullptr){vector<value_type> tmp(v.begin(), v.end());swap(tmp);}

💡 构造函数的现代写法复用了range构造函数，相当于让“打工人”tmp先帮我们把v的数据和空间拷贝过来，然后再把tmp和*this一交换，*this就成功拷贝了v，而出了作用域tmp也就被销毁了，就没他什么事了（纯纯地压榨）。这样一来，代码十分简洁，复用性也很强。

有了如此简洁的拷贝构造，作为它的孪生兄弟赋值重载，不也得进化一下？

		// 赋值重载的现代写法vector<value_type>& operator=(vector<value_type> v){swap(v);return *this;}

看起来是不是十分简洁？这里其实不仅复用了swap，还复用了拷贝构造。注意到这里的参数并不是引用，所以v是调用拷贝构造实例化出来的，与外部传入的类对象相等却无关。所以我们都不需要自己创造一个“打工人”，直接有了一个现成的“打工人”！！直接让*this和v交换一下就实现了。

---

📝构造函数现代写法的整体代码

		// 1. fillvector(int n, const value_type& val = value_type()):start(nullptr),finish(nullptr),end_of_storage(nullptr){reserve(n);while (n--){push_back(val);}}vector(size_t n, const value_type& val = value_type()):start(nullptr),finish(nullptr),end_of_storage(nullptr){reserve(n);while (n--){push_back(val);}}// 2.rangetemplate <class InputIterator>vector(InputIterator first, InputIterator last):start(nullptr),finish(nullptr),end_of_storage(nullptr){while (first != last){push_back(*first); ++first;}}// 3.拷贝构造vector(const vector<value_type>& v):start(nullptr),finish(nullptr),end_of_storage(nullptr){vector<value_type> tmp(v.begin(), v.end());swap(tmp);}// 4."="vector<value_type>& operator=(vector<value_type> v){swap(v);return *this;}

ending：
如果本文对你有帮助的话，不妨点赞关注收藏支持一下博主呀🍻