数组高阶应用（C++版）

在C++中，普通的数组（C-style array）、std::initializer_list 、 std::array和std::vector 是四种不同的容器类型，它们各自有不同的特性和用途。下面是对它们进行详细比较和解释。

1. 普通数组（C-style Array）

普通数组是C++中最基本的数组类型，它在C语言中就已经存在。

特点:

• 固定大小: 数组的大小在声明时确定，不能动态调整。
• 编译时分配内存: 数组的内存通常在栈上分配。
• 不具备任何额外的功能: 普通数组没有边界检查、长度查询等功能。
• 兼容性: 与C语言完全兼容，适用于需要与C代码交互的场景。

语法:

int arr[5] = {1, 2, 3, 4, 5};

使用限制:

• 普通数组不能作为函数的返回值（因为它会退化为指针）。
• 没有内置的成员函数，比如获取大小或进行边界检查。

2. initializer_list

std::initializer_list 是C++11引入的一种轻量级容器，专门用于初始化列表。

特点:

• 只读容器: 容器中的元素是只读的，无法修改。
• 常量大小: 容器的大小在初始化时确定，不能修改。
• 语法简洁: 使用花括号 {} 可以轻松初始化 std::initializer_list。

语法:

#include <initializer_list>
#include <iostream>

void printList(std::initializer_list<int> list) {
    for (int elem : list) {
        std::cout << elem << " ";
    }
    std::cout << std::endl;
}

int main() {
    printList({1, 2, 3, 4, 5});
    return 0;
}

主要用途:

• 通常用于函数的参数，以允许使用初始化列表作为函数的输入。
• 在构造函数中使用，以支持对象的初始化列表语法。

3. array

std::array 是C++11引入的标准库容器，封装了固定大小的数组，提供了更丰富的功能。

特点:

• 固定大小: 与普通数组一样，大小在编译时确定，不能动态调整。
• 强类型安全: 提供了类型安全的接口，避免了指针退化等问题。
• 支持STL算法: 可以与标准库算法和容器互操作。
• 丰富的成员函数: 包括 size()、at()（带边界检查）等。
• 内存布局与普通数组相同: 内存布局与普通数组相同，所以开销极低。

语法:

#include <array>
#include <iostream>

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

    // 使用 at() 访问元素，带边界检查
    std::cout << "Element at index 2: " << arr.at(2) << std::endl;

    // 使用迭代器
    for (auto it = arr.begin(); it != arr.end(); ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;

    return 0;
}

优势:

• 提供了与 std::vector 类似的接口，但由于其大小是固定的，所以比 std::vector 更轻量。
• 在需要使用固定大小数组的场景下，std::array 是普通数组的更安全、更方便的替代品。

总结

• 普通数组: 基本的数组类型，大小固定，轻量但功能有限，容易出错（如数组越界）。
• std::initializer_list: 只读容器，专门用于初始化列表，常用于函数参数。
• std::array: 封装了固定大小数组，提供了强类型安全和更丰富的功能，是普通数组的更好的替代品。

4. vector

相对于前面三者，std::vector 是一种动态大小的容器，提供了更为强大的功能。它是C++标准模板库（STL）中最常用的序列容器之一。之前有写过vector的模拟实现的博客：链接

特点

1. 动态大小：std::vector 的大小是可变的，可以根据需要动态增加或减少元素。这与普通数组和 std::array 是最大的不同。

2. 自动管理内存：std::vector 会自动管理它的内存，包括分配、扩展和释放。用户不需要手动管理内存，这避免了内存泄漏等问题。

3. 提供丰富的成员函数：std::vector 提供了一系列成员函数，比如 push_back()、emplace_back()、insert()、erase() 等，使得操作更加便捷。

4. 随机访问：std::vector 支持常数时间的随机访问（operator[] 和 at()），就像普通数组一样。

5. 内存连续性：std::vector 的元素是连续存储的，这意味着它可以与传统的C-style数组进行高效的互操作，并且可以利用底层硬件的缓存机制提高性能。

6. 支持STL算法：std::vector 可以与STL中的各种算法（如 sort()、find() 等）无缝配合使用。

vector 的用法

基本用法：

#include <vector>
#include <iostream>

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

    // 添加元素
    vec.push_back(6);

    // 访问元素
    std::cout << "Element at index 2: " << vec[2] << std::endl;

    // 使用迭代器遍历
    for (auto it = vec.begin(); it != vec.end(); ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;

    // 删除元素
    vec.pop_back();

    return 0;
}

与其它容器的区别

1. 与普通数组（C-style array）相比：

   • 普通数组的大小是固定的，不能在运行时改变；而 std::vector 可以动态调整大小。
   • 普通数组不提供边界检查，容易造成越界访问；而 std::vector 提供了 at() 方法，具有边界检查。
   • 普通数组不提供丰富的成员函数，操作不如 std::vector 方便。

2. 与 std::initializer_list 相比：

   • std::initializer_list 是一个轻量级的只读容器，不能修改和扩展；而 std::vector 是一个可读写的容器，支持动态大小。
   • std::initializer_list 常用于函数参数的初始化；而 std::vector 适用于更多场景。

