C++中vector的基本用法介绍

# 1. C++中vector容器的简介**

vector容器是C++标准库中一种动态数组，用于存储同类型元素的集合。它提供了一种高效且灵活的方式来管理动态变化的数据。vector容器具有以下特点：

- **动态大小：**vector容器的大小可以动态增长和缩减，无需手动分配或释放内存。
- **连续存储：**vector容器中的元素在内存中连续存储，这使得对元素的访问和修改非常高效。
- **随机访问：**vector容器支持通过索引快速访问任何元素，时间复杂度为O(1)。
- **自动内存管理：**vector容器负责管理其内部内存，无需手动释放已释放的内存。

# 2. vector容器的底层实现

### 2.1 vector容器的内存管理

#### 2.1.1 内存分配和释放机制

vector容器内部使用连续的内存块来存储元素，以保证元素在内存中紧密相邻，提高访问效率。当需要分配新的内存时，vector会通过调用系统提供的内存分配函数（如`malloc`）来分配一块新的内存块，并将该内存块添加到容器的内部内存管理链表中。

当需要释放内存时，vector会通过调用系统提供的内存释放函数（如`free`）来释放不再使用的内存块，并将其从内部内存管理链表中移除。

#### 2.1.2 容量和大小的动态调整

vector容器的容量是指容器可以容纳的最大元素数量，而大小是指容器中实际存储的元素数量。当容器中元素数量达到容量时，vector会自动扩充容量，以容纳更多元素。容量的扩充通常是通过分配一块新的、更大的内存块，并将原有元素复制到新的内存块中进行。

当容器中元素数量减少时，vector不会立即缩减容量。只有当容器的大小小于容量的一半时，vector才会考虑缩减容量，以释放不再使用的内存空间。容量的缩减同样是通过分配一块新的、更小的内存块，并将原有元素复制到新的内存块中进行。

### 2.2 vector容器的迭代器

#### 2.2.1 迭代器的类型和用法

vector容器提供了两种类型的迭代器：

- **输入迭代器**：只能单向向前遍历容器中的元素，不能修改元素的值。
- **双向迭代器**：可以双向遍历容器中的元素，也可以修改元素的值。

迭代器本质上是一个指向容器中元素的指针，它可以指向容器中的任何元素。通过使用迭代器，可以方便地遍历容器中的所有元素，并对元素进行操作。

#### 2.2.2 遍历vector容器中的元素

遍历vector容器中的元素可以使用以下代码：

#include <vector>

int main() {
  std::vector<int> v = {1, 2, 3, 4, 5};

  // 使用输入迭代器遍历容器中的元素
  for (std::vector<int>::iterator it = v.begin(); it != v.end(); ++it) {
    std::cout << *it << " ";  // 输出元素的值
  }

  std::cout << std::endl;

  // 使用双向迭代器遍历容器中的元素
  for (std::vector<int>::reverse_iterator it = v.rbegin(); it != v.rend(); ++it) {
    std::cout << *it << " ";  // 输出元素的值
  }

  std::cout << std::endl;

  return 0;
}

**代码逻辑分析：**

- 第一个`for`循环使用输入迭代器`it`遍历容器中的元素，从容器的第一个元素开始，依次访问每个元素，并输出元素的值。
- 第二个`for`循环使用双向迭代器`it`遍历容器中的元素，从容器的最后一个元素开始，依次访问每个元素，并输出元素的值。

**参数说明：**

- `v.begin()`：返回指向容器第一个元素的输入迭代器。
- `v.end()`：返回指向容器最后一个元素的下一个位置的输入迭代器。
- `v.rbegin()`：返回指向容器最后一个元素的双向迭代器。
- `v.rend()`：返回指向容器第一个元素的下一个位置的双向迭代器。

# 3. vector容器的操作

### 3.1 vector容器的元素访问和修改

#### 3.1.1 元素的获取和设置

vector容器提供了两种方式来获取和设置元素：下标访问和迭代器访问。

**下标访问**

下标访问是最直接的方式，通过下标索引来获取或设置元素。例如：

vector<int> v = {1, 2, 3, 4, 5};

// 获取元素
int element = v[2]; // element = 3

// 设置元素
v[2] = 10; // v = {1, 2, 10, 4, 5}

**迭代器访问**

迭代器访问提供了更灵活的方式来遍历和修改元素。可以使用begin()和end()函数获取迭代器，然后使用++和--操作符遍历元素。例如：

vector<int> v = {1, 2, 3, 4, 5};

// 获取迭代器
vector<int>::iterator it = v.begin();

// 遍历元素
while (it != v.end()) {
  *it += 1; // 修改元素
  it++;
}

// v = {2, 3, 4, 5, 6}

#### 3.1.2 元素的插入和删除

vector容器提供了多种方法来插入和删除元素：

