C++中的vector容器在内存上是如何实现的?
C++中的vector
是一个序列容器,它封装了动态大小数组的功能。在内存上,vector
通常是这样实现的:
- 动态数组:
vector
底层使用一个动态分配的数组来存储元素。当我们创建一个vector
时,它会根据需要的容量在堆上分配一块内存。 -
自动扩容:当向
vector
添加元素而当前的内存不足以容纳更多元素时,vector
会自动进行扩容。这通常涉及到以下步骤:- 分配一个更大的新内存块。
- 将现有元素从旧内存块复制到新内存块。
- 释放旧内存块。
- 更新内部指针以指向新的内存块。
- 连续内存:
vector
的元素在内存中是连续存储的,这意味着可以通过指针算术直接访问它们,这也使得vector
能够提供类似数组的高效随机访问。 -
空间复杂度:
vector
通常会预留一些额外的未使用空间,以减少频繁扩容的需求。当新元素被添加到vector
时,如果预留空间足够,则无需重新分配内存。
应用场景举例:
假设我们要存储一个班级里所有学生的成绩,可以使用vector
来动态地添加成绩:
#include <vector>
#include <iostream>
int main() {
std::vector<int> grades;
// 添加成绩
grades.push_back(85);
grades.push_back(92);
grades.push_back(88);
// 打印成绩
for (int grade : grades) {
std::cout << grade << std::endl;
}
// 由于vector内存是连续的,可以通过指针访问
int* p = &grades[0];
std::cout << "第一个成绩是:" << *p << std::endl;
return 0;
}
在这个例子中,随着我们不断添加成绩,vector
可能会进行几次内存重新分配,每次都会选择更大的内存块以存储更多的元素。由于vector
的内存是连续的,我们可以像使用数组一样访问它的元素。