C++ STL 容器 vector 的容量收缩方法

C++ STL 容器 vector 的容量收缩方法

vector 容量概述

在 C++ 的 STL（标准模板库）中，vector 是一种动态数组容器，它能够根据需要自动调整大小。vector 有两个重要的属性：大小（size）和容量（capacity）。大小指的是当前 vector 中实际存储的元素个数，而容量则是 vector 在不重新分配内存的情况下最多能容纳的元素个数。

#include <iostream>
#include <vector>

int main() {
    std::vector<int> vec;
    for (int i = 0; i < 10; ++i) {
        vec.push_back(i);
    }
    std::cout << "Size: " << vec.size() << std::endl;
    std::cout << "Capacity: " << vec.capacity() << std::endl;
    return 0;
}

在上述代码中，通过 push_back 方法向 vector 中添加了 10 个元素，此时 size 为 10。而 capacity 通常会大于等于 size，具体的值取决于 vector 的内存分配策略。一般来说，vector 在分配内存时会多分配一些空间，以避免频繁的内存重新分配。

为什么需要容量收缩

1. 内存优化：当 vector 中删除了大量元素后，其容量可能仍然保持在一个较高的水平，这会导致内存的浪费。例如，一个原本存储了 10000 个元素的 vector，删除了 9900 个元素后，如果容量没有收缩，仍然占用着能够存储 10000 个元素的内存空间，而实际只需要存储 100 个元素的空间即可，此时就有大量内存被闲置。
2. 性能提升：在某些对内存使用非常敏感的应用场景，如嵌入式系统、移动应用等，过多的闲置内存会影响系统的整体性能。通过收缩容量，可以释放这些闲置内存，提高程序的运行效率。

容量收缩方法

使用 swap 技巧

1. 原理：这种方法利用了 vector 的 swap 函数。swap 函数用于交换两个 vector 的内容，包括它们的大小和容量。通过将一个临时的 vector 与目标 vector 进行交换，可以达到收缩容量的目的。具体来说，创建一个临时 vector，它的大小和容量与目标 vector 当前的大小相同，然后将两者交换，目标 vector 的容量就会被收缩到当前的大小。
2. 代码示例：

#include <iostream>
#include <vector>

void shrinkVector(std::vector<int>& vec) {
    std::vector<int>(vec).swap(vec);
}

int main() {
    std::vector<int> vec;
    for (int i = 0; i < 100; ++i) {
        vec.push_back(i);
    }
    // 删除一些元素
    for (int i = 0; i < 50; ++i) {
        vec.pop_back();
    }
    std::cout << "Before shrink, capacity: " << vec.capacity() << std::endl;
    shrinkVector(vec);
    std::cout << "After shrink, capacity: " << vec.capacity() << std::endl;
    return 0;
}

在上述代码中，shrinkVector 函数实现了容量收缩的功能。首先创建了一个临时 vector，它是通过 std::vector<int>(vec) 这种方式，以 vec 为参数进行初始化，此时临时 vector 的大小和容量都与 vec 当前的大小相同。然后通过 swap 函数将临时 vector 和 vec 进行交换，从而使得 vec 的容量收缩到当前的大小。

使用 reserve 方法

1. 原理：vector 的 reserve 函数用于请求容器至少具有容纳指定数量元素的容量。如果当前容量小于参数所指定的值，vector 会重新分配内存，以满足新的容量需求；如果当前容量大于或等于指定的值，则 reserve 函数不做任何操作。利用这一特性，我们可以将 reserve 的参数设置为当前 vector 的大小，从而达到收缩容量的目的。
2. 代码示例：

#include <iostream>
#include <vector>

void shrinkVectorWithReserve(std::vector<int>& vec) {
    vec.reserve(vec.size());
}

int main() {
    std::vector<int> vec;
    for (int i = 0; i < 100; ++i) {
        vec.push_back(i);
    }
    // 删除一些元素
    for (int i = 0; i < 50; ++i) {
        vec.pop_back();
    }
    std::cout << "Before shrink, capacity: " << vec.capacity() << std::endl;
    shrinkVectorWithReserve(vec);
    std::cout << "After shrink, capacity: " << vec.capacity() << std::endl;
    return 0;
}