**插入元素**

* **push_back(value)**：在容器末尾添加一个元素。
* **insert(it, value)**：在迭代器it之前插入一个元素。
* **emplace_back(args...)**：在容器末尾构造一个元素。

**删除元素**

* **pop_back()**：删除容器末尾的元素。
* **erase(it)**：删除迭代器it指向的元素。
* **clear()**：删除容器中所有元素。

### 3.2 vector容器的容量和大小管理

#### 3.2.1 容量的扩充和缩减

vector容器的容量是指容器可以容纳的元素数量。当容器中的元素数量超过容量时，容器会自动扩充容量。容量的扩充通常是成倍进行的，例如，如果容量为10，扩充后容量变为20。

当容器中的元素数量减少时，容器不会自动缩减容量。可以使用reserve()函数显式指定容量，这样可以避免不必要的容量扩充。例如：

vector<int> v;
v.reserve(100); // 指定容量为100

#### 3.2.2 大小的获取和设置

vector容器的大小是指容器中实际存储的元素数量。可以通过size()函数获取容器的大小，也可以使用resize()函数修改容器的大小。例如：

vector<int> v = {1, 2, 3, 4, 5};

// 获取大小
int size = v.size(); // size = 5

// 修改大小
v.resize(10); // v = {1, 2, 3, 4, 5, 0, 0, 0, 0, 0}

# 4. vector容器的常见算法

### 4.1 vector容器的排序算法

**原理和实现**

vector容器提供了一系列排序算法，用于对容器中的元素进行排序。这些算法基于不同的排序原理，包括：

- **std::sort()：**使用快速排序算法，时间复杂度为O(n log n)。
- **std::stable_sort()：**使用归并排序算法，时间复杂度为O(n log n)，并保证元素的相对顺序不变。
- **std::partial_sort()：**对容器中的部分元素进行排序，时间复杂度为O(n log k)，其中k是排序元素的数量。
- **std::nth_element()：**找到容器中第n个最大的元素，时间复杂度为O(n)。

**代码示例：**

#include <vector>
#include <algorithm>

int main() {
    std::vector<int> v = {5, 2, 7, 1, 3};

    // 使用快速排序算法对v进行升序排序
    std::sort(v.begin(), v.end());

    // 使用归并排序算法对v进行降序排序
    std::stable_sort(v.rbegin(), v.rend());

    // 对v的前三个元素进行排序
    std::partial_sort(v.begin(), v.begin() + 3, v.end());

    // 找到v中第3个最大的元素
    std::nth_element(v.begin(), v.begin() + 2, v.end());

    return 0;
}

**复杂度分析**

vector容器的排序算法的复杂度与容器的大小和排序算法的类型有关。下表总结了不同排序算法的复杂度：

| 算法 | 时间复杂度 |
|---|---|
| std::sort() | O(n log n) |
| std::stable_sort() | O(n log n) |
| std::partial_sort() | O(n log k) |
| std::nth_element() | O(n) |

### 4.2 vector容器的查找算法

**原理和实现**

vector容器还提供了多种查找算法，用于在容器中查找特定元素。这些算法基于不同的查找原理，包括：

- **std::find()：**线性搜索算法，从容器的开头开始逐个比较元素，直到找到目标元素。
- **std::binary_search()：**二分查找算法，适用于已排序的容器，通过不断缩小搜索范围来查找目标元素。
- **std::lower_bound()：**查找第一个大于或等于目标元素的元素，适用于已排序的容器。
- **std::upper_bound()：**查找第一个大于目标元素的元素，适用于已排序的容器。

**代码示例：**

#include <vector>
#include <algorithm>

int main() {
    std::vector<int> v = {5, 2, 7, 1, 3};

    // 使用线性搜索算法查找元素5
    auto it = std::find(v.begin(), v.end(), 5);

    // 使用二分查找算法查找元素7（容器必须已排序）
    auto it = std::binary_search(v.begin(), v.end(), 7);

    // 使用lower_bound查找第一个大于或等于元素3的元素
    auto it = std::lower_bound(v.begin(), v.end(), 3);

    // 使用upper_bound查找第一个大于元素2的元素
    auto it = std::upper_bound(v.begin(), v.end(), 2);

    return 0;
}

**复杂度分析**

vector容器的查找算法的复杂度与容器的大小和查找算法的类型有关。下表总结了不同查找算法的复杂度：

| 算法 | 时间复杂度 |
|---|---|
| std::find() | O(n) |
| std::binary_search() | O(log n) |
| std::lower_bound() | O(log n) |
| std::upper_bound() | O(log n) |

# 5. vector容器的应用场景

vector容器在C++中有着广泛的应用场景，它可以用于数据存储、算法实现等多个方面。本章节将重点介绍vector容器在这些场景中的应用，帮助读者更深入地理解和使用vector容器。

