STL之vector篇（上）还在为学习vector而感到烦恼吗？每次做算法题都要回忆很久，不如来看看我的文章，精简又易懂，帮你快速掌握vector的相关用法

1. vector的介绍

std::vector是C++标准模板库（STL）中的一个非常重要和常用的容器。它提供了一种动态数组的功能，即可以在运行时根据需要自动调整其大小以存储元素。与普通的C数组相比，std::vector提供了更多的灵活性和安全性。

1.1 基本特性

• 动态大小：std::vector能够根据需要自动增长或缩小其存储空间，以存储更多的元素或释放不再需要的内存。
• 随机访问：支持通过索引（下标）直接访问任意位置的元素，时间复杂度为O(1)。
• 连续存储：在物理内存中，std::vector的元素是连续存储的，这意味着它可以像普通数组一样被高效地遍历和访问。
• 类型安全：std::vector是模板类，可以在声明时指定存储元素的类型，从而保证了类型安全。

1.2 主要操作

• 构造函数：用于创建std::vector对象，可以指定初始大小、初始值或从一个已有的范围（如另一个vector、数组等）初始化。
• 赋值操作：可以将一个std::vector的内容赋值给另一个同类型的vector。
• 迭代器：提供了正向迭代器和反向迭代器，用于遍历vector中的元素。
• 容量和大小：可以查询vector的当前大小（即存储的元素数量）和容量（即当前分配的存储空间大小）。还可以请求减少容量以匹配实际大小（shrink_to_fit），但这不是强制性的。
• 访问元素：可以通过索引（下标）或成员函数（如at、front、back）访问vector中的元素。注意，使用索引访问时要确保索引在有效范围内，否则可能导致未定义行为；而at成员函数在索引越界时会抛出异常。
• 修改容器：支持在vector的末尾添加或移除元素（push_back、pop_back），在指定位置插入或移除元素（insert、erase），以及通过resize改变vector的大小。
• 其他操作：如交换两个vector的内容（swap），清空vector（clear）等。

1.3 注意事项

• 当vector需要增加其存储空间以存储更多元素时，它通常会分配一个更大的连续内存块，并将旧元素复制到新位置。这个过程可能会导致迭代器、指针和引用失效，因为它们可能指向了旧的内存位置。然而，vector提供的end()迭代器在重新分配后仍然是有效的，尽管它不再指向任何元素。
• 访问vector的元素时要确保索引在有效范围内，否则可能会导致未定义行为。使用at成员函数可以避免这个问题，但会牺牲一些性能。
• 在某些情况下，如果知道vector的大致大小或最大大小，可以在创建时预留足够的空间（使用reserve成员函数），以减少重新分配的次数，从而提高性能。

总的来说，std::vector是C++中非常强大和灵活的容器之一，它结合了数组的高效访问和动态数组的动态大小调整能力，是处理动态数据集合时的首选容器之一。

2. vector的使用

vector（向量）是C++标准模板库（STL）中常用的动态数组容器之一，提供了丰富的接口来管理元素集合。以下是vector的一些常用接口介绍：

2.1 构造函数

• vector<T>()：创建一个空的vector。
• vector<T>(size_type count, const T& value)：创建包含count个值为value的元素的vector。
• vector<T>(const vector<T>& other)：复制另一个vector。
• vector<T>(initializer_list<T> init)：使用初始化列表创建vector。
• vector<T>(InputIt first, InputIt last)：创建一个vector，其元素由范围[first, last)内的元素初始化。

#include <vector>  
#include <iostream>  
  
int main() {  
    // 创建一个空的vector  
    std::vector<int> emptyVec;  
  
    // 创建一个包含5个0的vector  
    std::vector<int> vec5(5, 0);  
  
    // 使用初始化列表创建vector  
    std::vector<int> initListVec = {1, 2, 3, 4, 5};  
  
    // 复制构造函数  
    std::vector<int> copyVec(vec5);  
  
    // 迭代器范围构造函数  
    std::vector<int> rangeVec(initListVec.begin(), initListVec.end());  
  
    // 打印复制和范围构造的vector，以验证它们的内容  
    for (int n : copyVec) {  
        std::cout << n << " ";  
    }  
    std::cout << "\n";  
  
    for (int n : rangeVec) {  
        std::cout << n << " ";  
    }  
    std::cout << std::endl;  
  
    return 0;  
}

