std::vector
主要介绍std::vector相关的知识点
·
这里主要介绍下reserce/resize、push_back/emplace_back、shrink_to_fit/clear等接口；
1. reserve and resize
C++的vector对象可以通过reserve方法来设置vector对象的容量，通过resize方法来改变vector对象的大小。reserve所设置的容量指的是vector容器中可容纳元素的预留空间个数，但并不真正创建元素对象。resize则是直接改变vector容器中元素的个数，并且创建对象或者销毁空间。
resize()函数和容器的size息息相关。调用resize(n)后，容器的size即为n。至于是否影响capacity，取决于调整后的容器的size是否大于capacity。
reserve()函数和容器的capacity息息相关。调用reserve(n)后，若容器的capacity<n，则重新分配内存空间，从而使得capacity等于n。
如果capacity>=n呢？capacity无变化。
从两个函数的用途可以发现，容器调用resize()函数后，所有的空间都已经初始化了，所以可以直接访问。
而reserve()函数预分配出的空间没有被初始化，所以不可访问。
#include <iostream>
#include <vector>
#include <string>
#include <map>
using ValueType = std::string;
const ValueType dv = "aaaaaaaaaaaaaaaaaaaaaaaa";
constexpr int maxSize = 10;
class Widget {
public:
Widget(ValueType value = dv) : value{value}
{
std::cout << "Widget(ValueType) constructor: " << this << std::endl;
}
Widget(const Widget& w) : value{w.value}
{
std::cout<<"copy constructor" << std::endl;
}
Widget& operator=(const Widget& rhs)
{
if (this != &rhs)
{
value = rhs.value;//assign new resource
}
std::cout << "copy assignment constructor" << std::endl;
return *this;
}
//这里移动构造函数定义为noexcept
Widget(Widget&& w) noexcept: value{std::move(w.value)}
{
std::cout << "move constructor" << std::endl;
}
Widget& operator=(Widget&& rhs)
{
if (this != &rhs)
{
value = std::move(rhs.value);//assign new resource
}
std::cout << "move assignment constructor" << std::endl;
return *this;
}
~Widget()
{
if (value.empty())
{
std::cout << "0~destructor:" << this << std::endl;
}
else
{
value.clear();
std::cout << "~destructor:" << this << std::endl;
}
}
void print(){std::cout << "value:" << value << " : " << this << std::endl;}
private:
ValueType value{};
};
void test_reserve()
{
std::vector<Widget> v{Widget{"aaaaaaaaaaaaaaaaaaaaaaaa"}, Widget{"bbbbbbbbbbbbbbbbbbbbbbbb"}, Widget{"ccccccccccccccccccccccc"}};
std::cout << "size()=" << v.size() << ", capacity()=" << v.capacity() << std::endl << std::endl;
v.reserve(2);//当reserve的数据空间小于capacity的时候什么都不做;
std::cout << "size()=" << v.size() << ", capacity()=" << v.capacity() << std::endl << std::endl;
//当reserve的数据空间大于capacity时，vector的capacity变为reserve指定的大校
v.reserve(5);//由于要重新分配比 3 更大的存储空间，这里再次调用的移动构造函数(如果移动构造函数没有noexcept，则调用拷贝构造函数)
std::cout << "size()=" << v.size() << ", capacity()=" << v.capacity() << std::endl << std::endl;
v.reserve(4);
std::cout << "size()=" << v.size() << ", capacity()=" << v.capacity() << std::endl << std::endl;
v.reserve(2);
std::cout << "size()=" << v.size() << ", capacity()=" << v.capacity() << std::endl << std::endl;
}
void test_resize()
{
std::vector<Widget> v{Widget{"aaaaaaaaaaaaaaaaaaaaaaaa"}, Widget{"bbbbbbbbbbbbbbbbbbbbbbbb"}, Widget{"ccccccccccccccccccccccc"}};
std::cout << std::endl;
std::cout << "size()=" << v.size() << ", capacity()=" << v.capacity() << std::endl << std::endl;
v.resize(5);//vector重新分配空间(需要移动/拷贝原数据),resize的空间大于size()时,会构造 5 - size()个数据项(这里是构造2个新的Widget)
std::cout << "size()=" << v.size() << ", capacity()=" << v.capacity() << std::endl << std::endl;
v.resize(4);//destory多余指定size的数据项
std::cout << "size()=" << v.size() << ", capacity()=" << v.capacity() << std::endl << std::endl;
v.resize(2);//destory多余指定size的数据项
std::cout << "size()=" << v.size() << ", capacity()=" << v.capacity() << std::endl << std::endl;
}
int main()
{
test_reserve();
std::cout << "----------------------" << std::endl;
test_resize();
return 0;
}output:
2. vector(count, value) vs reserve(n)
这里有一个点需要注意下：vector( size_type count,
const T& value,
const Allocator& alloc = Allocator() );
和 vector.reserve的区别， 这个vector会构造数据项，而reserve不构造数据项，只是预留了空间;
#include <iostream>
#include <vector>
void test_vector_constructor_vs_reserve()
{
std::vector<int> v1(2,3);
std::cout << "size()=" << v1.size() << ", capacity()=" << v1.capacity() << std::endl << std::endl;
for(const auto i : v1)
{
std::cout << i << ' ';
}
std::cout << std::endl;
std::vector<int> v2{};
v2.reserve(2);//当reserve的数据空间小于capacity的时候什么都不做;
std::cout << "size()=" << v2.size() << ", capacity()=" << v2.capacity() << std::endl << std::endl;
}
int main()
{
test_vector_constructor_vs_reserve();
return 0;
}3. shrink_to_fit vs clear
shrink_to_fit() : 它减少容器的容量以适应其大小并销毁超出容量的所有元素。它会尝试重新分配内存并释放未使用的多余内存。
clear():从容器擦除所有元素。此调用后 size() 返回零。使任何指代所含元素的引用、指针或迭代器失效。任何尾后迭代器也会失效。 保持 vector 的 capacity() 不变。
#include <iostream>
#include <vector>
#include <string>
using ValueType = std::string;
const ValueType dv = "aaaaaaaaaaaaaaaaaaaaaaaa";
constexpr int maxSize = 10;
class Widget {
public:
Widget(ValueType value = dv) : value{value}
{
std::cout << "Widget(ValueType) constructor: " << this << std::endl;
}
Widget(const Widget& w) : value{w.value}
{
std::cout<<"copy constructor" << std::endl;
}
Widget& operator=(const Widget& rhs)
{
if (this != &rhs)
{
value = rhs.value;//assign new resource
}
std::cout << "copy assignment constructor" << std::endl;
return *this;
}
//这里移动构造函数定义为noexcept
Widget(Widget&& w) noexcept: value{std::move(w.value)}
{
std::cout << "move constructor" << std::endl;
}
Widget& operator=(Widget&& rhs)
{
if (this != &rhs)
{
value = std::move(rhs.value);//assign new resource
}
std::cout << "move assignment constructor" << std::endl;
return *this;
}
~Widget()
{
if (value.empty())
{
std::cout << "0~destructor:" << this << std::endl;
}
else
{
value.clear();
std::cout << "~destructor:" << this << std::endl;
}
}
void print(){std::cout << "value:" << value << " : " << this << std::endl;}
private:
ValueType value{};
};
void test_shrink_to_fit()
{
std::vector<Widget> v;
std::cout << "size()=" << v.size() << ", capacity()=" << v.capacity() << std::endl << std::endl;
v.emplace_back(std::string(24, 'a'));
v.emplace_back(std::string(24, 'b'));
v.emplace_back(std::string(24, 'c'));
v.emplace_back(std::string(24, 'd'));
v.emplace_back(std::string(24, 'e'));
std::cout << "size()=" << v.size() << ", capacity()=" << v.capacity() << std::endl << std::endl;
v.shrink_to_fit();//按照我测试结果，测试capacity=8, size为添加的5个元素;
//shrink_to_fit会释放掉多余的vector空间，使得capacity()==size();
//这里可能会重新分配空间，具体依赖于编译器的实现
std::cout << "size()=" << v.size() << ", capacity()=" << v.capacity() << std::endl << std::endl;
}
void test_clear()
{
std::vector<Widget> v{Widget{"aaaaaaaaaaaaaaaaaaaaaaaa"}, Widget{"bbbbbbbbbbbbbbbbbbbbbbbb"}, Widget{"ccccccccccccccccccccccc"}};
std::cout << "size()=" << v.size() << ", capacity()=" << v.capacity() << std::endl << std::endl;
std::cout << "call clear():" << std::endl;;
v.clear();//会把所有数据项destory掉，此时size()大小为0， capacity则不变;
std::cout << "size()=" << v.size() << ", capacity()=" << v.capacity() << std::endl << std::endl;
}
int main()
{
test_shrink_to_fit();
std::cout << std::endl << "----------------------" << std::endl << std::endl;
test_clear();
return 0;
}4. push_back vs emplace_back
push_back:是插入数据到vector，这里会构造一个临时的数据项，这个临时数据项参数满足push_back(T&& value)接口，通过移动构造函数把这个临时的数据项移动到vector对应的位置上；
emplace_back：是通过完美转发参数，在vector对应的位置上就地构造，只需要调用一次构造函数就可以；这种情况下，效率上来说要比push_back高一些；
对于push_back和emplace_back来说，如果传入的数据项本身是个左值，那么他们效率上都是一样的。因为这两个接口都只需要调用一次拷贝构造函数。代码如下：
#include <iostream>
#include <vector>
#include <string>
#include <map>
using ValueType = std::string;
const ValueType dv = "aaaaaaaaaaaaaaaaaaaaaaaa";
constexpr int maxSize = 10;
class Widget {
public:
Widget(ValueType value = dv) : value{value}
{
std::cout << "Widget(ValueType) constructor: " << this << std::endl;
}
Widget(const Widget& w) : value{w.value}
{
std::cout<<"copy constructor" << std::endl;
}
Widget& operator=(const Widget& rhs)
{
if (this != &rhs)
{
value = rhs.value;//assign new resource
}
std::cout << "copy assignment constructor" << std::endl;
return *this;
}
Widget(Widget&& w) : value{std::move(w.value)}
{
std::cout << "move constructor" << std::endl;
}
Widget& operator=(Widget&& rhs)
{
if (this != &rhs)
{
value = std::move(rhs.value);//assign new resource
}
std::cout << "move assignment constructor" << std::endl;
return *this;
}
~Widget()
{
if (value.empty())
{
std::cout << "0~destructor:" << this << std::endl;
}
else
{
value.clear();
std::cout << "~destructor:" << this << std::endl;
}
}
void print(){std::cout << "value:" << value << " : " << this << std::endl;}
private:
ValueType value{};
};
void push_vs_empalce_with_rvalue_item()
{
std::vector<Widget> v{};
v.reserve(10);
std::cout << std::endl;
std::string str(24, 'a');
v.push_back(str);
std::cout << std::endl;
v.emplace_back(str);
std::cout << std::endl;
}
void push_vs_empalce_with_lvalue_item()
{
Widget w1("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa");
Widget w2("bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb");
std::vector<Widget> v{};
v.reserve(10);
std::cout << std::endl;
v.push_back(w1);
std::cout << std::endl;
v.emplace_back(w2);
std::cout << std::endl;
}
int main()
{
push_vs_empalce_with_rvalue_item();
std::cout << std::endl << "-------------------------" << std::endl << std::endl;
push_vs_empalce_with_lvalue_item();
return 0;
}output:
5 vector::reserve() 和 vector() 区别
std::vector<int> v1; v1.reserve(10) 和 std::vector<int> v2(10); 是两种不同的初始化方式，它们的行为和适用场景有显著区别。以下是对它们的详细对比和示例说明：
1. 内存分配与初始化
std::vector<int> v1; v1.reserve(10)
-
行为:
-
v1是一个空的vector，初始时不包含任何元素。 -
v1.reserve(10)仅为v1分配至少能容纳 10 个元素的内存空间，但不会创建或初始化任何元素。 -
v1.size()仍为 0，v1.capacity()至少为 10。
-
-
适用场景:
-
当你需要预先分配内存以避免频繁重新分配，但暂时不需要实际元素时使用。
-
适合需要逐步添加元素的场景。
-
std::vector<int> v2(10)
-
行为:
-
v2是一个包含 10 个元素的vector，每个元素被值初始化为int()（即0）。 -
v2.size()为 10，v2.capacity()至少为 10。
-
-
适用场景:
-
当你需要一个固定大小的
vector，并且所有元素需要初始化为默认值（如0）时使用。 -
适合需要立即使用元素的场景。
-
2. 访问元素
std::vector<int> v1; v1.reserve(10)
-
行为:
-
v1是空的，不能直接通过下标访问元素（如v1[0]），否则会导致未定义行为。 -
必须通过
push_back或emplace_back添加元素后才能访问。
-
-
示例 1 :
std::vector<int> v1;
v1.reserve(10);
// v1[0] = 1; // 错误：未定义行为，因为 v1 是空的
v1.push_back(1); // 正确：添加元素
std::cout << v1[0]; // 正确：输出 1std::vector<int> v2(10)
-
行为:
-
v2包含 10 个元素，可以直接通过下标访问元素（如v2[0]）。 -
所有元素初始化为
0。
-
-
示例:
std::vector<int> v2(10);
std::cout << v2[0]; // 正确：输出 0
v2[0] = 1; // 正确：修改元素
std::cout << v2[0]; // 正确：输出 13. 添加元素
std::vector<int> v1; v1.reserve(10)
-
行为:
-
可以通过
push_back或emplace_back添加元素，直到达到capacity()。 -
添加元素不会触发重新分配，因为内存已经预先分配。
-
-
示例:
std::vector<int> v1;
v1.reserve(10);
for (int i = 0; i < 10; ++i) {
v1.push_back(i); // 添加元素
}
std::cout << v1.size(); // 输出 10std::vector<int> v2(10)
-
行为:
-
v2已经有 10 个元素，直接修改现有元素即可。 -
如果需要添加更多元素，可以使用
push_back或emplace_back，但可能会触发重新分配。
-
-
示例:
std::vector<int> v2(10);
for (int i = 0; i < 10; ++i) {
v2[i] = i; // 修改现有元素
}
v2.push_back(10); // 添加新元素，可能触发重新分配
std::cout << v2.size(); // 输出 114. 性能对比
std::vector<int> v1; v1.reserve(10)
-
优点:
-
避免频繁的内存重新分配，适合需要逐步添加元素的场景。
-
-
缺点:
-
需要显式添加元素，不能直接访问未初始化的内存。
-
std::vector<int> v2(10)
-
优点:
-
直接初始化所有元素，适合需要立即使用元素的场景。
-
-
缺点:
-
如果不需要所有元素，可能会浪费初始化时间。
-
完整代码示例：
#include <iostream>
#include <vector>
int main() {
// 示例 1: 使用 reserve
std::vector<int> v1;
v1.reserve(10); // 预分配内存
for (int i = 0; i < 10; ++i) {
v1.push_back(i); // 逐步添加元素
}
std::cout << "v1: ";
for (int i : v1) {
std::cout << i << " ";
}
std::cout << "\n";
// 示例 2: 使用固定大小初始化
std::vector<int> v2(10); // 初始化 10 个元素，值为 0
for (int i = 0; i < 10; ++i) {
v2[i] = i; // 直接修改元素
}
std::cout << "v2: ";
for (int i : v2) {
std::cout << i << " ";
}
std::cout << "\n";
return 0;
}6 vector中删除指定元素
从vector<int> v1 = {7, 8, 9, 10, 9, 10};中删除指定的元素9，哪些算法是正确的：
//algorithm A:
for (auto iter = v1.begin(); iter != v1.end();iter++)
{
if (*iter == 9)
{
v1.erase(iter);
}
}
//algorithm B:
for (auto iter = v1.begin(); iter != v1.end();iter++)
{
if (*iter == 9)
{
iter=v1.erase(iter);
}
}
//algorithm C:
for (auto iter = v1.begin(); iter != v1.end();)
{
if (*iter == 9)
{
iter = v1.erase(iter);
}
else
{
iter++;
}
}
//algorithm D:
for(auto iter=v1.begin(); iter!=v1.end(); )
{
if( *iter == 9)
{
auto& iter2 = iter;
v1.erase(iter2);
}
else
{
iter ++ ;
}
}算法C和D是正确的
algorithm A:
for (auto iter = v1.begin(); iter != v1.end();iter++)
{
if (*iter == 9)
{
v1.erase(iter);//执行完这行代码后，iter就编程了野指针，对一个野指针进行iter++是错误的；
}
}algorithm B:
for (auto iter = v1.begin(); iter != v1.end();iter++)
{
if (*iter == 9)
{
iter=v1.erase(iter);
}
}这段代码也是错误的：1）无法删除两个连续的"3"； 2）当3位于vector最后位置的时候，也会出错（在veci.end()上执行 ++ 操作）
#include <iostream>
#include <string>
#include <vector>
struct A
{
int i; //key
std::string s;
};
int main(void)
{
std::vector<A> va{{10, "aaa"},{10, "bbb"}, {10, "ccc"}, {10, "ddd"}, {10, "hhh"},{6, "eee"}, {8, "fff"} /*, {10, "segment fault"}*/};
for (auto iter = va.begin(); iter != va.end(); iter++)
{
if ((*iter).i == 10)
{
iter = va.erase(iter);
}
}
for(const auto v : va)
{
std::cout << "{" << v.i << "," << v.s << "} ";
}
}
Result: {10,bbb} {10,ddd} {6,eee} {8,fff}
在一次循环内部，当执行了 va.erase() 后, iter 指针会自动指向被删除了的元素的下一个位置，这个时候再执行循环体中的 iter++，就会导致 iter 直接指向了下下个元素！ 当第一个10被删除后， iter 指向了第三个10,并且将其删除，然后又指向了第5个10，将其删除。因此结果中，第二个和第四个10就被保留了，没有删除干净。
其实，这种写法的后果不仅仅是删除不干净那么简单：如果在数组最后的位置还有一个10呢？当最后一个10被删除后， iter 直接指向了数组的最后一位数字的后一位，超出了数组的界限，就会引发程序崩溃！
如果要手动实现这个算法从后面开始查找，总体移动的元素数量比从开头查找要移动的数量少。
C++20中可以使用std::erase_if来实现了。
vector.erase()函数的常见陷阱_vector.erase(it++)-CSDN博客
vector中erase用法注意事项_vector erase后begin会变吗-CSDN博客
7. std::erase和 std::remove+std::vector::erase
在C++中，当需要从容器中删除满足特定条件的元素时，通常的做法是使用std::remove或std::remove_if算法将不需要的元素移动到容器的末尾，然后使用std::erase函数删除这些元素。这种方法的效率高于直接使用std::erase逐个删除元素，尤其是在处理大数据量时，效率提升非常明显。
这是因为std::remove或std::remove_if算法通常具有较低的算法复杂度，能够快速地将不需要的元素集中到容器的末尾，然后通过一次性的erase操作删除这些元素，避免了逐个删除时的重复移动操作。
具体来说，当使用std::remove或std::remove_if后，容器的迭代器会指向第一个不需要的元素的位置。此时，通过调用std::erase函数，并将参数设置为std::remove或std::remove_if返回的迭代器和容器的end()迭代器，可以一次性删除所有不需要的元素。这种方法的整体效率较高，尤其是在处理大量数据时，能够显著提高程序的性能。
需要注意的是，由于容器中的元素在删除过程中可能会被移动，因此直接使用std::erase逐个删除元素可能会导致效率低下，并且容易出错。而通过结合使用std::remove和std::erase，可以避免这些问题，确保代码的正确性和效率。
#include <vector>
#include <algorithm>
#include <chrono>
#include <iostream>
#include <random>
#include <iomanip>
class Timer {
public:
Timer(const std::string& name) : name_(name), start_(std::chrono::high_resolution_clock::now()) {}
~Timer() {
auto end = std::chrono::high_resolution_clock::now();
auto duration = std::chrono::duration_cast<std::chrono::microseconds>(end - start_);
std::cout << std::setw(30) << std::left << name_
<< ": " << duration.count() << " μs" << std::endl;
}
private:
std::string name_;
std::chrono::high_resolution_clock::time_point start_;
};
// 生成测试数据
std::vector<int> generateTestData(size_t size, double removalRatio = 0.3) {
std::vector<int> data;
data.reserve(size);
std::random_device rd;
std::mt19937 gen(rd());
std::uniform_int_distribution<> dis(1, 100);
for (size_t i = 0; i < size; ++i) {
data.push_back(dis(gen));
}
return data;
}
// 测试 std::erase (C++20)
void testStdErase(std::vector<int> data, int valueToRemove) {
Timer timer("std::erase (C++20)");
std::erase(data, valueToRemove);
std::cout << " 残留元素数量: " << data.size() << std::endl;
}
// 测试 std::remove + vector::erase (经典方法)
void testRemoveErase(std::vector<int> data, int valueToRemove) {
Timer timer("remove + vector::erase");
auto it = std::remove(data.begin(), data.end(), valueToRemove);
data.erase(it, data.end());
std::cout << " 残留元素数量: " << data.size() << std::endl;
}
// 测试 std::erase_if (C++20) - 更灵活的版本
void testStdEraseIf(std::vector<int> data, int valueToRemove) {
Timer timer("std::erase_if (C++20)");
std::erase_if(data, [valueToRemove](int x) { return x == valueToRemove; });
std::cout << " 残留元素数量: " << data.size() << std::endl;
}
// 测试 std::remove_if + vector::erase (经典方法)
void testRemoveIfErase(std::vector<int> data, int valueToRemove) {
Timer timer("remove_if + vector::erase");
auto it = std::remove_if(data.begin(), data.end(),
[valueToRemove](int x) { return x == valueToRemove; });
data.erase(it, data.end());
std::cout << " 残留元素数量: " << data.size() << std::endl;
}
// 手动实现的删除（用于比较基准）
void testManualErase(std::vector<int> data, int valueToRemove) {
Timer timer("手动实现");
auto writeIt = data.begin();
for (auto readIt = data.begin(); readIt != data.end(); ++readIt) {
if (*readIt != valueToRemove) {
if (writeIt != readIt) {
*writeIt = *readIt;
}
++writeIt;
}
}
data.erase(writeIt, data.end());
std::cout << " 残留元素数量: " << data.size() << std::endl;
}
void runBenchmarks(size_t dataSize, int runs = 5) {
std::cout << "\n=== 基准测试: 数据大小 " << dataSize << " ===\n";
// 生成测试数据
auto originalData = generateTestData(dataSize);
int valueToRemove = 50; // 移除值为50的元素
// 统计要删除的元素数量
size_t elementsToRemove = std::count(originalData.begin(), originalData.end(), valueToRemove);
std::cout << "原始数据大小: " << originalData.size()
<< ", 要删除的元素数量: " << elementsToRemove << "\n\n";
// 多次运行取平均值
std::cout << "运行 " << runs << " 次测试...\n\n";
for (int run = 0; run < runs; ++run) {
std::cout << "--- 第 " << (run + 1) << " 次运行 ---\n";
testStdErase(originalData, valueToRemove);
testRemoveErase(originalData, valueToRemove);
testStdEraseIf(originalData, valueToRemove);
testRemoveIfErase(originalData, valueToRemove);
testManualErase(originalData, valueToRemove);
std::cout << std::endl;
}
}
// 特殊场景测试
void testSpecialScenarios() {
std::cout << "\n=== 特殊场景测试 ===\n";
// 场景1: 删除大量元素（90%）
{
std::cout << "\n场景1: 删除大量元素（大部分元素值为1）\n";
std::vector<int> data(100000);
std::fill(data.begin(), data.begin() + 90000, 1); // 90%为1
std::fill(data.begin() + 90000, data.end(), 2); // 10%为2
testStdErase(data, 1);
testRemoveErase(std::vector<int>(data), 1);
}
// 场景2: 删除少量元素（1%）
{
std::cout << "\n场景2: 删除少量元素（只有1%的元素值为99）\n";
std::vector<int> data(100000, 1);
for (size_t i = 0; i < 1000; ++i) {
data[i * 100] = 99; // 1%为99
}
testStdErase(data, 99);
testRemoveErase(std::vector<int>(data), 99);
}
// 场景3: 没有要删除的元素
{
std::cout << "\n场景3: 没有要删除的元素\n";
std::vector<int> data(100000, 1);
testStdErase(data, 999);
testRemoveErase(std::vector<int>(data), 999);
}
}
// 内存使用情况分析
void analyzeMemoryUsage() {
std::cout << "\n=== 内存使用分析 ===\n";
std::vector<int> data(1000000, 42);
std::cout << "原始容量: " << data.capacity() << std::endl;
std::cout << "原始大小: " << data.size() << std::endl;
// 使用 std::erase
auto data1 = data;
std::erase(data1, 42);
std::cout << "\nstd::erase 后:\n";
std::cout << " 容量: " << data1.capacity() << std::endl;
std::cout << " 大小: " << data1.size() << std::endl;
// 使用 remove + erase
auto data2 = data;
auto it = std::remove(data2.begin(), data2.end(), 42);
data2.erase(it, data2.end());
std::cout << "\nremove + erase 后:\n";
std::cout << " 容量: " << data2.capacity() << std::endl;
std::cout << " 大小: " << data2.size() << std::endl;
}
int main() {
std::cout << "=== Vector 删除操作性能比较 ===\n";
std::cout << "比较 std::erase (C++20) vs std::remove + vector::erase\n";
// 不同大小的数据集测试
runBenchmarks(1000, 3);
runBenchmarks(10000, 3);
runBenchmarks(100000, 3);
runBenchmarks(1000000, 2);
// 特殊场景测试
testSpecialScenarios();
// 内存使用分析
analyzeMemoryUsage();
std::cout << "\n=== 结论 ===\n";
std::cout << "1. 性能方面: std::erase 和 remove+erase 性能基本相同\n";
std::cout << "2. 代码简洁性: std::erase 更简洁，减少了样板代码\n";
std::cout << "3. 类型安全: std::erase 提供更好的类型推导\n";
std::cout << "4. 标准支持: std::erase 需要 C++20，remove+erase 兼容性更好\n";
std::cout << "5. 建议: 如果项目支持 C++20，优先使用 std::erase/std::erase_if\n";
return 0;
}
#include <algorithm>
#include <chrono>
#include <iostream>
#include <vector>
// 方法1：从前往后删除（低效）
void forwardErase(std::vector<int> nums)
{
for (auto iter = nums.begin(); iter != nums.end();)
{
if (*iter == 2)
{
iter = nums.erase(iter);
}
else
{
++iter;
}
}
}
// 方法2：从后往前删除（较好）
void backwardErase(std::vector<int> nums)
{
if (nums.empty())
{
return;
}
for (auto iter = nums.end() - 1; ; )
{
if (*iter == 2)
{
iter = nums.erase(iter);
}
if (iter == nums.begin())
{
break;
}
--iter;
}
}
// 方法3：erase-remove idiom（最佳 - C++11/14/17）
void eraseRemoveIdiom(std::vector<int> nums)
{
nums.erase(
std::remove(nums.begin(), nums.end(), 2),
nums.end()
);
}
// 方法4：erase-remove_if（最灵活 - C++11/14/17）
void eraseRemoveIfIdiom(std::vector<int> nums)
{
nums.erase(
std::remove_if(nums.begin(), nums.end(),
[](int val) { return val == 2; }
),
nums.end()
);
}
// 方法5：std::erase（C++20 新特性）
void stdErase(std::vector<int> nums)
{
std::erase(nums, 2);
}
// 方法6：std::erase_if（C++20 新特性）
void stdEraseIf(std::vector<int> nums)
{
std::erase_if(nums, [](int val) { return val == 2; });
}
template<typename Func>
void benchmark(const char* name, Func func, const std::vector<int>& data)
{
auto start = std::chrono::high_resolution_clock::now();
func(data);
auto end = std::chrono::high_resolution_clock::now();
auto duration = std::chrono::duration_cast<std::chrono::microseconds>(end - start);
std::cout << name << ": " << duration.count() << " μs" << std::endl;
}
int main()
{
std::cout << "C++20 Vector Erase Optimization Benchmark\n";
std::cout << "==========================================\n\n";
// 测试数据集 1: 1000 个元素
{
std::vector<int> data;
data.reserve(1000);
for (int i = 0; i < 1000; ++i)
{
data.push_back(i % 2 == 0 ? 2 : i);
}
std::cout << "=== 测试 1: 1000 个元素 (删除约 1/2) ===\n";
benchmark("方法1: 从前往后删除 ", forwardErase, data);
benchmark("方法2: 从后往前删除 ", backwardErase, data);
benchmark("方法3: erase-remove (C++11) ", eraseRemoveIdiom, data);
benchmark("方法4: erase-remove_if(C++11)", eraseRemoveIfIdiom, data);
benchmark("方法5: std::erase (C++20) ", stdErase, data);
benchmark("方法6: std::erase_if (C++20)", stdEraseIf, data);
std::cout << "\n";
}
// 测试数据集 2: 10000 个元素
{
std::vector<int> data;
data.reserve(10000);
for (int i = 0; i < 10000; ++i)
{
data.push_back(i % 2 == 0 ? 2 : i);
}
std::cout << "=== 测试 2: 10000 个元素 (删除约 1/2) ===\n";
benchmark("方法1: 从前往后删除 ", forwardErase, data);
benchmark("方法2: 从后往前删除 ", backwardErase, data);
benchmark("方法3: erase-remove (C++11) ", eraseRemoveIdiom, data);
benchmark("方法4: erase-remove_if(C++11)", eraseRemoveIfIdiom, data);
benchmark("方法5: std::erase (C++20) ", stdErase, data);
benchmark("方法6: std::erase_if (C++20)", stdEraseIf, data);
std::cout << "\n";
}
// 测试数据集 3: 100000 个元素
{
std::vector<int> data;
data.reserve(100000);
for (int i = 0; i < 100000; ++i)
{
data.push_back(i % 2 == 0 ? 2 : i);
}
std::cout << "=== 测试 3: 100000 个元素 (删除约 1/2) ===\n";
std::cout << "⚠️ 方法1 (从前往后) 会非常慢，请耐心等待...\n";
benchmark("方法1: 从前往后删除 ", forwardErase, data);
benchmark("方法2: 从后往前删除 ", backwardErase, data);
benchmark("方法3: erase-remove (C++11) ", eraseRemoveIdiom, data);
benchmark("方法4: erase-remove_if(C++11)", eraseRemoveIfIdiom, data);
benchmark("方法5: std::erase (C++20) ", stdErase, data);
benchmark("方法6: std::erase_if (C++20)", stdEraseIf, data);
std::cout << "\n";
}
// 测试数据集 4: 1000000 个元素
{
std::vector<int> data;
data.reserve(1000000);
for (int i = 0; i < 1000000; ++i)
{
data.push_back(i % 2 == 0 ? 2 : i);
}
std::cout << "=== 测试 4: 1000000 个元素 (删除约 1/2) ===\n";
std::cout << "⚠️ 方法1 (从前往后) 会极其缓慢，可能需要数分钟...\n";
std::cout << "⚠️ 如果不想等待，可以按 Ctrl+C 中断\n";
benchmark("方法1: 从前往后删除 ", forwardErase, data);
benchmark("方法2: 从后往前删除 ", backwardErase, data);
benchmark("方法3: erase-remove (C++11) ", eraseRemoveIdiom, data);
benchmark("方法4: erase-remove_if(C++11)", eraseRemoveIfIdiom, data);
benchmark("方法5: std::erase (C++20) ", stdErase, data);
benchmark("方法6: std::erase_if (C++20)", stdEraseIf, data);
std::cout << "\n";
}
// 正确性验证
{
std::cout << "=== 正确性验证 ===\n";
// 测试 std::erase
{
std::vector<int> testData1{2, 2, 2, 3, 2, 4, 5, 6, 2, 2};
std::cout << "std::erase - 原始数据: ";
for (auto val : testData1)
{
std::cout << val << " ";
}
std::cout << "\n";
std::erase(testData1, 2);
std::cout << "std::erase - 删除所有 2 后: ";
for (auto val : testData1)
{
std::cout << val << " ";
}
std::cout << "\n";
}
// 测试 std::erase_if
{
std::vector<int> testData2{1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
std::cout << "\nstd::erase_if - 原始数据: ";
for (auto val : testData2)
{
std::cout << val << " ";
}
std::cout << "\n";
std::erase_if(testData2, [](int val) { return val % 2 == 0; }); // 删除偶数
std::cout << "std::erase_if - 删除所有偶数后: ";
for (auto val : testData2)
{
std::cout << val << " ";
}
std::cout << "\n期望结果: 1 3 5 7 9\n";
}
// 测试传统 erase-remove
{
std::vector<int> testData3{2, 2, 2, 3, 2, 4, 5, 6, 2, 2};
std::cout << "\nerase-remove - 原始数据: ";
for (auto val : testData3)
{
std::cout << val << " ";
}
std::cout << "\n";
testData3.erase(
std::remove(testData3.begin(), testData3.end(), 2),
testData3.end()
);
std::cout << "erase-remove - 删除所有 2 后: ";
for (auto val : testData3)
{
std::cout << val << " ";
}
std::cout << "\n期望结果: 3 4 5 6\n";
}
}
std::cout << "\n=== 总结 ===\n";
std::cout << "1. ❌ 从前往后删除：O(n²) - 最慢，避免使用\n";
std::cout << "2. ⚠️ 从后往前删除：O(n²) - 比方法1快约50%，但仍不推荐\n";
std::cout << "3. ✅ erase-remove：O(n) - 快速高效，C++11+ 推荐\n";
std::cout << "4. ✅ erase-remove_if：O(n) - 灵活强大，C++11+ 推荐\n";
std::cout << "5. ⭐ std::erase：O(n) - 最简洁，C++20 首选\n";
std::cout << "6. ⭐ std::erase_if：O(n) - 最强大，C++20 首选\n";
std::cout << "\n性能提升：方法3-6 比方法1 快 300-400 倍！\n";
return 0;
}
有“AI”的1024 = 2048，欢迎大家加入2048 AI社区
更多推荐
29
0- 0
已为社区贡献10条内容
所有评论(0)