vector的时空效率呢？

vector是一种动态数组，它具有良好的时空效率。

时效性：
- 插入和删除元素的时间复杂度为O(1)，因为vector的底层数组是连续存储的，可以通过索引直接访问元素。
- 在末尾插入元素的平均时间复杂度为O(1)，当vector的容量不足时，会进行扩容操作，时间复杂度为O(n)。
- 在任意位置插入或删除元素的平均时间复杂度为O(n)，因为需要移动其他元素来保持连续存储。

空间效率：
- vector的空间效率较高，因为它只需要额外的空间来存储元素本身，不需要额外的指针或链表节点。
- vector的空间复杂度为O(n)，其中n是vector中元素的数量。
- vector的空间利用率较高，因为它可以根据需要动态调整容量，避免了空间浪费。

总结起来，vector具有较好的时空效率，适用于需要频繁插入和删除元素，并且对内存占用有要求的场景。

相关问题

cpp vector如何加入元素？

向 `vector` 中加入元素可以使用 `push_back()` 函数，该函数将一个元素加入到 `vector` 的末尾，例如：

vector<int> vec;
vec.push_back(10);

以上代码将 `10` 加入到了 `vector` 的末尾。`push_back()` 函数会自动调整 `vector` 的大小以容纳新元素。如果需要加入多个元素，可以多次调用 `push_back()` 函数，例如：

vector<int> vec;
vec.push_back(10);
vec.push_back(20);
vec.push_back(30);

以上代码将 `10`、`20`、`30` 三个元素加入到了 `vector` 的末尾。

除了 `push_back()` 函数，还可以使用 `insert()` 函数将元素加入到 `vector` 的指定位置，例如：

vector<int> vec;
vec.insert(vec.begin(), 10); // 在 vector 开头加入元素 10
vec.insert(vec.end(), 20); // 在 vector 结尾加入元素 20
vec.insert(vec.begin() + 2, 30); // 在 vector 第 2 个位置后加入元素 30

以上代码分别在 `vector` 的开头、结尾和第 2 个位置后加入了元素。`insert()` 函数的第一个参数是插入位置的迭代器，第二个参数是要插入的元素。

C++ Vector 怎么扩容？

在 C 语言中，如果我们使用动态数组实现 Vector，需要考虑到扩容的问题。下面是一种实现方式：

1. 定义结构体 `vector`，包含以下成员：

typedef struct {
    int *data;
    int size;
    int capacity;
} vector;

其中，`data` 指向动态数组的首地址，`size` 表示当前数组中元素的个数，`capacity` 表示数组的容量。

2. 实现初始化函数 `init_vector`，用于初始化一个 vector：

void init_vector(vector *v) {
    v->data = (int *)malloc(sizeof(int) * INIT_CAPACITY);
    v->size = 0;
    v->capacity = INIT_CAPACITY;
}

其中，`INIT_CAPACITY` 是一个预定义的常量，表示数组的初始容量。

3. 实现添加元素函数 `push_back`，用于在数组的末尾添加一个元素：

void push_back(vector *v, int value) {
    if (v->size == v->capacity) {
        v->capacity *= 2;
        v->data = (int *)realloc(v->data, sizeof(int) * v->capacity);
    }
    v->data[v->size++] = value;
}

如果数组已满，就将容量扩大一倍，并使用 `realloc` 函数重新分配内存。然后，在数组末尾添加新的元素。

需要注意的是，`realloc` 函数可能会返回空指针，因此在使用之前需要进行判断。

4. 实现释放函数 `free_vector`，用于释放动态数组占用的内存：

void free_vector(vector *v) {
    free(v->data);
    v->size = 0;
    v->capacity = 0;
}

这样，我们就实现了一个简单的动态数组 Vector，并且实现了扩容的功能。