C++ 学习系列 -- std::vector (未完待续)

一 std::vector 是什么？

vector 是c++ 中一种序列式容器，与前面说的 array 类似，其内存分配是连续的，但是与 array 不同的地方在于，vector 在运行时是可以动态扩容的，此外 vector 提供了许多方便的操作，比如：插入、删除、查找、排序等。

std::vector - cppreference.com

二 std::vector 的特性与常见面试问题有哪些？

1 特性

1.1 vector 底层是基于分配连续空间的数组，因此 vector的访问既可以通过容器的迭代器的方式，也可以通过数组的下标方式来访问元素

1.2 vector 可以在运行期间根据需要，进行动态的扩容，当已分配的空间被用满时，会再重新分配一块通常是原来空间两倍的内存，接下来依次将原来内存中的元素依次拷贝过来

1.3 基于底层的原理，其相关操作的时间复杂度如下：

1）访问元素的时间复杂度与数组相同，是 O(1) ；

2）在 vector末尾插入元素或者删除元素 O(1)

3) 在 vector 中间某个位置插入或者删除一个元素，O(n)

2 常见面试问题

1. vector 的扩容机制？

1.1 扩容倍数一般为 2 倍或者 1.5 倍

// main.cpp#include<vector>
#include<iostream>int main()
{std::vector<int>  vec2;for(int i=0; i<20; i++){std::cout << "size: " << vec2.size() << ", capaticy: " << vec2.capacity() << std::endl;vec2.push_back(i);}return 0;
}

其实际存储的元素个数，与开辟空间可以存放的元素个数如下：

从输出结果可以看出，每当存放的元素将分配的空间耗尽以后，vector 就会再次申请两倍于当前内存大小的空间来使用

1.2 扩容的具体过程

当存放元素个数将 vector 分配的内存空间耗尽时，当再放入新元素时，会触发如下过程

重新分配新的连续内存空间，大小一般是原来的 2 倍
将原来内存空间的元素依次拷贝到新空间中, 此过程会触发拷贝构造函数
调用存放在原内存空间中各元素的析构函数
释放掉原空间的内存

我们可以通过如下代码的结果看到这个过程

#include<iostream>
#include<vector>class AAA
{
public:AAA(int i):index(i){std::cout << "constructor AAA index: " << index << std::endl;}~AAA(){std::cout << "destructor AAA index: " << index << std::endl;}AAA(AAA& a):index(a.index){std::cout << "copy constructor AAA index: " << index << std::endl;}AAA(const AAA& a):index(a.index){std::cout << "copy constructor const AAA index: " << index << std::endl;}AAA(AAA&& a):index(a.index){std::cout << "move copy constructor AAA index: " << index << std::endl;a.index = 0;}AAA& operator=(AAA& a){this->index = a.index;std::cout << "equals AAA index: " << index << std::endl;return *this;}public:int index;
};int  main()
{std::vector<AAA> vec2;for(int i=0; i<7; i++){std::cout << "size: " << vec2.size() << ", capaticy: " << vec2.capacity() << std::endl;vec2.emplace_back(i);}return 0;
}

输出：

2.如何避免扩容导致的效率低下？

2.1 可以在使用 vector 之前，预估好元素的个数，在使用 vector 之前，将内存空间分配好，而不是在一边插入一边分配新空间与拷贝旧空间的元素

2.2 若是无法预估，可以在自定义类中实现高效的移动构造函数，然后禁用拷贝构造函数，这样vector 在扩容完毕后的拷贝元素阶段，会自动调用移动构造函数，具体如下：

（c++ 中声明移动构造函数后，会自动禁用拷贝构造函数）

#include<iostream>
#include<vector>class AAA
{
public:AAA(int i):index(i){std::cout << "constructor AAA index: " << index << std::endl;}~AAA(){std::cout << "destructor AAA index: " << index << std::endl;}AAA(AAA&& a):index(a.index){std::cout << "move copy constructor AAA index: " << index << std::endl;a.index = 0;}AAA& operator=(AAA& a){this->index = a.index;std::cout << "equals AAA index: " << index << std::endl;return *this;}public:int index;
};int  main()
{std::vector<AAA> vec2;for(int i=0; i<7; i++){std::cout << "size: " << vec2.size() << ", capaticy: " << vec2.capacity() << std::endl;vec2.emplace_back(i);}return 0;
}

输出：

3.为什么选择以1.5倍或者2倍方式进行扩容？而不是3倍4倍扩容？

面试题：C++vector的动态扩容，为何是1.5倍或者是2倍_vector扩容_森明帮大于黑虎帮的博客-CSDN博客

4.vs为什么选择1.5倍，linux为什么选择2倍？

面试题：C++vector的动态扩容，为何是1.5倍或者是2倍_vector扩容_森明帮大于黑虎帮的博客-CSDN博客

三 std::vector 的使用

1. vector 常见接口与操作

std::vector - cppreference.com

1.1 容器构造

构造函数	说明
vector();	空构造函数
template<typename T> vector( size_type count, const T& value);	构造 count 各 value 到vector 中
template< class InputIt > vector( InputIt first, InputIt last, const Allocator& alloc = Allocator() );	利用迭代器构造 vector
vector( const vector& other );	拷贝构造函数
vector( vector&& other );	移动构造函数