2.2 赋值操作

• operator=：将一个vector赋值给另一个vector。
• assign(InputIt first, InputIt last)：用范围[first, last)内的元素替换当前vector的内容。
• assign(size_type count, const T& value)：用count个值为value的元素替换当前vector的内容。

#include <vector>  
#include <iostream>  
  
int main() {  
    std::vector<int> vec1 = {1, 2, 3};  
    std::vector<int> vec2;  
  
    // 赋值操作  
    vec2 = vec1;  
  
    // 使用assign  
    vec2.assign(3, 42); // vec2现在包含3个42  
  
    // 打印vec2以验证赋值和assign操作  
    for (int n : vec2) {  
        std::cout << n << " ";  
    }  
    std::cout << std::endl;  
  
    return 0;  
}

2.3 迭代器

• begin()：返回指向第一个元素的迭代器。
• end()：返回指向最后一个元素后面的位置的迭代器。
• rbegin()、rend()：分别返回指向最后一个元素和第一个元素前面的位置的逆向迭代器。
• cbegin()、cend()：与begin()、end()类似，但返回的是const迭代器，即不能通过这些迭代器修改vector中的元素。

#include <vector>  
#include <iostream>  
  
int main() {  
    std::vector<int> vec = {10, 20, 30, 40, 50};  
  
    // 使用迭代器遍历vector  
    for (std::vector<int>::iterator it = vec.begin(); it != vec.end(); ++it) {  
        std::cout << *it << " ";  
    }  
    std::cout << "\n";  
  
    // 使用反向迭代器  
    for (std::vector<int>::reverse_iterator rit = vec.rbegin(); rit != vec.rend(); ++rit) {  
        std::cout << *rit << " ";  
    }  
    std::cout << std::endl;  
  
    return 0;  
}

2.4 容量和大小

• size()：返回vector中的元素数量。
• max_size()：返回vector可以容纳的最大元素数量（这是一个理论上的上限，实际使用中很少会达到）。
• capacity()：返回vector当前分配的存储容量。
• empty()：如果vector为空，则返回true，否则返回false。
• reserve(size_type new_cap)：请求vector容器的存储空间至少足够容纳new_cap个元素。这有助于减少重新分配的次数，提高性能。
• shrink_to_fit()：将vector的capacity缩小为与其size相等，但这只是一个请求，编译器可能会忽略它。

#include <vector>  
#include <iostream>  
  
int main() {  
    std::vector<int> vec;  
  
    // 添加元素以改变容量和大小  
    vec.push_back(1);  
    vec.push_back(2);  
  
    std::cout << "Size: " << vec.size() << ", Capacity: " << vec.capacity() << std::endl;  
  
    // reserve更多容量  
    vec.reserve(10);  
    std::cout << "Reserved capacity: " << vec.capacity() << std::endl;  
  
    // shrink_to_fit（注意：这可能不会总是减少容量）  
    vec.shrink_to_fit();  
    // 注意：shrink_to_fit后容量可能不变，因为它是一个请求  
    std::cout << "Shrunk capacity (may not be reduced): " << vec.capacity() << std::endl;  
  
    return 0;  
}

2.5 访问元素

• operator[]：通过下标访问指定位置的元素（不进行范围检查）。
• at(size_type pos)：访问指定位置的元素，并进行范围检查。如果位置超出范围，将抛出std::out_of_range异常。
• front()：返回第一个元素的引用。
• back()：返回最后一个元素的引用。
• data()：返回指向底层数据的指针（以T*类型）。

#include <vector>  
#include <iostream>  
  
int main() {  
    std::vector<int> vec = {10, 20, 30, 40, 50};  
  
    // 访问元素  
    std::cout << "First element: " << vec[0] << std::endl;  
    std::cout << "Last element: " << vec.back() << std::endl;  
  
    try {  
        // 尝试访问超出范围的元素（使用at会抛出异常）  
        std::cout << "Out of range element: " << vec.at(10) << std::endl;  
    } catch (const std::out_of_range& e) {  
        std::cout << "Caught exception: " << e.what() << std::endl;  
    }  
  
    return 0;  
}

2.6 修改容器

