【C++STL详解 —— vector的介绍及使用】
- vector的介绍
- vector的使用
- vector的构造
- vector iterator 的使用
- begin和end
- rbegin和rend
- vector 空间增长问题
- size和capacity
- reserve和resize
- empty
- vector 增删查改
- push_back和pop_back
- insert和erase
- find
- swap
- 元素访问
- vector 迭代器失效问题(重点)
- 迭代器失效问题举例
- 迭代器失效解决方法
vector的介绍
在C++中,vector是一个非常重要和常用的容器类型,它是标准模板库(Standard Template Library, STL)的一部分。简单来说,vector是一个能够存储任意类型元素的动态数组,其大小可以在运行时自动扩展或缩减。
vector的具体特性如下:
- 动态数组: 与普通数组不同,vector可以根据需要动态地增加或减少元素,而不需要程序员手动管理内存。
- 模板: vector是一个模板类,意味着它可以用来存储任意类型的对象。例如,vector用于存储整数,vector用于存储字符串。
- 自动管理内存: vector自动管理其存储的元素的内存。当vector的容量不足以容纳更多元素时,它会自动重新分配内存空间以容纳新元素。
- 随机访问: vector支持通过索引快速访问其元素(类似于数组),这意味着你可以直接通过下标来获取或修改任何位置的元素。
vector的使用
vector的构造
- 默认构造函数:创建一个空的vector容器。
std::vector<int> v;
- 填充构造函数:创建一个具有特定大小的vector,可以指定元素的初始值。
std::vector<int> v(5, 10); // 创建一个包含5个元素的vector,每个元素的初始值都是10。
- 范围构造函数:通过复制另一个容器或数组的元素范围来创建vector。
std::vector<ElementType> v(begin_iterator, end_iterator);
//例子:
std::vector<int> original = {1, 2, 3, 4, 5};
// 假设我们想从original中复制从第二个元素到第四个元素(2, 3, 4)
std::vector<int> subVector(original.begin() + 1, original.begin() + 4);
// subVector现在包含{2, 3, 4}
- 拷贝构造函数: 通过复制另一个vector来创建一个新的vector。
std::vector<int> original(5, 10); // original是一个包含5个元素,每个元素值为10的vector。
std::vector<int> v(original); // 通过拷贝original创建一个新的vector v。
- 初始化列表构造函数(C++11及之后版本):允许使用初始化列表来创建vector。
std::vector<int> v = {1, 2, 3, 4, 5}; // 使用初始化列表创建vector。
vector iterator 的使用
iterator begin();
iterator end();
const_iterator begin() const;
const_iterator end() const;
//iterator是typedef定义的一个指向T类型对象的指针,
//而const_iterator是一个指向const T类型对象的指针。
begin和end
begin(): 获取第一个数据位置的iterator/const_iterator
end(): 获取最后一个数据的下一个位置的iterator/const_iterator。
#include <iostream>
#include <vector>
using namespace std;
int main()
{
vector<int> v(10, 2);
//正向迭代器遍历容器
vector<int>::iterator it = v.begin();
while (it != v.end())
{
cout << *it << " ";
it++;
}
cout << endl;
return 0;
}
rbegin和rend
rbegin(): 获取最后一个数据位置的reverse_iterator.
rend(): 获取第一个数据前一个位置的reverse_iterator
#include <iostream>
#include <vector>
using namespace std;
int main()
{
vector<int> v(10, 2);
//反向迭代器遍历容器
vector<int>::reverse_iterator rit = v.rbegin();
while (rit != v.rend())
{
cout << *rit << " ";
rit++;
}
cout << endl;
return 0;
}
vector 空间增长问题
size和capacity
size_t size() const;
size_t capacity() const;
容量空间 | 接口说明 |
---|---|
size | 获取数据个数 |
capacity | 获取容量大小 |
- capacity的代码在vs和g++下分别运行会发现,vs下capacity是按1.5 倍增长的,g++是按 2 倍增长的。 vs是PJ版本STL,g++是SGI版本STL。
- reserve只负责开辟空间,如果确定知道需要用多少空间,reserve可以缓解vector增容的代价缺陷问题。
- resize在开空间的同时还会进行初始化,影响size。
vector<int> v(10, 2);
cout << v.size() << endl; //获取当前容器中的有效元素个数
cout << v.capacity() << endl; //获取当前容器的最大容量
reserve和resize
void reserve(size_type new_cap);
void resize(size_type count, const value_type& value = value_type());
/*
在resize()中,const value_type& value = value_type() 是一个默认参数。
这个参数表示如果调用 resize() 函数时不提供第二个参数(即 value),
则默认使用 value_type() 构造一个新的元素来填充 std::vector 中的新增位置。
在这里,value_type 是 std::vector 存储的元素类型。
例如,如果 std::vector 存储的是 int 类型的元素,
那么 value_type 就是 int。默认构造一个 int 类型的对象会得到值为 0 的对象。
*/
容量空间 | 接口说明 |
---|---|
resize | 改变vector的size |
reserve | 改变vector的capacity |
reserve规则:
1、当所给值大于容器当前的capacity时,将capacity扩大到该值。
2、当所给值小于容器当前的capacity时,什么也不做。
resize规则:
1、当所给值大于容器当前的size时,将size扩大到该值,扩大的元素为第二个所给值,若未给出,则默认为0。
2、当所给值小于容器当前的size时,将size缩小到该值。
vector<int> v(10, 2);
cout << v.size() << endl; //10
cout << v.capacity() << endl; //10
v.reserve(20); //改变容器的capacity为20,size不变
cout << v.size() << endl; //10
cout << v.capacity() << endl; //20
v.resize(15); //改变容器的size为15
cout << v.size() << endl; //15
cout << v.capacity() << endl; //20
empty
bool empty() const;
容量空间 | 接口说明 |
---|---|
empty | 判断是否为空 |
vector<int> v(10, 2);
cout << v.empty() << endl;
vector 增删查改
push_back和pop_back
void push_back(const T& value);
void pop_back();
通过push_back函数对容器进行尾插,pop_back函数对容器进行尾删。
insert和erase
// insert
iterator insert(iterator pos, const T& value); // 插入单个元素
void insert(iterator pos, size_type count, const T& value); // 插入多个相同值的元素
template<class InputIterator>
void insert(iterator pos, InputIterator first, InputIterator last); // 插入范围内的元素
//erase
iterator erase(iterator pos); // 删除单个元素
iterator erase(iterator first, iterator last); // 删除范围内的元素
通过insert函数可以在所给迭代器位置插入一个或多个元素,通过erase函数可以删除所给迭代器位置的元素,或删除所给迭代器区间内的所有元素(左闭右开)。
vector<int> v1;
vector<int> v2{ 'a','b','c'};
v1.insert(v1.begin(), 10);
v1.insert(v1.begin(), v2.begin(), v2.end());
for (auto e : v1)
{
cout << e << ' ';
}
find
template <class InputIterator, class T>
InputIterator find (InputIterator first, InputIterator last, const T& val);
first
和last
是迭代器,它们分别指向容器中要进行查找的范围的开始和结束。注意,范围包括first
指向的元素,但不包括last
指向的元素。
val
是要查找的值。返回值是一个迭代器,指向在范围[first, last)
中找到的第一个与val
相等的元素。如果找不到这样的元素,则返回值等于last
。
std::vector<int> vec = {1, 2, 3, 4, 5, 6};
auto it = std::find(vec.begin(), vec.end(), 5);
if (it != vec.end()) {
std::cout << "Found the number: " << *it << std::endl;
} else {
std::cout << "Number not found." << std::endl;
}
注意: find函数是在算法模块(algorithm)当中实现的,不是vector的成员函数。
swap
通过swap函数可以交换两个容器的数据空间,实现两个容器的交换。
vector<int> v1(10, 1);
vector<int> v2(10, 2);
v1.swap(v2); //交换v1,v2的数据空间
元素访问
vector当中实现了 [ ] 操作符的重载,因此我们也可以通过“下标+[ ]”的方式对容器当中的元素进行访问。
vector<int> v(10, 1);
//使用“下标+[]”的方式遍历容器
for (size_t i = 0; i < v.size(); i++)
{
cout << v[i] << " ";
}
cout << endl;
vector 迭代器失效问题(重点)
迭代器失效问题举例
- 插入(push_back, insert):当向vector插入元素时,如果需要更多的内存空间以容纳新元素,vector可能会重新分配其内存以获得更大的容量。这种重新分配会使所有之前的迭代器、引用和指针失效。
- 删除(erase, pop_back):从vector中删除元素后,所有指向被删除元素之后元素的迭代器、引用和指针都将失效。
- 缩减容量(shrink_to_fit, resize):缩减vector的容量可能导致重新分配内存,从而使现有的迭代器、引用和指针失效。
插入元素导致的迭代器失效
问题:在vector中插入元素导致容器重新分配内存。
#include <vector>
#include <iostream>
int main() {
std::vector<int> vec = {1, 2, 3, 4, 5};
auto it = vec.begin() + 2; // 指向3
vec.push_back(6); // 可能导致迭代器it失效,因为可能会重新分配内存
// 使用失效的迭代器it访问元素
// std::cout << *it << std::endl; // 未定义行为
return 0;
}
删除元素导致的迭代器失效
问题:从vector中删除元素导致之后的迭代器失效。
std::vector<int> vec = {1, 2, 3, 4, 5};
auto it = vec.begin() + 3; // 指向4
vec.erase(vec.begin() + 2); // 删除元素3,导致迭代器it失效
// 使用失效的迭代器it访问元素
// std::cout << *it << std::endl; // 未定义行为
缩减容量导致的迭代器失效
问题:使用shrink_to_fit或resize缩减vector容量导致的迭代器失效。
std::vector<int> vec = {1, 2, 3, 4, 5};
vec.reserve(100); // 预分配较大的内存空间
auto it = vec.begin() + 2; // 指向3
vec.shrink_to_fit(); // 缩减容量,可能导致迭代器it失效
// 使用失效的迭代器it访问元素
// std::cout << *it << std::endl; // 未定义行为
迭代器失效解决方法
插入元素导致的迭代器失效 -> 解决方法:重新获取迭代器。
// 在push_back后重新获取迭代器
it = vec.begin() + 2;
std::cout << *it << std::endl; // 正确访问
删除元素导致的迭代器失效 -> 解决方法:使用erase返回的迭代器。
// 使用erase返回的迭代器更新it
it = vec.erase(vec.begin() + 2); // 现在it指向4
std::cout << *it << std::endl; // 正确访问
缩减容量导致的迭代器失效 -> 解决方法:避免在需要保持迭代器有效时使用shrink_to_fit,或者在操作后重新获取迭代器。
// 在shrink_to_fit后重新获取迭代器
it = vec.begin() + 2;
std::cout << *it << std::endl; // 正确访问