使用例子：

#include<vector>
#include<iostream>void printVector(std::vector<T>& vec)
{for(T& v:vec){std::cout << v << " ";}std::cout << "" << std::endl;
}void testVector()
{std::cout << "testVector --" << std::endl;// 1. 构造空 vectorstd::vector<int>  vec1;for(int i=1;i<7;i++){vec1.push_back(i);}std::cout << "------------ 1" << std::endl;printVector(vec1);// 2. 构造 count 个 value 到 vector 中std::vector<int> vec2(6, 88);std::cout << "------------ 2" << std::endl;printVector(vec2);// 3. 利用迭代器构造 vectorstd::vector<int> vec3(vec2.begin(), vec2.end());std::cout << "------------ 3" << std::endl;printVector(vec3);// 4. 拷贝构造函数std::vector<int> vec4(vec1);std::cout << "------------ 4" << std::endl;printVector(vec4);// 5. 移动构造函数std::vector<int> vec5(std::move(vec1));std::cout << "------------ 5" << std::endl;printVector(vec5);
}int main(int argc, char *argv[])
{testVector();return 0;
}

输出：

1.2 容器访问

函数	说明
at(size_type pos)	返回位置 pos 上的元素引用
operator[size_type pos]	同上
front	返回 vector 上第一个元素的引用
back	返回 vector 上最后一个元素的引用
data	返回底层存储数组的指针

示例代码：

#include<iostream>
#include<vector>void testVector2()
{std::cout << "testVector --" << std::endl;// 构造 vectorstd::vector<int>  vec1;for(int i=1;i<7;i++){vec1.push_back(i);}std::cout << "------------ 1" << std::endl;// 1. atint pos = 3;std::cout << " pos = 3, val = " << vec1.at(pos)<< std::endl;// 可以修改数据int& tmp1 = vec1.at(pos);tmp1 = 88;std::cout << " pos = 3, val = " << vec1.at(pos)<< std::endl;std::cout << "------------ 2" << std::endl;// 2. operator[]std::cout << " pos = 3, val = " << vec1[pos]<< std::endl;std::cout << "------------ 3" << std::endl;// 3. frontstd::cout << " front, val = " << vec1.front() << std::endl;std::cout << "------------ 4" << std::endl;// 4. backstd::cout << " back, val = " << vec1.back()<< std::endl;std::cout << "------------ 5" << std::endl;// 5. dataint*  tmp5 = vec1.data();for(int i=0; i<6;i++){std::cout << "i = " << i <<", val = " <<*(tmp5 + i) << std::endl;}
}int main()
{testVector2();return 0;
}

输出：

1.3 容器空间

函数	说明
empty()	vector 是否为空
size()	返回存储的元素个数
reserve(size_type new_cap)	提升vector 容量
capacity()	返回vector分配的空间可以存放的元素个数

示例如下

#include<iostream>
#include<vector>void testVector3()
{std::cout << "testVector --" << std::endl;std::vector<int> vec1;std::cout << " empty: " << vec1.empty() << ", size: " << vec1.size() << std::endl;for(int i=0; i<5; i++){std::cout << "size: " << vec1.size() << ", capaticy: " << vec1.capacity() << std::endl;vec1.emplace_back(i+1);}std::cout << " empty: " << vec1.empty() << ", size: " << vec1.size() << std::endl;vec1.reserve(8);std::cout << "size: " << vec1.size() << ", capaticy: " << vec1.capacity() << std::endl;
}int main()
{testVector3();return 0;
}

输出:

1.4 容器修改

函数	说明
clear()	清空 vector 中的所有元素
insert	在位置 pos 前插入元素 value
emplace	与insert类似，不过该函数可以只传元素类的构造参数，实现原地构造，效率上比 insert 高一些，因为缺少了拷贝函数的调用
push_back	在 vector 的最后append 新的元素，若是append前，vector 的size与capacity相等，那么就会重新分配内存
emplace_back	与 push_back 类似，区别在于该函数可以只传元素类的构造参数，实现原地构造，效率上比 push_back 高一些，因为缺少了拷贝函数的调用
pop_back	将 vector 的最后一个元素移除

示例如下：

#include<iostream>
#include<vector>void testVector4()
{std::cout << "testVector --" << std::endl;std::vector<int> vec1;for(int i=0; i<5; i++){vec1.emplace_back(i+1);}printVector(vec1);// 1. insertstd::cout << "------------ 1" << std::endl;auto iter = std::find(vec1.begin(), vec1.end(), 3);vec1.insert(iter,666);printVector(vec1);// 2. emplacestd::cout << "------------ 2" << std::endl;vec1.emplace(iter,888);printVector(vec1);// 3. push_backstd::cout << "------------ 3" << std::endl;vec1.push_back(77);printVector(vec1);// 4. emplace_backstd::cout << "------------ 4" << std::endl;vec1.emplace_back(778);printVector(vec1);// 5. pop_backstd::cout << "------------ 5" << std::endl;vec1.pop_back();printVector(vec1);// 6. clearstd::cout << "------------ 6" << std::endl;vec1.clear();std::cout << "empyt: " << vec1.empty() << std::endl;
}int main()
{testVector4();return 0;
}

输出：