• push_back(const T& value)：将元素添加到vector的末尾。
• pop_back()：移除vector的最后一个元素。
• emplace_back(Args&&... args)：在vector的末尾就地构造一个元素，避免了额外的拷贝或移动操作。
• insert(iterator pos, const T& value)：在指定位置插入元素。
• erase(iterator pos)：移除指定位置的元素。
• erase(iterator first, iterator last)：移除范围[first, last)内的元素。
• clear()：移除所有元素，但不改变capacity。
• resize(size_type count)：改变vector的大小，如果新大小大于当前大小，则新元素将被默认构造；如果新大小小于当前大小，则超出的元素将被销毁。
• resize(size_type count, const T& value)：改变vector的大小，并用value值初始化新的元素。

#include <vector>  
#include <iostream>  
  
int main() {  
    std::vector<int> vec = {1, 2, 3, 4, 5};  
  
    // 修改容器  
    vec.push_back(6); // 在末尾添加元素  
    vec.pop_back(); // 移除末尾元素  
    vec.insert(vec.begin(), 0); // 在开头插入元素  
    vec.erase(vec.begin() + 2); // 移除指定位置的元素  
  
    // 使用resize  
    vec.resize(3); // 缩小vector的大小，超出部分的元素被销毁  
    vec.resize(5, 10); // 扩大vector的大小，新元素初始化为10  
  
    // 打印修改后的vector  
    for (int n : vec) {  
        std::cout << n << " ";  
    }  
    std::cout << std::endl;  
  
    return 0;  
}

2.7 其他操作

• swap(vector<T>& other)：交换两个vector的内容。

#include <vector>  
#include <iostream>  
  
int main() {  
    std::vector<int> vec1 = {1, 2, 3};  
    std::vector<int> vec2 = {4, 5, 6};  
  
    // 交换vector  
    vec1.swap(vec2);  
  
    // 打印以验证交换  
    for (int n : vec1) {  
        std::cout << n << " ";  
    }  
    std::cout << "\n";  
  
    for (int n : vec2) {  
        std::cout << n << " ";  
    }  
    std::cout << std::endl;  
  
    return 0;  
}

3. vector的迭代器失效问题

在C++中，std::vector的迭代器失效问题是一个重要的概念，它主要发生在vector的容量发生变化时。迭代器失效意味着迭代器不再指向有效的内存位置，如果此时尝试通过失效的迭代器访问或修改元素，程序的行为将是未定义的。

3.1 迭代器失效的常见情况

1. 重新分配：当vector需要增加其存储容量以存储更多元素时（通常是因为调用了push_back、insert等操作，并且当前容量不足以容纳更多元素），它可能会重新分配一个更大的内存块，并将旧元素复制到新位置。这个过程中，所有指向旧内存块的迭代器、指针和引用都会失效。
2. 删除元素：虽然删除元素（如使用erase）不会导致整个vector的重新分配，但被删除元素之后的所有迭代器、指针和引用都会失效，因为它们不再指向有效的元素。注意，erase方法会返回一个指向被删除元素之后元素的迭代器，这可以用来继续迭代。

3.2 迭代器失效的避免策略

1. 使用成员函数返回的新迭代器：在删除元素时，使用erase方法返回的迭代器继续迭代。这个迭代器指向被删除元素之后的元素，因此是有效的。
2. 预留空间：如果可能，使用reserve成员函数提前为vector预留足够的空间。这样可以减少重新分配的次数，从而降低迭代器失效的风险。但是，请注意，reserve不会改变vector的大小（即存储的元素数量），只是改变其容量。
3. 使用标准算法：当需要在vector中执行复杂的操作时（如排序、查找、删除等），考虑使用标准库提供的算法。这些算法通常设计为与迭代器一起工作，并且能够处理迭代器失效的情况（尽管在某些情况下，如排序，可能需要使用额外的缓冲区来避免迭代器失效）。
4. 避免在迭代过程中修改vector的大小：在遍历vector时，尽量避免修改其大小（除非你能确保这种修改不会导致迭代器失效，例如只在vector的末尾添加元素）。如果需要频繁地修改vector的大小，并且同时需要遍历它，考虑使用其他数据结构（如list或deque），它们在设计上更加灵活，可以容忍更多的修改而不会导致迭代器失效。

【总结】

std::vector的迭代器失效是一个需要开发者注意的问题。了解何时以及如何避免迭代器失效对于编写健壮、可维护的C++代码至关重要。通过预留空间、使用标准算法和避免在迭代过程中修改vector的大小，可以大大降低迭代器失效的风险。