在这个例子中，shrinkVectorWithReserve 函数通过调用 vec.reserve(vec.size())，请求 vector 的容量至少为当前的大小。如果当前容量大于当前大小，vector 会重新分配内存，将容量调整为当前大小，从而实现容量收缩。

C++11 及以后的 shrink_to_fit 方法

1. 原理：从 C++11 开始，vector 提供了 shrink_to_fit 成员函数。该函数请求容器减少其容量以适应其大小。然而，需要注意的是，shrink_to_fit 只是一个请求，标准库并不保证容器一定会减少容量。实现该功能的具体行为取决于标准库的实现者，不同的编译器和标准库版本可能有不同的表现。一般来说，大多数现代标准库实现会尽量满足这个请求，将容量收缩到与大小相近的值。
2. 代码示例：

#include <iostream>
#include <vector>

int main() {
    std::vector<int> vec;
    for (int i = 0; i < 100; ++i) {
        vec.push_back(i);
    }
    // 删除一些元素
    for (int i = 0; i < 50; ++i) {
        vec.pop_back();
    }
    std::cout << "Before shrink, capacity: " << vec.capacity() << std::endl;
    vec.shrink_to_fit();
    std::cout << "After shrink, capacity: " << vec.capacity() << std::endl;
    return 0;
}

在上述代码中，通过调用 vec.shrink_to_fit()，向 vector 请求收缩容量。在大多数情况下，vector 的容量会被收缩到更接近当前大小的值，但不能保证一定能收缩到与大小完全相同。

不同方法的性能比较

1. swap 技巧：这种方法相对高效，因为它只涉及一次内存交换操作。创建临时 vector 并进行交换的开销相对较小，尤其是在处理较大规模的 vector 时，能够快速有效地收缩容量。不过，它在代码可读性上可能稍逊一筹，对于不熟悉这种技巧的开发者来说，理解起来可能有一定难度。
2. reserve 方法：reserve 方法在大多数情况下也能有效地收缩容量，但它可能会涉及内存的重新分配和数据的拷贝。如果当前容量远大于目标容量，重新分配内存和拷贝数据的开销会比较大，从而影响性能。特别是在元素数量较多且元素类型较大时，这种开销会更加明显。
3. shrink_to_fit 方法：由于 shrink_to_fit 只是一个请求，其性能表现依赖于标准库的具体实现。在一些实现中，它可能会采用与 reserve 类似的方式来收缩容量，因此性能也会受到内存重新分配和数据拷贝的影响。而且由于不保证一定能收缩成功，在对容量收缩有严格要求的场景下，可能不太适用。

实际应用场景

1. 数据处理应用：在数据处理程序中，经常会遇到数据量动态变化的情况。例如，在对大量数据进行筛选、过滤等操作后，可能会删除很多元素。此时，通过收缩 vector 的容量，可以及时释放闲置内存，提高程序后续处理其他数据的效率。
2. 图形图像处理：在图形图像处理领域，内存的使用非常关键。例如，在处理图像的像素数据时，可能会使用 vector 来存储像素信息。当对图像进行裁剪、缩放等操作后，vector 中可能会有大量不再使用的像素数据对应的内存空间。通过收缩容量，可以优化内存使用，避免内存泄漏和性能下降。
3. 游戏开发：游戏中常常需要动态管理各种资源，如角色信息、场景数据等。这些数据可能会根据游戏的进程不断变化，使用 vector 存储这些数据时，适时地收缩容量可以提高游戏的运行效率，减少内存占用，特别是在移动游戏开发中，对内存的优化尤为重要。

注意事项

1. 内存重新分配：无论是使用 swap 技巧、reserve 方法还是 shrink_to_fit 方法，都可能涉及内存的重新分配。内存重新分配会带来一定的性能开销，包括内存申请、数据拷贝等操作。因此，在频繁进行容量收缩操作时，需要谨慎考虑性能问题。
2. 迭代器和引用失效：当 vector 的容量发生变化（如通过上述方法收缩容量）时，其内部的内存布局可能会改变，这会导致指向 vector 元素的迭代器、指针和引用失效。例如：

