C++ STL 容器详解：vector 原理与使用

（2）resize() 和 reserve() 的区别

resize(): 调整大小，使得容量和元素的个数相同。

int main() {
    // resize(n)——填充 n 个元素，容量也为 n
    std::vector<int> ar(5, 10);
    // 尾插后，需要进行扩容，原有的空间会被释放，重新分配内存空间
    ar.resize(10, 23); // 元素的个数和容量的大小都是 10
    // 输出结果：10 10 10 10 10 23 23 23 23 23
    cout << ar.size() << endl; // 10
    cout << ar.capacity() << endl; // 10
    for (auto& x : ar) {
        cout << x << " ";
    }
    cout << endl;
    return 0;
}

reserve(): 只分配对应数目的容量。如果提前已知需要分配的元素个数，可以使用 reserve() 函数，避免频繁扩容。

int main() {
    // reserve(n)——容量为 n，但不填充元素
    std::vector<int> ar(5, 10);
    ar.reserve(20); // 元素的个数是 5，容量的大小是 20
    cout << ar.size() << endl; // 5
    cout << ar.capacity() << endl; // 20
    // 输出结果：10 10 10 10 10
    for (auto& x : ar) {
        cout << x << " ";
    }
    cout << endl;
    return 0;
}

（3）data()

data() 函数的返回值是首元素地址，即开始指针指向的位置。

int main() {
    std::vector<int> ar = { 1, 2, 3, 4, 5 };
    int* p = ar.data(); // 返回开始指针的指向位置
    for (int i = 0; i < ar.size(); ++i) {
        std::cout << *p << std::endl; // 1 2 3 4 5
        p += 1;
    }
    return 0;
}

（4）emplace_back()

直接在 vector 尾部原位构造元素，消除临时对象的拷贝/移动开销，内部采用定位 new 实现。

int main() {
    std::vector<int> ar{ 12, 23, 45, 56 };
    ar.emplace_back(69); // 原位构造，在原地址就地构建，内部调用的是定位 new
    for (auto x : ar) {
        std::cout << x << " "; // 12 23 45 56 69
    }
    std::cout << std::endl;
    return 0;
}

（5）shrink_to_fit()

释放未使用的内存减少内存的使用，即用来回收空间。

int main() {
    std::vector<int> ar = { 12, 23, 34, 45, 56, 67, 78, 89 };
    ar.erase(ar.begin() + 2, ar.end());
    std::cout << ar.capacity() << std::endl;
    // ar.shrink_to_fit(); // 当容量与元素的个数差距太多，则可以使用该函数缩减容量
    // 底层实现：使用 swap() 函数
    // 使用块域和 swap 缩减容量
    {
        std::vector<int>(ar).swap(ar); // 解释：使用 ar 初始化不具名的对象，因为是不具名对象，根据元素的个数分配容量的大小
                                       // 使用交换函数将原本的 ar 与不具名对象交换后，原本的 ar 容量的大小与元素的个数相同
                                       // 不具名的对象在块域结束后，会被销毁。
    }
    std::cout << "ar.capacity:" << ar.capacity() << std::endl;
    return 0;
}

5. 迭代器失效

（1）扩容导致迭代器失效

当元素的个数大于等于容器容量的个数时，就会发生扩容（在 Windows 下以 2 倍进行扩容，在 Linux 下以 1.5 倍进行扩容）。当发生扩容时，会分配一块新的更大的存储区，将旧存储区的元素拷贝或者移动到新的存储区，释放旧存储区的内存，导致迭代器失效。

（2）插入/删除导致迭代器失效

（3）其他情况

1. 使用 resize() 改变 vector 大小，若新大小超过原容量（本质是扩容），迭代器失效；
2. 使用 assign() 替换 vector 内容，底层内存可能重新分配，迭代器失效；
3. 使用 swap() 交换两个 vector，原迭代器会指向交换后的 vector 对应元素（不算'失效'，但逻辑上指向的内容变了）。

（4）示例

// vector 的迭代器失效，插入或者删除都会导致迭代器的失效（因为会发生会扩容）
// 注意：释放空间时候是连续释放的，只是删除掉了元素
int main() {
    std::vector<int> ar{ 12, 23, 34, 45, 56, 67, 78, 89 };
    // std::vector<int>::iterator it = ar.begin();
    auto it = ar.begin();
    ar.insert(it, 122); // 扩容，删除掉原本的空间，但迭代器仍然还指向原本的空间
    std::cout << "插入后的元素：" << std::endl;
    for (auto x : ar) {
        std::cout << x << " ";
    }
    std::cout << std::endl;
    // it=ar.erase(it); // 程序崩溃，因为在插入过程后，迭代器已经失效，此时还在使用原本的迭代器
    std::cout << "删除后的元素：" << std::endl;
    for (it = ar.begin(); it != ar.end(); ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;
}

6. 避免迭代器失效

1. 如果已知元素的个数，则可以使用 reserve() 函数提前预留空间，避免频繁扩容导致迭代器失效。
2. vector 容器中，对于 insert() 和 erase() 函数时，使用返回值进行接收。返回值是新的有效迭代器。