C++ vector动态扩容及动态数组C语言实现

std::vector是stl中的动态数组，支持动态扩容，stl是如何进行动态扩容的呢？了解其动态扩容过程有什么用？

一、探究std::vector动态扩容过程

我们通过下面这段代码来了解一下std::vector的动态扩容过程。

#include <iostream>
#include <vector>

int main()
{
    std::vector<int> vec;
    int capacity = -1;
    std::cout << "size: " << vec.size() << " capacity: " << vec.capacity() << std::endl;

    for (int i = 0; i < 500; i++)
    {
        vec.push_back(i);
        if (capacity != vec.capacity())
        {
            std::cout << "size: " << vec.size() << " capacity: " << vec.capacity() << std::endl;
            capacity = vec.capacity();
        }
    }
    return 0;
}

Visual Studio 2022运行结果：

size: 0 capacity: 0
size: 1 capacity: 1
size: 2 capacity: 2
size: 3 capacity: 3
size: 4 capacity: 4
size: 5 capacity: 6
size: 7 capacity: 9
size: 10 capacity: 13
size: 14 capacity: 19
size: 20 capacity: 28
size: 29 capacity: 42
size: 43 capacity: 63
size: 64 capacity: 94
size: 95 capacity: 141
size: 142 capacity: 211
size: 212 capacity: 316
size: 317 capacity: 474
size: 475 capacity: 711

可以看出来，在msvc编译器中的std::vector实现每次扩容是以1.5倍的大小来扩容。

gcc 11.4运行结果：

size: 0 capacity: 0
size: 1 capacity: 1
size: 2 capacity: 2
size: 3 capacity: 4
size: 5 capacity: 8
size: 9 capacity: 16
size: 17 capacity: 32
size: 33 capacity: 64
size: 65 capacity: 128
size: 129 capacity: 256
size: 257 capacity: 512

可以看出，在gcc中是以2倍的大小来扩容的。

二、gcc源码探究

msvc的源码拿不到，gcc11.4的代码看着比较抽象，所以找了gcc2.95的版本代码来展示一下，本质上都是一样的。

push_back函数

void push_back(const _Tp& __x) {
    if (_M_finish != _M_end_of_storage) {
        construct(_M_finish, __x);
        ++_M_finish;
    }
    else
        _M_insert_aux(end(), __x);
}

当空间不足时，会执行_M_insert_aux

template <class _Tp, class _Alloc>
void 
vector<_Tp, _Alloc>::_M_insert_aux(iterator __position, const _Tp& __x)
{
  if (_M_finish != _M_end_of_storage) {
    construct(_M_finish, *(_M_finish - 1));
    ++_M_finish;
    _Tp __x_copy = __x;
    copy_backward(__position, _M_finish - 2, _M_finish - 1);
    *__position = __x_copy;
  }
  else {
    const size_type __old_size = size();
    const size_type __len = __old_size != 0 ? 2 * __old_size : 1;
    iterator __new_start = _M_allocate(__len);
    iterator __new_finish = __new_start;
    __STL_TRY {
      __new_finish = uninitialized_copy(_M_start, __position, __new_start);
      construct(__new_finish, __x);
      ++__new_finish;
      __new_finish = uninitialized_copy(__position, _M_finish, __new_finish);
    }
    __STL_UNWIND((destroy(__new_start,__new_finish), 
                  _M_deallocate(__new_start,__len)));
    destroy(begin(), end());
    _M_deallocate(_M_start, _M_end_of_storage - _M_start);
    _M_start = __new_start;
    _M_finish = __new_finish;
    _M_end_of_storage = __new_start + __len;
  }
}

三、如何避免std::vector动态扩容的性能损耗

从gcc源码中，我们可以了解到，std::vector每当空间不足时，就需要进行扩容，扩容是以原空间大小的2倍来进行扩容的，然后将之前的数据拷贝到新的内存空间，并将之前的内存空间释放掉。其实频繁执行这个过程是会对性能有损耗的，并且会造成内存的碎片化。

那么我们在使用std::vector时如何避免这种对性能和内存的不良影响呢？

可以通过以下几种方式来减少性能损耗和内存碎片化的问题：

• 预留空间：通过reserve方法来预先分配足够的空间，这样可以避免多次扩容操作。

std::vector<int> vec;
vec.reserve(100);

• 初始化时指定大小：在定义 vector 时直接指定初始大小，可以减少后续插入元素时的扩容次数。

std::vector<int> vec(100); // 创建一个初始大小为100的vector

四、emplace_back

很多同学可能对push_back比较了解，而对emplace_back不太了解。

总的来说就是，我们在push_back的是对象时，push_back是函数，传入的参数是形参，函数调用时就会执行一次拷贝构造函数，然后在vector内部又会执行一次移动构造函数。

而emplace_back就可以节省一下构造的过程。

#include <iostream>
#include <vector>

class MyClass {
public:
    MyClass(int id) : id_(id) {
        std::cout << "Constructing MyClass with ID " << id_ << std::endl;
    }

