目录
std::vector
是 C++ 标准库中的一个动态数组容器,位于 #include <vector>
头文件中。它是一个模板类,可以存储任何类型的对象,并根据需要动态调整其大小。std::vector
提供了高效的随机访问、尾部插入/删除操作(O(1)),但在中间插入或删除元素的性能较差(O(n))。
1. 特性
- 动态大小:
std::vector
能自动调整大小,随着元素的增加,容量会自动扩展。 - 连续内存存储:由于
std::vector
的存储空间是连续的,它支持像数组一样的随机访问,时间复杂度为 O(1)。 - 自动管理内存:
std::vector
自动管理内存的分配和释放,不需要手动调用new
和delete
。 - 模板类:可以存储任意类型的对象,必须在创建
std::vector
时指定存储的对象类型,例如std::vector<int>
存储整数,std::vector<std::string>
存储字符串。 - 支持范围检查:通过
at()
方法访问元素时会进行范围检查,如果索引越界会抛出std::out_of_range
异常,而使用operator[]
则不会进行检查。
2. 常用成员函数
2.1 构造函数
std::vector<T> v;
:创建一个空的向量。std::vector<T> v(n);
:创建一个包含n
个默认值为T()
的元素的向量。std::vector<T> v(n, value);
:创建一个包含n
个值为value
的元素的向量。std::vector<T> v{elements...};
:通过初始化列表来初始化std::vector
。
2.2 元素访问
v[i]
:返回向量中第i
个元素(不进行边界检查)。v.at(i)
:返回向量中第i
个元素(进行边界检查)。v.front()
:返回第一个元素。v.back()
:返回最后一个元素。v.data()
:返回指向存储数组的指针。
2.3 修改容器
v.push_back(value)
:在向量的末尾添加元素value
。v.pop_back()
:删除向量中的最后一个元素。v.insert(iterator, value)
:在指定位置插入元素。v.erase(iterator)
:删除指定位置的元素。v.clear()
:删除所有元素,使向量为空。v.resize(n)
:调整向量大小为n
,若n
大于当前大小,增加的元素将初始化为默认值。v.reserve(n)
:预留空间至少能容纳n
个元素,避免多次分配内存。
2.4 容量相关
v.size()
:返回向量中当前元素的数量。v.capacity()
:返回向量当前容量,即不重新分配内存的情况下,最多能容纳多少元素。v.empty()
:判断向量是否为空。
2.5 迭代器
v.begin()
:返回指向第一个元素的迭代器。v.end()
:返回指向最后一个元素之后的迭代器。v.rbegin()
:返回指向最后一个元素的反向迭代器。v.rend()
:返回指向第一个元素之前的反向迭代器。
3. 内存管理与效率
-
std::vector
的内存分配具有一定的增长策略,当容量不足时,会重新分配一个更大的内存块(通常是当前容量的 1.5 倍或 2 倍),并将现有元素复制到新的内存块中。这种策略可以减少多次分配和复制的开销,但也可能导致暂时的内存浪费。 -
使用
reserve()
可以预先分配足够的空间,从而避免多次扩容带来的开销,特别是在可以预测元素数量时。 -
shrink_to_fit()
:这个方法请求减少容量以匹配大小,不过实现可以选择忽略此请求。它可能会将未使用的空间释放给操作系统。
4. 示例:
#include <iostream>
#include <vector>
int main() {
std::vector<int> v = {1, 2, 3, 4, 5};
// 添加元素
v.push_back(6);
// 访问元素
std::cout << "Element at index 2: " << v[2] << std::endl;
std::cout << "First element: " << v.front() << std::endl;
std::cout << "Last element: " << v.back() << std::endl;
// 修改元素
v[1] = 10;
// 输出向量的所有元素
for (int x : v) {
std::cout << x << " ";
}
std::cout << std::endl;
// 删除最后一个元素
v.pop_back();
// 输出当前大小和容量
std::cout << "Size: " << v.size() << std::endl;
std::cout << "Capacity: " << v.capacity() << std::endl;
return 0;
}
5. 性能分析:
- 时间复杂度:
- 访问元素的时间复杂度为 O(1)。
- 在尾部插入或删除元素的时间复杂度为摊销 O(1),因为扩展操作在多次插入后才会触发。
- 插入或删除元素(非尾部)的时间复杂度为 O(n),因为插入或删除操作需要移动后续元素。
- 内存重分配开销:扩展向量容量时会进行内存重分配,这时所有的元素会被复制到新的内存地址,因此在频繁插入大量元素时,提前使用
reserve()
可以提高效率。
std::vector
是 C++ 中最常用的容器之一,因其灵活的动态数组功能、优秀的性能和易用性而广受欢迎。尽管它的动态扩展会有一定的开销,但通过适当的预分配(使用 reserve()
)和合理的使用方式,std::vector
可以满足大多数应用场景中的性能需求。
标签:std,返回,元素,C++,vector,内存,向量 From: https://www.cnblogs.com/keye/p/18401509