目录
专栏:C++学习笔记
在C++标准模板库(STL)中,vector
是一个非常重要的容器,它提供了一个动态数组,可以根据需要自动调整其大小。
1. vector
的介绍及使用
1.1 vector
的介绍
1.1.1 vector
是什么
vector
是一个序列容器,表示可变大小的数组。与数组相似,vector
使用连续的存储空间来存储元素,因此可以通过下标访问元素,且效率与数组相当。不同的是,vector
的大小是动态的,会随着元素的增加自动调整。
小李的理解:vector
就像是一个能自动扩展的数组,当需要放更多的东西时,它会自动找更大的地方,把原来的东西搬过去。
1.1.2 vector
的存储机制
vector
的实现基于动态分配数组。当新元素插入时,如果当前数组容量不足,vector
会重新分配一个更大的数组,并将现有元素复制到新数组中。这种重新分配是一个耗时操作,但vector
通常会预留额外的空间以减少重新分配的频率,从而优化性能。
小李的理解:vector
的存储方式就像是搬家,当家里东西太多放不下时,它会找到一个更大的房子,把所有东西搬过去,这样下次再放东西就不用总是搬家了。
1.2 vector
的使用
使用vector
时,必须熟悉其常用接口。以下是一些重要的接口:
1.2.1 定义和构造函数
- 无参构造函数:
vector()
- 指定大小和默认值的构造函数:
vector(size_type n, const value_type& val = value_type())
- 拷贝构造函数:
vector(const vector& x)
- 使用迭代器范围的构造函数:
vector(InputIterator first, InputIterator last)
#include <vector>
#include <iostream>
int main() {
std::vector<int> v1; // 默认构造函数
std::vector<int> v2(10, 1); // 构造一个包含10个1的vector
std::vector<int> v3(v2); // 拷贝构造
std::vector<int> v4(v2.begin(), v2.end()); // 迭代器范围构造
return 0;
}
小李的理解:创建vector
的方法就像是买不同规格的箱子,有的箱子是空的(无参构造),有的箱子里已经装满了指定数量的物品(指定大小和默认值),有的箱子是完全照搬另一个箱子的东西(拷贝构造),还有的是根据一个范围内的物品来装箱(迭代器范围构造)。
1.2.2 迭代器
begin()
和end()
:获取首元素和末尾后一个位置的迭代器rbegin()
和rend()
:获取末元素和首元素前一个位置的反向迭代器
#include <vector>
#include <iostream>
int main() {
std::vector<int> v{1, 2, 3, 4, 5};
for (auto it = v.begin(); it != v.end(); ++it) {
std::cout << *it << " ";
}
std::cout << std::endl;
return 0;
}
小李的理解:迭代器就像是一个指针,可以帮我们一个一个地访问箱子里的东西,从头到尾,也可以从尾到头。
1.2.3 容量相关操作
size()
:获取当前元素个数capacity()
:获取当前容量empty()
:判断是否为空resize()
:调整大小reserve()
:预留存储空间
#include <vector>
#include <iostream>
int main() {
std::vector<int> v;
v.reserve(10); // 预留空间
v.resize(5); // 调整大小为5
std::cout << "Size: " << v.size() << ", Capacity: " << v.capacity() << std::endl;
return 0;
}
小李的理解:size
告诉我们箱子里有多少东西,capacity
告诉我们箱子能装多少东西,empty
告诉我们箱子是不是空的,resize
可以调整箱子里的东西数量,reserve
可以提前预留空间,避免频繁换箱子。
1.2.4 元素访问和修改
operator[]
:下标访问at()
:带边界检查的访问push_back()
:尾部插入pop_back()
:尾部删除insert()
:在指定位置插入erase()
:删除指定位置的元素swap()
:交换两个vector
的内容
#include <vector>
#include <iostream>
int main() {
std::vector<int> v{1, 2, 3, 4, 5};
v.push_back(6); // 尾部插入
std::cout << "After push_back(6): ";
for (const auto& elem : v) {
std::cout << elem << " ";
}
std::cout << std::endl; // After push_back(6): 1 2 3 4 5 6
v.pop_back(); // 尾部删除
std::cout << "After pop_back: ";
for (const auto& elem : v) {
std::cout << elem << " ";
}
std::cout << std::endl; // After pop_back: 1 2 3 4 5
v.insert(v.begin() + 2, 10); // 在第三个位置插入10
std::cout << "After insert at position 2: ";
for (const auto& elem : v) {
std::cout << elem << " ";
}
std::cout << std::endl; // After insert at position 2: 1 2 10 3 4 5
v.erase(v.begin() + 2); // 删除第三个位置的元素
std::cout << "After erase at position 2: ";
for (const auto& elem : v) {
std::cout << elem << " ";
}
std::cout << std::endl; // After erase at position 2: 1 2 3 4 5
std::vector<int> v2{7, 8, 9};
std::swap(v, v2); // 交换内容
std::cout << "After swap: v: ";
for (const auto& elem : v) {
std::cout << elem << " ";
}
std::cout << std::endl; // After swap: v: 7 8 9
std::cout << "v2: ";
for (const auto& elem : v2) {
std::cout << elem << " ";
}
std::cout << std::endl; // v2: 1 2 3 4 5
return 0;
}
解释:
v.push_back(6)
在vector
末尾插入6,结果为1 2 3 4 5 6
。v.pop_back()
删除vector
末尾元素,结果为1 2 3 4 5
。v.insert(v.begin() + 2, 10)
在第三个位置插入10,结果为1 2 10 3 4 5
。v.erase(v.begin() + 2)
删除第三个位置的元素,结果为1 2 3 4 5
。std::swap(v, v2)
交换v
和v2
的内容,v
变为7 8 9
,v2
变为1 2 3 4 5
。
小李的理解:vector
就像是一个万能的箱子,不仅可以用下标访问里面的东西,还可以在尾部添加或删除东西,在指定位置插入或删除东西,还能和另一个箱子的东西互换。
1.3 迭代器失效问题
在vector
的操作中,有些操作可能会导致迭代器失效,如resize
、reserve
、insert
、assign
、push_back
等。当这些操作引起底层数组重新分配时,原来的迭代器会指向无效的内存区域,继续使用这些迭代器会导致程序崩溃。因此,在这些操作后,必须重新获取迭代器。
#include <vector>
#include <iostream>
int main() {
std::vector<int> v{1, 2, 3, 4, 5, 6};
auto it = v.begin();
// 操作可能导致迭代器失效
v.assign(100, 8);
// 必须重新获取迭代器
it = v.begin();
while (it != v.end()) {
std::cout << *it << " ";
++it;
}
std::cout << std::endl;
return 0;
}
小李的理解:迭代器就像是箱子里的一个标记,告诉我们从哪里开始访问东西。但是如果箱子重新调整过,原来的标记就会失效,所以每次调整后需要重新放置标记。
2. vector
深度剖析及模拟实现
2.1 std::vector
的模拟实现
要深入理解vector
,可以尝试实现一个简单的模拟版本。下面是一个简化的vector
实现示例:
#include <iostream> // Include this header for std::cout and std::endl
template <typename T>
class Vector {
private:
T* data;
size_t sz;
size_t cap;
void reallocate(size_t new_cap) {
T* new_data = new T[new_cap];
for (size_t i = 0; i < sz; ++i) {
new_data[i] = std::move(data[i]);
}
delete[] data;
data = new_data;
cap = new_cap;
}
public:
Vector() : data(nullptr), sz(0), cap(0) {}
void push_back(const T& value) {
if (sz == cap) {
reallocate(cap == 0 ? 1 : cap * 2);
}
data[sz++] = value;
}
size_t size() const { return sz; }
size_t capacity() const { return cap; }
T& operator[](size_t index) { return data[index]; }
~Vector() { delete[] data; }
};
int main() {
Vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
std::cout << "v size: " << v.size() << ", capacity: " << v.capacity() << std::endl; // v size: 3, capacity: 4
for (size_t i = 0; i < v.size(); ++i) {
std::cout << v[i] << " ";
}
std::cout << std::endl; // 1 2 3
return 0;
}
解释:
v.push_back(1)
,v.push_back(2)
,v.push_back(3)
将三个元素插入vector
。- 初始容量为0,每次容量不足时容量翻倍,最终容量为4,大小为3。
- 输出
vector
大小和容量,结果为v size: 3, capacity: 4
。 - 输出所有元素,结果为
1 2 3
。
小李的理解:这个模拟实现就像是自己动手做一个可扩展的箱子,当箱子满了,我们自己找个更大的地方搬过去,这样就可以不断地增加箱子里的东西。
2.2 memcpy
的使用问题
在vector
的实现中,有时会使用memcpy
来复制内存。但是,如果元素类型是自定义类型,且涉及资源管理,memcpy
的浅拷贝会导致问题,如内存泄漏或程序崩溃。因此,对于自定义类型,应避免使用memcpy
,而应使用元素的拷贝构造函数。
#include <iostream>
#include <cstring>
class MyClass {
public:
int* data;
MyClass(int value) {
data = new int(value);
}
~MyClass() {
delete data;
}
};
int main() {
MyClass obj1(10);
MyClass obj2(20);
// 浅拷贝导致问题
std::memcpy(&obj2, &obj1, sizeof(MyClass));
std::cout << *obj2.data << std::endl; // 可能导致程序崩溃
return 0;
}
小李的理解:memcpy
就像是复制一个箱子里的东西,但如果箱子里的东西需要特别处理(比如需要手动管理的资源),直接复制可能会出问题,应该用正确的方法来复制这些东西。、
结论:如果对象中涉及到资源管理时,千万不能使用memcpy进行对象之间的拷贝,因为memcpy是浅拷贝,否则可能会引起内存泄漏甚至程序崩溃。
2.3 动态二维数组
使用vector
可以方便地构建动态二维数组,例如,生成杨辉三角:
#include <vector>
#include <iostream>
void generate_pascals_triangle(size_t n) {
std::vector<std::vector<int>> vv(n);
for (size_t i = 0; i < n; ++i) {
vv[i].resize(i + 1, 1);
for (size_t j = 1; j < i; ++j) {
vv[i][j] = vv[i - 1][j] + vv[i - 1][j - 1];
}
}
for (const auto& row : vv) {
for (int val : row) {
std::cout << val << " ";
}
std::cout << std::endl;
}
}
int main() {
size_t n = 5; // You can change this value to generate more rows of Pascal's Triangle
generate_pascals_triangle(n);
return 0;
}
小李的理解:动态二维数组就像是很多小箱子放在一个大箱子里,每个小箱子可以根据需要调整大小,用来存放不同数量的东西。比如杨辉三角,每一行的小箱子里放的东西都不一样多。
总结
C++中的
vector
是一个动态数组,可以根据需要自动调整大小。它使用连续的内存空间,像普通数组一样可以通过下标快速访问元素,但与普通数组不同的是,vector
可以动态增加或减少元素。创建vector
有多种方式,包括默认构造、指定大小和默认值、拷贝构造等。常用的操作有插入、删除、访问和遍历元素,vector
还提供了容量管理的方法,如reserve
和resize
,以优化性能。在使用过程中需要注意迭代器失效的问题,当vector
重新分配内存时,原来的迭代器会失效,必须重新获取。通过这些特性,vector
在处理动态数据时非常方便和高效。