vector
介绍
vector（向量）是一种序列容器，表示为可以改变大小的数组。vector中的元素使用连续的存储位置，这意味着也可以使用指向其元素的常规指针+偏移量来访问任意元素，且与数组一样高效。但与数组不同的是，vector的大小可以动态变化，容器会自动处理他们的存储空间。在其内部，vector使用动态分配的数组来存储他们的元素。当插入新元素需要增大容量时，存储空间需要重新分配，这意味着需要分配一个新数组并将所有元素移动到其中。就处理时间而言，这是一个相对昂贵的任务，因此vector不会在每次想容器中添加元素时都重新分配。相反，vector容器可以分配一些额外的存储空间，以适应可能的增长，因此容器的实际容量肯呢个大于包含其元素严格所需的存储空间。因此与数组相比，向量消耗更多的内存，以换取更有效的方式管理存储和动态增长的能力。与其他动态序列容器（deque、列表、前向列表）相比，vector可以非常高效地访问其元素，并且可以相对高效地从其末端添加或删除元素。对于涉及在末尾以外的位置插入或删除元素的操作，他们的性能比其他操作差，并且迭代器引用的一致性不如列表和前向列表。
以上是官方对于vector的介绍，从上面我们能够了解到vector本质上就是一种可动态增长的顺序表，其特性与数据结构中学习的顺序表相差无几，但vector的出现极大地简化了我们使用顺序表的工作量，且vector与其他容器有着较深的联系，因此学好vector有利于我们未来的学习。
vector的使用
对于vector，在学习时我们一定要学会查看文档：vector文档，vector在实际中非常重要，我们要熟悉常见的接口，以应对未来的使用。
(constructor)构造函数
| 函数声明 | 接口说明 |
|---|---|
| vector(); | 无参构造 |
| vector(size_t n, const T& val = T()); | 构造并初始化n个val |
| vector(const vector& x); | 拷贝构造 |
| vector(inputiterator first, inputiterator last); | 使用迭代器进行区间初始化构造 |
代码演示：
//构造5个int的空间
vector<int> v1(5);
//构造10个int空间，并初始化为1
vector<int> v2(10, 1);
//去掉v2的第一个和最后一个空间，使用剩余空间构造并用相同数值初始化
vector<int> v3(++v2.begin(), --v2.end());
//拷贝构造
vector<int> v4 = v3;iterator迭代器的使用
| 函数名称 | 接口说明 |
|---|---|
| begin+end | 获取第一个数据位置的iterator/const_iterator，获取最后一个数据的下一个位置的iterator/const_iterator. |
| rbegin+rend | 获取最后一个数据位置的reverse_iterator，获取第一个数据前一个位置的reverse_iterator |
代码演示：
vector<int> v(10, 1);
// []下标形式
for (size_t i = 0; i < v.size(); i++)
{
cout << v[i] << " ";
}
cout << endl;
//迭代器
vector<int>::iterator it = v.begin();
while (it != v.end())
{
cout << *it << " ";
it++;
}
cout << endl;
//反向迭代器
vector<int>::reverse_iterator rit = v.rbegin();
while(rit != v.rend())
{
cout << *rit << " ";
rit++;
}
cout << endl;
//范围for
for (auto& e : v)
{
cout << e << " ";
}
cout << endl;空间管理函数
| 函数名称 | 接口说明 |
|---|---|
| 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就可以一次性开好，缓解了多次扩容的代价。
- resize在开空间的同时还会进行初始化，影响_size。
扩容机制测试代码：
// 测试vector的默认扩容机制
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';
}
}
}内存管理函数代码演示：
//reserve
vector<int> v(10, 1);
cout << "size:" << v.size() << " " << "capacity:" << v.capacity() << endl;
v.reserve(20);
cout << "size:" << v.size() << " " << "capacity:" << v.capacity() << endl;
v.reserve(15);
cout << "size:" << v.size() << " " << "capacity:" << v.capacity() << endl;
v.reserve(5);
cout << "size:" << v.size() << " " << "capacity:" << v.capacity() << endl;
//resize
vector<int> v(10, 1);
cout <<"size:" << v.size() << " " << "capacity:" << v.capacity() << endl;
for (auto& e : v)
{
cout << e << " ";
}
cout << endl;
v.resize(15,2);
cout << "size:" << v.size() << " " << "capacity:" << v.capacity() << endl;
for (auto& e : v)
{
cout << e << " ";
}
cout << endl;
v.resize(25, 3);
cout << "size:" << v.size() << " " << "capacity:" << v.capacity() << endl;
for (auto& e : v)
{
cout << e << " ";
}
cout << endl;
v.resize(5);
cout << "size:" << v.size() << " " << "capacity:" << v.capacity() << endl;
for (auto& e : v)
{
cout << e << " ";
}
cout << endl;增删查改
| 函数名称 | 接口说明 |
|---|---|
| push_back | 尾插 |
| pop_back | 尾删 |
| find | 查找（不是vector的成员接口） |
| insert | 在pos之前插入val |
| erase | 删除pos位置的数据 |
| swap | 交换两个vector对象的数据空间 |
| operator[] | 像数组一样访问 |
代码演示：
vector<int> v(5, 1);
for (auto& e : v)
{
cout << e << " ";
}
cout << endl;
//尾删
v.pop_back();
for (auto& e : v)
{
cout << e << " ";
}
cout << endl;
//尾插
v.push_back(5);
for (auto& e : v)
{
cout << e << " ";
}
cout << endl;
//pos位置之前插入
v.insert(v.begin(), 4);
for (auto& e : v)
{
cout << e << " ";
}
cout << endl;
//寻找第一个为1数据的位置
vector<int>::iterator pos = find(v.begin(),v.end(),1);
//删除pos位置的数据
v.erase(pos);
for (auto& e : v)
{
cout << e << " ";
}
cout << endl;
// operator[]的调用
v[2] = 9;
for (auto& e : v)
{
cout << e << " ";
}
cout << endl;
//swap交换函数
vector<int> v1(5, 2);
swap(v, v1);
for (auto& e : v)
{
cout << e << " ";
}
cout << endl;vector<vector<int>>
vector<vector<int>>是C++中的动态二维数组结构，是一个vector的集合，其中每个元素都是一个vector<int>，用于存储整数。对比c语言中的二维数组，两者的存储方式与索引访问方法是一样的，不同指出在于：1、vector的动态性(vector<vector<int>>可以动态调整大小，支持在运行时添加或删除行)，而二维数组的大小需要在编译时固定。2、内存管理方面，vector会自动管理内存，避免了内存泄漏，而二维数组需要手动管理(特别是在动态分配内存时)。3、便利性：vector中提供了许多遍历的成员函数(如size()、push_back()等)，使用更加灵活。
例题：
给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。在「杨辉三角」中，每个数是它左上方和右上方的数的和。
C++的vector写法：
class Solution {
public:
vector<vector<int>> generate(int numRows) {
vector<vector<int>> vv(numRows);
for(size_t i = 0; i < vv.size(); i++)
{
vv[i].resize(i+1,1);
}
for(size_t i = 2; i < vv.size(); i++)
{
for(size_t j = 1; j < vv[i].size()-1; j++)
{
vv[i][j] = vv[i-1][j] + vv[i-1][j-1];
}
}
return vv;
}
};在使用vector<vector<int>>做这道题时，我们可以发现每一列的数组是动态开辟的，这样极大的简化了代码量，且在遍历访问数组赋值时，由于resize初始化可以给1，我们在下面的遍历赋值中可以省去第一二行和每一行的首尾的赋值操作。
vector底层的模拟实现
框架：
template<class T>
class vector
{
public:
private:
iterator _start = nullptr;
iterator _finish = nullptr;
iterator _end_of_storage = nullptr;
};默认成员函数的实现：
//构造
/*vector()
{}*/
vector() = default; // C++11 强制生成默认构造
vector(size_t n, const T& val = T())
{
reserve(n);
for (size_t i = 0; i < n; i++)
{
push_back(val);
}
}
vector(int n, const T& val = T())
{ //解决传单个整形参数不匹配问题
reserve(n);
for (size_t i = 0; i < n; i++)
{
push_back(val);
}
}
template<class InputIterator>
vector(InputIterator first, InputIterator last)
{
while (first != last)
{
push_back(*first);
++first;
}
}
//拷贝构造
vector(const vector<T>& v)
{
reserve(v.size());
for (auto& e : v)
{
push_back(e);
}
}
//swap
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> tmp)
{
swap(tmp);
return *this;
}
//析构函数
~vector()
{
delete[] _start;
_start = _finish = _end_of_storage = nullptr;
} 上面的代码中实现了一个简单的 vector 类的构造函数、拷贝构造、析构函数和一些成员函数。
- 无参默认构造函数：使用 C++11 的特性生成一个默认构造函数。这里也可以写一个空的默认构造函数，我们只要在变量声明时给了缺省值，就无需再给默认值初始化。
- 带参默认构造函数：
vector(size_t n, const T& val = T())和vector(int n, const T& val = T())：这两个构造函数用于创建一个包含n个元素、初始值为val的vector。使用reserve(n)预留空间，随后通过push_back(val)向vector中添加元素。 - 迭代器区间构造函数：接受两个迭代器，复制
[first, last)范围内的元素到vector中。 - 拷贝构造函数：通过
reserve分配足够的空间，然后逐个使用push_back复制原vector的元素。 - 交换函数：通过交换内部指针
_start、_finish和_end_of_storage实现高效的资源交换。 - 赋值运算符重载：使用拷贝并交换的技术实现赋值运算符，避免多次资源管理，确保安全性和效率。
- 析构函数：清理分配的内存，将指针置为空，防止悬挂指针。
迭代器的实现：
//迭代器
typedef T* iterator;
typedef const T* const_iterator;
iterator begin()
{
return _start;
}
iterator end()
{
return _finish;
}
const_iterator begin() const
{
return _start;
}
const_iterator end() const
{
return _finish;
} 上面的代码实现了一个简单的迭代器接口，允许用户遍历 vector 中的元素。
iterator和const_iterator分别定义了指向元素的普通指针和常量指针类型，即普通迭代器和const迭代器。begin()返回指向vector第一个元素的迭代器（_start）。end()返回指向vector最后一个元素后一个位置的迭代器（_finish），用于表示迭代的结束。- 常量版本的
begin()和end()允许在const对象上使用迭代器，保证不会修改vector中的元素。
空间管理函数：
//empty
bool empty()
{
if (_start == _finish)
return true;
else
return false;
}
// size和capacity
size_t size() const
{
return _finish - _start;
}
size_t capacity() const
{
return _end_of_storage - _start;
}
// reserve
void reserve(size_t n)
{
if (n > capacity())
{
size_t old_size = size();
T* tmp = new T[n];
//memcpy(tmp, _start, old_size * sizeof(T));
for (size_t i = 0; i < old_size; i++)
{
tmp[i] = _start[i];
}
delete[] _start;
_start = tmp;
_finish = _start + old_size;
_end_of_storage = _start + n;
}
}
//resize
void resize(size_t n, T val = T())
{
if (n < _finish)
{
_finish = _start + n;
}
else
{
reserve(n);
while (_finish < _start + n)
{
*_finish = val;
++_finish;
}
}
} 上面代码实现了一些常用的 vector 成员函数，包括检查是否为空、获取大小和容量、以及调整容量和大小的功能。
- empty：检查
vector是否为空，判断begin()和end()是否相同。如果相同，返回true，表示没有元素；否则返回false。 size()：返回当前vector中元素的数量（_finish与_start的差）。capacity():返回当前分配的空间大小（_end_of_storage与_start的差），表示在不重新分配内存的情况下，最多能容纳多少元素。-
reserve(n)：用于调整vector的容量，如果n大于当前容量，重新分配内存并复制原有元素到新内存中，释放旧内存。这里需要注意如果对象中涉及到资源管理时，千万不能使用memcpy进行对象之间的拷贝，因为memcpy是浅拷贝，否则可能会引起内存泄漏甚至程序崩溃。 resize(n, val):调整vector的大小：如果新大小n小于当前大小，更新_finish；如果n大于当前大小，首先调用reserve(n)确保有足够的容量，然后在新增加的元素位置填充val。
增删查改：
//尾插
void push_back(const T& x)
{
if (_finish == _end_of_storage)
{
reserve(capacity() == 0 ? 4 : 2 * capacity());
}
*_finish = x;
++_finish;
}
//尾删
void pop_back()
{
if (!empty());
--_finish;
}
//insert
void insert(iterator pos, const T& x)
{
assert(pos >= _start);
assert(pos <= _finish);
//扩容
if (_finish == _end_of_storage)
{//解决迭代器失效的问题
size_t len = pos - _start;
reserve(capacity() == 0 ? 4 : 2 * capacity());
pos = _start + len;
}
iterator end = _finish - 1;
while (end >= pos)
{
*(end + 1) = *end;
end--;
}
*pos = x;
++_finish;
}
//erase
void erase(iterator pos)
{
assert(pos >= _start);
assert(pos < _finish);
iterator end = pos + 1;
while (end < _finish)
{
*(end - 1) = *end;
end++;
}
_finish--;
}
// operator[]
T& operator[](int i)
{
return _start[i];
}
const T& operator[](int i) const
{
return _start[i];
} 上面代码实现了 vector 的一些基本操作，包括尾插、尾删、插入、删除元素，以及重载下标运算符。
push_back(x)：在vector的末尾添加一个元素x。如果当前容量已满，调用reserve()扩大容量（初始为 4，之后每次扩展为当前容量的两倍），随后将新元素赋值到_finish指向的位置，然后递增_finish。pop_back()：从vector的末尾删除一个元素。先检查是否为空（条件判断有一个多余的分号，应去掉），然后递减_finish即可。insert(pos, x):在指定位置pos插入元素x。先检查pos是否有效。如果当前容量已满，扩容并更新pos的指向。通过向后移动元素，为新元素留出空间，最后将x放入pos位置，并递增_finish。erase(pos):删除指定位置的元素。先检查pos是否有效。将pos后面的元素向前移动，覆盖pos位置的元素，最后递减_finish。- 提供对
vector元素的随机访问。非常量版本返回可修改的元素引用，常量版本返回常量引用，保证元素不能被修改。
完整代码：
vector.h
#pragma once
#include<iostream>
#include<vector>
#include<assert.h>
using namespace std;
// 模板不能把声明和定义分离，因此只定义了一个.h文件。
namespace zy
{
//vctor<vector<int>>
template<class T>
class vector
{
public:
//构造
/*vector()
{}*/
vector() = default; // C++11 强制生成默认构造
vector(size_t n, const T& val = T())
{
reserve(n);
for (size_t i = 0; i < n; i++)
{
push_back(val);
}
}
vector(int n, const T& val = T())
{ //解决传单个整形参数不匹配问题
reserve(n);
for (size_t i = 0; i < n; i++)
{
push_back(val);
}
}
template<class InputIterator>
vector(InputIterator first, InputIterator last)
{
while (first != last)
{
push_back(*first);
++first;
}
}
//拷贝构造
vector(const vector<T>& v)
{
reserve(v.size());
for (auto& e : v)
{
push_back(e);
}
}
//swap
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> tmp)
{
swap(tmp);
return *this;
}
//析构函数
~vector()
{
delete[] _start;
_start = _finish = _end_of_storage = nullptr;
}
//迭代器
typedef T* iterator;
typedef const T* const_iterator;
iterator begin()
{
return _start;
}
iterator end()
{
return _finish;
}
const_iterator begin() const
{
return _start;
}
const_iterator end() const
{
return _finish;
}
//empty
bool empty()
{
if (_start == _finish)
return true;
else
return false;
}
// size和capacity
size_t size() const
{
return _finish - _start;
}
size_t capacity() const
{
return _end_of_storage - _start;
}
// reserve
void reserve(size_t n)
{
if (n > capacity())
{
size_t old_size = size();
T* tmp = new T[n];
//memcpy(tmp, _start, old_size * sizeof(T));
for (size_t i = 0; i < old_size; i++)
{
tmp[i] = _start[i];
}
delete[] _start;
_start = tmp;
_finish = _start + old_size;
_end_of_storage = _start + n;
}
}
//resize
void resize(size_t n, T val = T())
{
if (n < _finish)
{
_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 : 2 * capacity());
}
*_finish = x;
++_finish;
}
//尾删
void pop_back()
{
if (!empty());
--_finish;
}
//insert
void insert(iterator pos, const T& x)
{
assert(pos >= _start);
assert(pos <= _finish);
//扩容
if (_finish == _end_of_storage)
{//解决迭代器失效的问题
size_t len = pos - _start;
reserve(capacity() == 0 ? 4 : 2 * capacity());
pos = _start + len;
}
iterator end = _finish - 1;
while (end >= pos)
{
*(end + 1) = *end;
end--;
}
*pos = x;
++_finish;
}
//erase
void erase(iterator pos)
{
assert(pos >= _start);
assert(pos < _finish);
iterator end = pos + 1;
while (end < _finish)
{
*(end - 1) = *end;
end++;
}
_finish--;
}
// operator[]
T& operator[](int i)
{
return _start[i];
}
const T& operator[](int i) const
{
return _start[i];
}
private:
iterator _start = nullptr;
iterator _finish = nullptr;
iterator _end_of_storage = nullptr;
};
template<class T>
void print_vector(const vector<T>& v)
{
// 规定，不能在没有实例化的类模板里面取东西，编译器不能区分这里const_iterator是类型还是静态成员变量
// 想取东西需要在开头加typename，或者使用auto自动判断类型
//typename vector<T>::const_iterator it = v.begin();
auto it = v.begin();
while (it != v.end())
{
cout << *it << " ";
it++;
}
cout << endl;
}
void vector_test1()
{
vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
//v.push_back(5);
v.insert(v.begin() + 1, 6);
print_vector(v);
auto it = v.begin();
while (it != v.end())
{
//使用insert和erase以后，就不能直接访问，需要先更新这个迭代器的值。
//因为在vs的标准库中是会报错的，因为发生了迭代器失效
if ((*it) % 2 == 0)
{
//it = v.erase(it);
v.erase(it);
}
else {
++it;
}
}
print_vector(v);
}
};
vector迭代器失效问题
迭代器的主要作用就是让算法能够忽略底层数据结构的差异，可直接对容器进行遍历。其底层实际就是一个指针，或者是对指针进行了封装，比如：vector的迭代器就是原生态指针T*。因此迭代器失效实际上就是迭代器底层对应的指针所指向的空间被销毁了或被修改了，导致迭代器指向的是一块已经被释放的空间或被修改后的空间，造成的后果是程序崩溃或取值不对。
对于vector可能会导致其迭代器失效的操作有：
- 会引起其底层空间改变的操作，都有可能是迭代器失效，比如：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;
}- 指定位置元素的删除操作--erase
#include <iostream>
using namespace std;
#include <vector>
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就认为该位置迭代器失效了。
以本题为例：删除vector中所有的偶数。
#include <iostream>
using namespace std;
#include <vector>
int main()
{
vector<int> v{ 1, 2, 3, 4 };
auto it = v.begin();
while (it != v.end())
{
if (*it % 2 == 0)
v.erase(it);
++it;
}
return 0;
}这样写就会导致迭代器失效的问题，在删除it位置的元素后，后面的元素会先前覆盖，也就是说此时 it 又指向了下一个元素，然后it++，导致跳过了一个元素，有可能导致数据删除的不干净。解决办法是每次删除元素后，返回一个迭代器给it，在删除元素时跳过++it，这样就避免了‘遍历时有元素被跳过。
#include <iostream>
using namespace std;
#include <vector>
int main()
{
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;
}
return 0;
}值得注意的是：Linux下，g++编译器对迭代器失效的检测并不是非常严格，处理也没有vs下极端。且与vector类似，string在插入+扩容操作和erase之后，迭代器也会失效。
迭代器失效解决办法是在使用前，对迭代器重新赋值即可。