    MyClass(const MyClass& other) : id_(other.id_) {
        std::cout << "Copy constructing MyClass with ID " << id_ << std::endl;
    }

    MyClass(MyClass&& other) noexcept : id_(other.id_) {
        std::cout << "Move constructing MyClass with ID " << id_ << std::endl;
    }

    ~MyClass() {
        std::cout << "Destructing MyClass with ID " << id_ << std::endl;
    }

private:
    int id_;
};

int main() {
    std::vector<MyClass> vec;

    MyClass obj1(1);
    vec.push_back(obj1);

    vec.emplace_back(2);

    return 0;
}

运行结果：

Constructing MyClass with ID 1
Copy constructing MyClass with ID 1
Constructing MyClass with ID 2
Move constructing MyClass with ID 1
Destructing MyClass with ID 1
Destructing MyClass with ID 1
Destructing MyClass with ID 1
Destructing MyClass with ID 2

这个运行结果一目了然。

所以emplace_back也是一种优化的方式。

五、C语言实现动态数组示例

我们在C语言中是没有动态数组的，那么如何实现一个C语言的动态数组呢？

可以通过零长度数组和指针两种方式来实现，下面以零长度数组为例来实现一个动态数组。

5.1 零长度数组

int a[0];

零长度数组是不占用内存存储空间的。

#include <stdio.h>
typedef struct {    
    int size;    
    char str[];
} Str;

int main()
{    
    int a[0];    
    int b[5];    
    printf("sizeof(a): %d\n", sizeof(a));    
    printf("sizeof(b): %d\n", sizeof(b));    
    printf("sizeof(Str): %d\n", sizeof(Str));    
    return 0;
}

运行结果：

sizeof(a): 0
sizeof(b): 20
sizeof(Str): 4

5.2 利用零长度数组实现动态数组

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// 动态数组结构体
typedef struct
{
    int capacity; // 数组容量
    int count;    // 当前元素数量
    int data[];   // 零长度数组
} DynamicArray;

// 初始化动态数组
DynamicArray *init_dynamic_array(int initial_capacity)
{
    // 为结构体和元素分配足够的内存
    DynamicArray *array = (DynamicArray *)malloc(sizeof(DynamicArray) + initial_capacity * sizeof(int));
    if (array)
    {
        array->capacity = initial_capacity;
        array->count = 0;
    }
    return array;
}

// 增加数组容量
DynamicArray *ensure_capacity(DynamicArray *array, int min_capacity)
{
    if (min_capacity > array->capacity)
    {
        int new_capacity = (array->capacity * 3) / 2 + 1; // 新容量至少增加50%
        if (new_capacity < min_capacity)
        {
            new_capacity = min_capacity;
        }
        // 重新分配内存以适应新的大小
        DynamicArray *new_array = (DynamicArray *)realloc(array, sizeof(DynamicArray) + new_capacity * sizeof(int));
        if (new_array)
        {
            new_array->capacity = new_capacity;
            return new_array;
        }
    }
    return array; // 如果不需要扩容，返回原数组
}

// 向动态数组中添加元素
void append(DynamicArray **array, int element)
{
    // 先确保有足够的容量
    *array = ensure_capacity(*array, (*array)->count + 1);
    // 添加元素
    (*array)->data[(*array)->count] = element;
    (*array)->count++;
}

// 打印动态数组的内容
void print_array(const DynamicArray *array)
{
    for (int i = 0; i < array->count; ++i)
    {
        printf("%d ", array->data[i]);
    }
    printf("\n");
}

// 销毁动态数组
void destroy_dynamic_array(DynamicArray *array)
{
    free(array);
}

int main()
{
    int initial_capacity = 5;
    printf("sizeof DynamicArray: %ld\n", sizeof(DynamicArray));
    DynamicArray *array = init_dynamic_array(initial_capacity); // 初始容量为5

    // 添加一些元素
    for (int i = 0; i < 10; ++i)
    {
        append(&array, i);
    }

    // 打印动态数组
    print_array(array);

    // 销毁动态数组
    destroy_dynamic_array(array);

    return 0;
}

运行结果：

sizeof DynamicArray: 8
0 1 2 3 4 5 6 7 8 9 

六、实现泛型的C语言动态数组

C++语言是有泛型功能的，而且std::vector是支持泛型的。

而我们上面实现的C语言的动态数组，只是一个整型的动态数组，如果要用在浮点数或其他类型上，还是重新写一个新的。

那么如何实现一个泛型的C语言动态数组呢？

6.1 C语言中的泛型

在 C 语言中，虽然没有真正意义上的泛型编程，但 C11 标准中的 _Generic 关键字提供了一种在编译时根据赋值表达式的类型在泛型关联表中选择一个表达式的方法。这样可以将一组功能相同但类型不同的函数抽象为一个统一的接口。

6.2 _Generic 的语法形式

_Generic 关键字的基本语法如下：

_Generic ( assignment-expression , generic-assoc-list )

其中： - assignment-expression：赋值表达式，可以认为是变量 var。 - generic-assoc-list：泛型关联表，其语法为： c type-name : expression, type-name : expression, ..., default : expression