#include <iostream>
#include <vector>

int main() {
    std::vector<int> vec = {1, 2, 3, 4, 5};
    auto it = vec.begin();
    std::vector<int>(vec).swap(vec);
    // 此时 it 已经失效
    // std::cout << *it << std::endl; // 这将导致未定义行为
    return 0;
}

在上述代码中，通过 swap 技巧收缩容量后，之前获取的迭代器 it 已经失效。如果继续使用失效的迭代器，会导致程序出现未定义行为。因此，在进行容量收缩操作后，如果还需要使用迭代器、指针或引用，需要重新获取。 3. 不同标准库实现的差异：如前文所述，shrink_to_fit 方法的具体行为依赖于标准库的实现。不同的编译器和标准库版本可能对 shrink_to_fit 有不同的实现方式，甚至在同一个编译器的不同版本中也可能有所变化。因此，在编写跨平台或对容量收缩有严格要求的代码时，需要对不同的标准库实现进行测试和验证。

结合场景选择合适的方法

1. 对性能要求极高且代码可读性影响不大的场景：如果应用场景对性能要求非常高，且开发团队对代码技巧比较熟悉，可以优先选择 swap 技巧。例如，在一些底层的算法库、高性能计算模块中，这种方法能够在不引入过多复杂逻辑的情况下，快速有效地收缩 vector 的容量。
2. 对内存使用和性能有平衡需求的场景：对于大多数一般性的数据处理场景，reserve 方法是一个不错的选择。它相对容易理解和实现，并且在大多数情况下能够有效地收缩容量。虽然可能会有一定的内存重新分配开销，但在可以接受的范围内。
3. 对兼容性要求高且对容量收缩要求不绝对严格的场景：如果应用程序需要在不同的编译器和标准库版本上运行，且对容量收缩的要求不是非常严格，shrink_to_fit 方法可以作为一个简单的选择。尽管不保证一定能成功收缩容量，但在大多数现代标准库实现中，它通常能够满足基本的容量优化需求。

综合示例

以下是一个综合示例，展示了在不同场景下如何使用上述容量收缩方法：

#include <iostream>
#include <vector>
#include <algorithm>

// 使用 swap 技巧收缩容量
void shrinkBySwap(std::vector<int>& vec) {
    std::vector<int>(vec).swap(vec);
}

// 使用 reserve 方法收缩容量
void shrinkByReserve(std::vector<int>& vec) {
    vec.reserve(vec.size());
}

// 使用 shrink_to_fit 方法收缩容量
void shrinkByShrinkToFit(std::vector<int>& vec) {
    vec.shrink_to_fit();
}

// 模拟数据处理场景
void dataProcessingScenario() {
    std::vector<int> data;
    for (int i = 0; i < 10000; ++i) {
        data.push_back(i);
    }
    // 模拟数据筛选
    data.erase(std::remove_if(data.begin(), data.end(), [](int num) { return num % 2 == 0; }), data.end());
    std::cout << "Before shrink, size: " << data.size() << ", capacity: " << data.capacity() << std::endl;

    // 选择合适的收缩方法
    // shrinkBySwap(data);
    // shrinkByReserve(data);
    shrinkByShrinkToFit(data);

    std::cout << "After shrink, size: " << data.size() << ", capacity: " << data.capacity() << std::endl;
}

int main() {
    dataProcessingScenario();
    return 0;
}

在上述代码中，dataProcessingScenario 函数模拟了一个数据处理场景，首先生成了 10000 个整数并存储在 vector 中，然后通过 erase 和 remove_if 组合删除了所有偶数。之后，可以根据具体需求选择不同的容量收缩方法，这里分别注释了 swap 技巧、reserve 方法和 shrink_to_fit 方法的调用，开发者可以根据实际场景取消相应注释来使用合适的方法。

通过深入理解 vector 的容量收缩方法，并根据不同的应用场景选择合适的方法，可以有效地优化程序的内存使用和性能，提高 C++ 程序的质量和可靠性。在实际开发中，需要综合考虑各种因素，包括性能、代码可读性、兼容性等，以做出最佳的决策。