C语言数据结构之vector底层实现机制解析

什么是vector?

vector是C++标准库中的一种容器，可以动态调整大小，用于存储数据。

vector的底层实现机制

vector实际上是通过数组实现的，当需要添加元素时，如果当前数组已满，就会重新创建一个更大的数组，并将原数组中的元素复制到新数组中。这样，内存空间得到了增加，同时操作后的元素仍然是顺序存储, 存取元素的时间复杂度仍为O(1)。

vector的成员变量

vector的成员变量包括三个关键变量：

• start_：指向vector的第一个元素的指针。
• finish_：指向当前vector中最后一个元素的后一个位置。
• end_of_storage_：指向vector的一个可用空间(不属于vector中的元素)，当添加元素时，如果vector的容量已满，就需要扩容。

vector的操作

vector提供了以下常用的方法：

• push_back(const T& x)：将元素x添加到向量的末尾
• pop_back()：从向量的末尾移除一个元素
• size()：返回向量中元素的个数
• capacity()：返回向量中第一个元素指针到reserve空间末尾的距离
• resize(size_t n, T x)：改变容器的大小为n，如果改变后的大小小于原来的大小，会删除多余的元素，如果改变后的大小大于原来的大小，则会使用元素的默认构造函数添加元素。
• reserve(size_t n)：改变容器中可存储元素的空间大小为n，不会改变向量中的元素数量，如果n小于向量当前的容量，则不会改变向量的容量。如果n大于向量当前的容量，则会改变向量的容量，并保证扩容后仍然是顺序存储。

vector的时间复杂度

在大多数情况下，vector的时间复杂度如下：

• 访问元素：O(1)
• 添加元素：O(1)或O(n)（取决于是否需要扩容）
• 删除元素：O(n)

vector的示例说明

示例一：添加元素

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    vector<int> vec;
    for (int i = 0; i < 10; ++i)
    {
        vec.push_back(i);
    }
    for (int i = 0; i < vec.size(); ++i)
    {
        cout << vec[i] << endl;
    }
}

在这个示例中，我们创建一个vector<int>类型的对象，然后将0到9的整数添加到这个对象中。使用push_back()方法将元素添加到vector末尾。添加元素的时间复杂度是O(1)。最后，我们遍历向量并打印所有元素。

示例二：扩容

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    vector<int> vec;
    cout << "当前vector的容量为：" << vec.capacity() << endl;
    for (int i = 0; i < 10; ++i)
    {
        vec.push_back(i);
    }
    cout << "当前vector的容量为：" << vec.capacity() << endl;
    vec.reserve(20);
    cout << "reserve(20)后当前vector的容量为：" << vec.capacity() << endl;
}

在这个示例中，我们创建一个vector<int>类型的对象，并使用capacity()方法打印它的初始容量。然后，我们向vector中添加10个整数，每次添加一个整数时，vector都会检查是否需要扩容。最后，我们使用reserve()方法扩展向量的容量，并再次使用capacity()方法打印容量。

输出结果如下：

当前vector的容量为：0
当前vector的容量为：16
reserve(20)后当前vector的容量为：20

在这个示例中，我们观察到在添加元素时vector会自动扩容并保证元素的顺序存储，同时我们也观察到reserve()方法可以手动扩展向量的容量。

总结

成功地理解vector的底层实现机制是学习数据结构的重要一步。vector的时间复杂度通常是常数时间，可以在大多数情况下保证高效和可靠。当操作需求增加，遇到瓶颈时，我们可以手动通过reserve()方法扩容，这可以有效减少不必要的重复分配内存操作。