6.3 示例： getTypeName 函数

假设我们想要实现一个 getTypeName 函数，该函数返回变量 var 的类型名称。可以这样写：

#define GET_TYPENAME(var) _Generic((var), \
    int: "int", \
    char: "char", \
    float: "float", \
    double: "double", \
    char*: "char *", \
    default: "other type")

int main(int argc, char const *argv[]) {
    int x;
    int* x1;
    char s[10];

    printf("type: x = %s\n", GET_TYPENAME(x));
    printf("type: x1 = %s\n", GET_TYPENAME(x1));
    printf("type: s = %s\n", GET_TYPENAME(s));

    return 0;
}

运行结果：

type: x = int
type: x1 = other type
type: s = char *

6.4 泛型C语言动态数组

接下来我们就通过泛型来改造上面实现的C语言动态数组。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// 泛型动态数组结构体
typedef struct {
    int capacity;        // 数组容量
    int count;           // 当前元素数量
    size_t elem_size;    // 元素大小
    int (*data)[0];      // 零长度数组
} GenericDynamicArray;

// 初始化泛型动态数组
GenericDynamicArray* init_generic_dynamic_array(int initial_capacity, size_t elem_size) {
    // 为结构体和元素分配足够的内存
    GenericDynamicArray* array = (GenericDynamicArray*)malloc(sizeof(GenericDynamicArray) + initial_capacity * elem_size);
    if (array) {
        array->capacity = initial_capacity;
        array->count = 0;
        array->elem_size = elem_size;
        array->data = (int(*)[0])(((char*)array) + sizeof(GenericDynamicArray)); // 计算数据起始地址
    }
    return array;
}

// 增加泛型动态数组容量
void ensure_capacity(GenericDynamicArray *array, size_t min_capacity) {
    if (min_capacity > array->capacity) {
        size_t new_capacity = (array->capacity * 3) / 2 + 1;
        if (new_capacity < min_capacity) {
            new_capacity = min_capacity;
        }
        array = realloc(array, sizeof(GenericDynamicArray) + new_capacity * array->elem_size);
        array->capacity = new_capacity;
    }
}

// 向泛型动态数组中添加元素
#define append(array, element) _Generic((element), \
    int: append_int, \
    float: append_float, \
    char: append_char \
    )(array, element)


// 特化版本的 append 函数
void append_int(GenericDynamicArray *array, int element) {
    ensure_capacity(array, array->count + 1);
    ((int *)array->data)[array->count] = element;
    array->count++;
}

void append_float(GenericDynamicArray *array, float element) {
    ensure_capacity(array, array->count + 1);
    ((float *)array->data)[array->count] = element;
    array->count++;
}

void append_char(GenericDynamicArray *array, char element) {
    ensure_capacity(array, array->count + 1);
    ((char *)array->data)[array->count] = element;
    array->count++;
}

// 打印泛型动态数组的内容
void print_array(const GenericDynamicArray* array, void (*print)(const void *)) {
    for (int i = 0; i < array->count; ++i) {
        print((char*)array->data + i * array->elem_size);
    }
    printf("\n");
}

// 泛型打印函数
void generic_print_int(const void *data) {
    printf("%d ", *(int *)data);
}

void generic_print_long(const void *data) {
    printf("%ld ", *(long *)data);
}

void generic_print_double(const void *data) {
    printf("%f ", *(double *)data);
}

void generic_print_char(const void *data) {
    printf("%c ", *(char *)data);
}

void generic_print_void(const void *data) {
    printf("%p ", data);
}

int main() {
    int initial_capacity = 5;
    printf("sizeof GenericDynamicArray: %ld\n", sizeof(GenericDynamicArray));

    GenericDynamicArray* array_int = init_generic_dynamic_array(initial_capacity, sizeof(int)); // 初始容量为5

    // 添加一些整数元素
    int int_data[] = {1, 2, 3, 4, 5, 6, 7 , 8, 9};
    for (int i = 0; i < sizeof(int_data) / sizeof(int); ++i) {
        append(array_int, int_data[i]);
    }

    // 打印动态数组
    print_array(array_int, generic_print_int);

    // 销毁动态数组
    free(array_int);

    GenericDynamicArray* array_char = init_generic_dynamic_array(initial_capacity, sizeof(char)); // 初始容量为5

    char char_data[] = { 'a', 'b', 'c', 'd', 'e', 'f', 'g'};
    for (int i = 0; i < sizeof(char_data) / sizeof(char); ++i) {
        append(array_char, char_data[i]);
    }

    print_array(array_char, generic_print_char);

    free(array_char);

    return 0;
}

在这个示例中，我实现了泛型的append方法，但是对于print_array方法我却用的是回调。那么，是否可以通过_Generic实现print_array方法呢？如果可以，熟优熟劣呢？

可以看到，gcc中，当内存空间不足时，会申请一块原空间大小2倍的空间，然后讲原来的内容copy到新的内存空间中，并释放原来的内存。