3. 与 std::array 相比：

   • std::array 的大小是固定的，类似于普通数组，不能在运行时改变；而 std::vector 支持动态大小。
   • std::array 的性能通常略优于 std::vector，因为它没有动态分配和管理内存的开销；而 std::vector 由于需要动态分配内存，有时会比 std::array 稍慢。

总结

• 普通数组: 固定大小，轻量但功能有限，容易出错（如数组越界）。
• std::initializer_list: 只读容器，专门用于初始化列表，常用于函数参数。
• std::array: 封装了固定大小数组，提供了更安全、更方便的替代品。
• std::vector: 动态大小容器，自动管理内存，功能丰富，是大多数情况下的首选容器。

std::vector 的灵活性和功能使它成为C++编程中最常用的容器之一，适用于需要动态大小和频繁增删元素的场景。

每种容器都有其特定的应用场景，选择时要根据具体需求来决定。

扩展：迭代器失效问题

在C++中，std::vector 是一个动态数组，随着元素的增加或删除，其底层内存可能会重新分配。当发生重新分配时，所有指向旧存储空间的迭代器、指针和引用将失效，导致可能的程序错误。这就是所谓的迭代器失效问题。

迭代器失效的情况

std::vector 中迭代器可能失效的主要情况有以下几种：

1. 插入元素时：

   • 当 std::vector 需要扩展容量时，可能会重新分配更大的内存，并将现有元素复制到新的内存位置。此时，所有旧的迭代器、指针、和引用都会失效。

   • 如果插入的位置不是 vector 的末尾，所有从插入点开始的迭代器也会失效，因为后面的元素要向后移动。

2. 删除元素时：

   • 如果删除元素，所有指向被删除元素以及它后面元素的迭代器都会失效，因为元素会被向前移动来填补删除的位置。

3. clear() 和 erase() 操作：

   • clear() 会删除所有元素，使所有迭代器失效。
   • erase() 会使指向被删除元素和它后面的元素的迭代器失效。

错误示范

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

for (auto it = v.begin(); it != v.end(); ++it) {
    if (*it % 2 == 0) {
        it = v.erase(it); 
    } 
}

erase已经返回下一个元素的位置，如果再加加可能起不到遍历的效果，甚至会访问到不属于vector的空间。

如何处理迭代器失效

要处理 std::vector 的迭代器失效问题，可以采用以下几种方法：

1. 避免在迭代时改变容器

这是最简单的策略。如果在遍历 std::vector 的时候不修改它，迭代器就不会失效。

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

for (auto it = v.begin(); it != v.end(); ++it) {
    std::cout << *it << std::endl;
}

2. 重新获取迭代器

当执行插入或删除操作时，可以重新获取迭代器。对于插入操作，插入元素后可以通过返回的新迭代器继续操作。对于删除操作，erase 返回的迭代器指向删除元素之后的下一个元素。

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

for (auto it = v.begin(); it != v.end(); /* nothing */) {
    if (*it % 2 == 0) {
        it = v.erase(it);  // erase 返回删除元素之后的迭代器
    } else {
        ++it;
    }
}

3. 预先分配足够的空间

在插入大量元素之前，可以使用 reserve() 方法提前分配足够的空间，避免频繁的内存重新分配，减少迭代器失效的机会。

std::vector<int> v;
v.reserve(1000); // 预分配空间，避免多次重新分配

for (int i = 0; i < 1000; ++i) {
    v.push_back(i); // 不会导致迭代器失效
}

4. 使用索引而不是迭代器

在遍历 std::vector 时，使用索引而不是迭代器，可以避免迭代器失效的问题。

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

for (std::size_t i = 0; i < v.size(); /* nothing */) {
    if (v[i] % 2 == 0) {
        v.erase(v.begin() + i); // 删除偶数
    } else {
        ++i;
    }
}

5. 使用双向迭代器结构的算法

有些标准库算法，如 remove_if，不会修改容器的大小，而是重排容器元素。这些算法不会导致迭代器失效。你可以结合 erase 和 remove_if 来安全地删除符合条件的元素。

std::vector<int> v = {1, 2, 3, 4, 5};
v.erase(
    std::remove_if(v.begin(), v.end(), [](int x) { return x % 2 == 0; }), 
    v.end()
);

在这里，std::remove_if 会把不符合条件的元素移动到容器的末尾，而 erase 则将那些元素实际删除。这样可以避免多次 erase 操作造成的迭代器失效。

处理方式汇总

1. 插入元素时，特别是插入到 vector 末尾时，尽量提前调用 reserve() 预分配空间。
2. 删除元素时，使用 erase 返回的迭代器或结合 remove_if 等标准库算法。
3. 遍历容器时，可以使用索引或重新获取迭代器，避免指向失效的迭代器。
4. 在多线程场景下，修改 vector 需要特别小心同步问题，可以考虑使用锁或其他并发安全容器。

如果你能看到这里，给你点个赞，如果对你有帮助的话不妨点赞支持一下~