### 5.1 vector容器在数据存储中的应用

#### 5.1.1 存储动态变化的数据

vector容器的一个重要应用场景是存储动态变化的数据。由于vector容器可以动态调整其容量和大小，因此非常适合存储随着程序运行而不断变化的数据。例如，在处理用户输入或从文件中读取数据时，可以使用vector容器来存储这些数据，并随着数据的增加或减少而动态调整容器的大小。

#### 5.1.2 实现队列和栈等数据结构

vector容器还可以用来实现队列和栈等数据结构。队列是一种先进先出（FIFO）的数据结构，而栈是一种后进先出（LIFO）的数据结构。通过利用vector容器的插入和删除操作，可以轻松地实现队列和栈的功能。

### 5.2 vector容器在算法实现中的应用

#### 5.2.1 算法中数据的存储和处理

在算法实现中，vector容器经常被用来存储和处理数据。例如，在排序算法中，vector容器可以用来存储待排序的数据，并在排序过程中对数据进行操作。在搜索算法中，vector容器可以用来存储待搜索的数据，并通过遍历容器中的元素来查找目标元素。

#### 5.2.2 算法中动态数组的实现

vector容器还可以用来实现算法中的动态数组。动态数组是一种可以动态调整其大小的数组，非常适合处理数据量不确定的情况。通过使用vector容器，可以轻松地实现动态数组的功能，并避免手动管理内存的复杂性。

### 代码示例

**存储动态变化的数据**

#include <vector>

int main() {
  // 创建一个vector容器
  std::vector<int> numbers;

  // 动态添加数据
  numbers.push_back(1);
  numbers.push_back(2);
  numbers.push_back(3);

  // 动态删除数据
  numbers.pop_back();

  // 遍历容器中的元素
  for (int number : numbers) {
    std::cout << number << " ";
  }

  return 0;
}

**实现队列**

#include <vector>

class Queue {
 public:
  void enqueue(int data) {
    // 将数据添加到vector容器的末尾
    queue_.push_back(data);
  }

  int dequeue() {
    // 从vector容器的开头删除并返回数据
    int data = queue_.front();
    queue_.erase(queue_.begin());
    return data;
  }

 private:
  std::vector<int> queue_;
};

**实现动态数组**

#include <vector>

class DynamicArray {
 public:
  DynamicArray() : data_(std::vector<int>()) {}

  void add(int data) {
    // 将数据添加到vector容器的末尾
    data_.push_back(data);
  }

  int get(int index) {
    // 从vector容器中获取指定索引的数据
    return data_[index];
  }

  void remove(int index) {
    // 从vector容器中删除指定索引的数据
    data_.erase(data_.begin() + index);
  }

 private:
  std::vector<int> data_;
};

# 6. vector容器的注意事项

### 6.1 vector容器的内存管理注意事项

#### 6.1.1 避免内存泄漏

vector容器在动态分配内存时，如果不再使用该容器，需要及时释放其占用的内存，以避免内存泄漏。释放内存的操作可以通过调用`clear()`方法或`delete`操作符来完成。

// 使用clear()方法释放内存
vector<int> v;
v.push_back(1);
v.push_back(2);
v.clear(); // 释放内存

// 使用delete操作符释放内存
vector<int> *v = new vector<int>;
v->push_back(1);
v->push_back(2);
delete v; // 释放内存

#### 6.1.2 优化内存使用效率

vector容器在容量扩充时会重新分配一块更大的内存空间，这可能会导致内存碎片化。为了优化内存使用效率，可以在插入元素之前预留足够的空间。预留空间可以通过`reserve()`方法来完成。

vector<int> v;
v.reserve(100); // 预留100个元素的空间
for (int i = 0; i < 100; i++) {
  v.push_back(i);
}

### 6.2 vector容器的迭代器注意事项

#### 6.2.1 迭代器失效的处理

vector容器在容量扩充时，会重新分配一块更大的内存空间，导致原有的迭代器失效。因此，在容量扩充之后，需要重新获取迭代器。

vector<int> v;
v.push_back(1);
v.push_back(2);
vector<int>::iterator it = v.begin(); // 获取迭代器
v.push_back(3); // 容量扩充
it = v.begin(); // 重新获取迭代器

#### 6.2.2 同时使用多个迭代器

当同时使用多个迭代器遍历vector容器时，需要格外小心。因为其中一个迭代器进行元素插入或删除操作后，其他迭代器可能会失效。

vector<int> v;
v.push_back(1);
v.push_back(2);
vector<int>::iterator it1 = v.begin();
vector<int>::iterator it2 = v.begin();
it1++; // 移动it1
it2 = v.erase(it2); // 删除元素

在上面的代码中，删除元素后，`it2`迭代器失效，而`it1`迭代器仍然有效。