C++ Vector

vector是一个能够存放任意类型的动态数组，能够增加和压缩数据。

vector的用法类似于Python中的list数据类型。

基本概念

• std::vector是动态数组，支持随机访问
• 内存连续存储，支持下标操作
• 插入/删除尾部效率高，在中间或头部插入效率低
• 会自动扩容，容量(capacity) ≥ 元素个数(size)

容器特性

1. 顺序特性

   顺序容器中的元素按照严格的线性顺序排序，可以通过元素在序列中的位置访问对应的元素

2. 动态数组

   支持对序列中的任意元素进行快速直接访问，甚至可以通过指针算术进行该操作。

3. 能够感知内存分配器

   容器使用一个内存分配器对象来动态地处理它的存储需求

基本函数实现

1. 构造函数

   • vector(): 创建一个空的vector
   • vector(int nSize): 创建一个vector，元素个数为nSize
   • vector(int nSize, const t& t): 创建一个vector，元素个数为nSize，且值均为t
   • vector(const vector&): 复制构造函数
   • vector(begin, end): 复制[begin, end)区间内的另一个数组的元素到vector中

    std::vector<int> vec;
    vec.push_back(1);
   
    std::vector<int> vec(2);
    std::vector<int> vec(1,1);
   
    std::vector<int> vec = {1, 2, 3, 4};
    std::vector<int> vec{1, 2, 3, 4, 5};
   
    std::vector<int> vec_copy(vec);
   
    std::vector<int> vec2(vec.begin(), vec.begin()+3);
   

2. 增加函数

   • void push_back(const T& x): 向量尾部添加一个元素x
   • iterator insert(iterator it, const T& x): 向量中迭代器指向的位置前前增加一个元素x
   • iterator insert(iterator it, int n, const T& x): 向量中迭代器指向的位置前增加n个相同的元素x
   • iterator insert(iterator it, const_iterator first, const_iterator last): 向量中迭代器指向元素前插入另一个相同类型向量的[first,last)间的数据

    vector<int> vec = {1, 2, 3, 4};
    vec.push_back(7);
   
    auto it = vec.begin() + 1;
    vec.insert(it, 7);  // 1, 7, 2, 3, 4
   
    auto it = vec.begin() + 1;
    vec.insert(it, 2, 7);  // 1, 7, 7, 2, 3, 4
    // vec.insert(vec.begin()  + 1, 2, 7);
   
    vector<int> vec1 = {1, 4};
    vector<int> vec2 = {2, 3};
   
    vec1.insert(vec1.begin() + 1, vec2.begin(), vec2.end());
    // 结果: [1, 2, 3, 4]
   

3. 删除函数

   • iterator erase(iterator it): 删除向量中迭代器指向元素
   • iterator erase(iterator first, iterator last): 删除向量中[first,last)中元素
   • void pop_back(): 删除向量中最后一个元素
   • void clear(): 清空向量中所有元素

    vector<int> vec = {1, 2, 3, 4};
   
    auto it = vec.begin() + 1;
    vec.erase(it);
   
    vec.erase(vec.begin() + 1);
   
    vec.erase(vec.begin() + 1, vec.end() - 1);
   

4. 遍历函数

   • reference at(int pos): 返回pos位置元素的引用
   • reference front(): 返回首元素的引用
   • reference back(): 返回尾元素的引用
   • iterator begin(): 返回向量头指针，指向第一个元素
   • iterator end(): 返回向量尾指针，指向向量最后一个元素的下一个位置
   • reverse_iterator rbegin(): 反向迭代器，指向最后一个元素
   • reverse_iterator rend(): 反向迭代器，指向第一个元素之前的位置

5. 判断函数

   • bool empty() const: 判断向量是否为空，若为空，则向量中无元素

6. 大小函数

   • int size() const: 返回向量中元素的个数
   • int capacity() const: 返回当前向量所能容纳的最大元素值
   • int max_size() const: 返回最大可允许的 vector 元素数量值

7. 其他函数

   • void swap(vector&): 交换两个同类型向量的数据
   • void assign(int n, const T& x): 设置向量中前n个元素的值为x
   • void assign(const_iterator first, const_iterator last): 向量中[first,last)中元素设置成当前向量元素

8. 常用成员方法

方法	作用
push_back(x)	在尾部插入元素
pop_back()	删除尾部元素
insert(pos, x)	在指定位置插入元素
erase(pos)	删除指定位置元素
erase(first, last)	删除范围内元素
clear()	删除所有元素
operator[]	通过下标访问元素（不检查越界）
at(i)	通过下标访问元素（检查越界，抛异常）
front()	返回第一个元素
back()	返回最后一个元素
begin()	返回指向第一个元素的迭代器
end()	返回指向最后一个元素后面的位置迭代器
rbegin() / rend()	反向迭代器
size()	当前元素个数
capacity()	当前分配的空间大小
resize(n)	改变大小，多余元素会被删除或新元素初始化
reserve(n)	预留容量，避免频繁扩容
shrink_to_fit()	把容量缩小到正好容纳当前元素数
empty()	判断是否为空
swap(v2)	与另一个 vector 交换内容

常见操作

#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> v;   // 定义一个空 vector<int>

    // 插入
    v.push_back(10);
    v.push_back(20);
    v.push_back(30);

    // 遍历
    cout << "Elements: ";
    for (int x : v) cout << x << " ";
    cout << endl;

    // 下标访问
    cout << "v[1] = " << v[1] << endl;

    // 大小
    cout << "size=" << v.size() << " capacity=" << v.capacity() << endl;

    // 删除最后一个
    v.pop_back();

    // 插入指定位置
    v.insert(v.begin() + 1, 15);

    // 删除指定位置
    v.erase(v.begin());  

    // 清空
    v.clear();

    cout << "Final size=" << v.size() << endl;
}

vector对象的定义和初始化

#include <vector>
using namespace std;

std::vector是一个类模板（class template），在编译时根据指定的元素类型T生成对应的类

template <
	class T,								              // 存储的元素类型
	class Allocator = std::allocator<T>		// 内存分配器（默认用std::allocator>
> class vector;	

例如：

vector<int> v1;		  // 实例化为存int的动态数组
vector<string> v2;  // 实例化为存string的动态数组

和数组对比

• vector 动态分配，支持自动扩容，安全且方便。
• 普通数组大小固定，越界访问不会报错。
• 推荐优先用 vector 代替裸数组。

动态分配和指针

std::vector<int> vec = {1, 2, 3, 4};
int* p = &vec[2];
vec.push_back(5);
std::cout << *p << std::endl;

在上面的程序中，首先定义了一个容量为4的vector，并且定义了一个指向向量第二个数值的指针

指针 p 指向 vec[2]（即值为 3 的元素），保存了该元素的内存地址。

接着使用push_back函数增加了一个元素，此时由于vec默认的容量为4，添加后为5个元素，超出了容量，触发自动扩容机制

这时候会重新为vec申请容量更大（大于5）的内存，并且将元素复制到新的内存中，释放旧内存

重新分配后，原来所有指向vec的迭代器、引用和指针都有可能失效，p成为悬空指针

永远不要在可能重新分配的操作（ push_back 、 resize、 insert等）中保留指向 std::vector 元素的原始指针。重新分配后使用索引或更新指针。