C++ vector源码解析 |21xrx.com

C++ vector源码解析

2023-07-12 00:56:55 深夜i -- --

C++ vector 源码解析容器

C++ vector是常用的STL容器之一，它提供了动态数组的功能，可以方便地管理和操作可变长度的数组。在实际开发中，我们经常使用vector来存储和处理数据。本文将从源码的角度，解析C++ vector的实现原理。

vector的定义

vector是一个模板类，它的定义如下：


template <typename T, typename Allocator = allocator<T>>
class vector;

其中T表示存储的元素类型，Allocator是可选的内存分配器类型，默认使用std::allocator。vector类的主要成员函数包括：push_back、pop_back、resize、clear、size、capacity等。

vector的内存结构

vector在内存中以连续的、动态分配的方式存储元素。当元素个数逐渐增加，vector会动态扩展容量，分配更大的内存空间。当元素个数减少或删除元素时，vector会缩减容量，释放一部分内存空间。vector的实际容量可以通过capacity()函数获取，而元素个数则可以通过size()函数获取。

vector的内存管理

为了支持动态分配和释放内存，vector内部使用了一套内存管理机制。这个机制主要由两个关键函数实现：allocate()和deallocate()。

allocate()函数用于分配内存空间，它的实现如下：


T* allocate(size_type n, const void* hint=0) {
  return _Alloc::allocate(n * sizeof(T), hint);
}

其中，_Alloc是vector的分配器类型，默认使用std::allocator。allocate函数会根据指定的元素数量n，计算需要分配的内存空间大小n * sizeof(T)，并调用分配器的allocate函数分配内存。

deallocate()函数用于释放内存空间，它的实现如下：


void deallocate(pointer p, size_type n) {
  _Alloc::deallocate(p, n * sizeof(T));
}

其中，p是要释放的内存空间的指针，n是要释放的内存空间大小（以元素数量为单位）。deallocate函数会调用分配器的deallocate函数释放内存。

vector的元素存取

vector中的元素可以通过下标来访问。例如，下面的代码片段可以获取vector中的第i个元素：


vector<int> v;
int x = v[i];

vector的下标操作会调用operator[]操作符重载函数。默认情况下，operator[]函数的实现如下：


reference operator[](size_type i) {
  return *(begin() + i);
}

其中，begin()函数用于获取vector的起始位置迭代器，i表示要访问的元素下标。operator[]函数会通过指针计算的方式，返回第i个位置上的元素。

vector的插入操作

vector的插入操作主要由push_back()函数实现，它可以在vector的末尾添加一个元素。下面是push_back()函数的默认实现代码：


void push_back(const T& x) {
  if (size() == capacity()) {
    reserve(max(size() + 1, size() * 3));
  }
  _Alloc::construct(&elem[size()], x);
  ++_Size;
}

push_back()函数首先判断当前vector是否已经达到容量上限。如果已经达到容量上限，则调用reserve()函数扩展vector的内存空间。reserve()函数会重新分配更大的内存空间，并将旧的元素数据拷贝到新的内存空间中。

在扩展内存空间后，push_back()函数会调用construct()函数，将新元素插入到vector的末尾位置。construct()函数的实现代码如下：


void construct(pointer p, const T& x) {
  ::new ((void*)p) T(x);
}

construct()函数会在指定的内存地址p上，构造一个新的元素，并初始化为x的值。这样，新元素就成功地插入到了vector的末尾位置。

vector的删除操作

vector的删除操作主要由pop_back()函数实现。它可以删除vector中的最后一个元素。下面是pop_back()函数的默认实现代码：


void pop_back() {
  _Alloc::destroy(&elem[size()-1]);
  --_Size;
}

pop_back()函数首先调用destroy()函数，释放vector中的最后一个元素。destroy()函数的实现代码如下：


void destroy(pointer p){
  p->~T();
}

destroy()函数会调用元素的析构函数，释放元素占用的内存。最后，pop_back()函数还会将vector的元素数量减1，实现了元素的删除操作。

总结

本文从vector的定义、内存结构、内存管理、元素存取、插入操作、删除操作等几个方面，对C++ vector的源码进行了解析。熟悉vector的实现原理不仅有助于我们更好地理解该容器的使用方式，还可以帮助我们深入了解STL的存储和数据结构设计。

上一篇: idea打包java可执行jar包

下一篇: C++程序设计(原书第3版)

评论区

()

相似文章