C++容器vector与set核心原理及高效使用指南-嵌云网-嵌入式AI开发资源站

C++容器vector与set核心原理及高效使用指南

露克

1. 动态数组vector的深度解析与实战技巧

作为C++标准库中最基础也最常用的容器，vector本质上是一个封装了动态数组的模板类。它完美解决了原生数组的痛点——固定大小、手动内存管理等问题。在实际项目中，我几乎每天都会用到vector来处理各种数据集合。

1.1 vector的核心特性与底层原理

vector的底层实现是一个动态分配的连续内存空间，这使得它同时具备数组和链表的优势：

随机访问时间复杂度O(1)
尾部插入/删除平均时间复杂度O(1)
自动扩容机制（通常按1.5或2倍增长）

重要提示：vector的size()返回实际元素数量，capacity()返回当前分配的内存容量。当size==capacity时再插入元素会触发扩容，这是一个相对耗时的操作。

cpp复制vector<int> v;  // 初始capacity可能是0
cout << v.size() << " " << v.capacity();  // 输出: 0 0
v.push_back(1);
cout << v.size() << " " << v.capacity();  // 可能输出: 1 1

1.2 vector初始化与内存预分配技巧

在实际工程中，合理初始化vector可以避免频繁扩容带来的性能损耗：

cpp复制// 方式1：指定初始大小和默认值
vector<int> v1(100, 0);  // 100个0

// 方式2：从数组初始化
int arr[] = {1,2,3};
vector<int> v2(arr, arr+3);

// 方式3：C++11列表初始化
vector<int> v3 = {1,2,3};

// 专业技巧：预分配足够容量
vector<int> v4;
v4.reserve(1000);  // 预先分配1000个元素空间

1.3 vector的增删改查实战

插入元素的三种典型场景：

cpp复制vector<int> v = {1,3,4};

// 尾部插入（高效）
v.push_back(5);  // 1,3,4,5

// 中间插入（O(n)复杂度）
v.insert(v.begin()+1, 2);  // 1,2,3,4,5

// 批量插入
int arr[] = {6,7};
v.insert(v.end(), arr, arr+2);  // 1,2,3,4,5,6,7

删除元素的注意事项：

cpp复制// 错误示范：遍历删除时直接使用索引会导致错位
for(int i=0; i<v.size(); i++) {
    if(v[i]%2 == 0) {
        v.erase(v.begin()+i);
        // 删除后i++会导致跳过下一个元素
    }
}

// 正确做法：使用迭代器
for(auto it=v.begin(); it!=v.end(); ) {
    if(*it%2 == 0) {
        it = v.erase(it);  // erase返回下一个有效迭代器
    } else {
        ++it;
    }
}

1.4 vector的高阶用法

二维vector的三种声明方式：

cpp复制// 方式1：固定行数，每行独立
vector<vector<int>> mat1(5);  // 5行，每行元素数不定

// 方式2：固定行列数
vector<vector<int>> mat2(5, vector<int>(3));  // 5行3列

// 方式3：不规则二维数组
vector<vector<int>> mat3;
mat3.push_back({1});        // 第0行1个元素
mat3.push_back({2,3});      // 第1行2个元素

性能优化技巧：

使用emplace_back替代push_back避免临时对象构造
大vector传参使用const引用避免拷贝
shrink_to_fit()释放多余内存

2. 有序集合set的完全指南

set是基于红黑树实现的有序容器，我在需要快速查找和去重的场景下经常使用它。与unordered_set相比，set保持了元素有序性，但查找效率同为O(logn)。

2.1 set的核心特性

元素自动按升序排列（可通过比较函数修改）
元素唯一性（重复插入无效）
插入/删除/查找时间复杂度均为O(logn)

cpp复制set<int> s = {3,1,2,1};  // 实际存储1,2,3
cout << s.size();  // 输出3

2.2 set的插入与查找实战

插入操作的返回值很实用：

cpp复制auto ret = s.insert(4);
if(ret.second) {
    cout << "插入成功，新元素位置：" << *ret.first;
}

// 批量插入效率更高
vector<int> v = {5,6,7};
s.insert(v.begin(), v.end());

查找操作的典型应用：

cpp复制// 检查元素是否存在
if(s.find(3) != s.end()) {
    cout << "元素3存在";
}

// 查找第一个不小于给定值的元素
auto it = s.lower_bound(3);  // 返回3的位置

2.3 set的删除与遍历技巧

安全删除模式：

cpp复制// 错误示范：直接删除可能不存在的元素
s.erase(100);  // 无报错但无效

// 安全做法：先查找再删除
auto it = s.find(100);
if(it != s.end()) {
    s.erase(it);
}

遍历的现代写法：

cpp复制// C++11范围for循环
for(int x : s) {
    cout << x << " ";
}

// 使用auto避免冗长类型声明
for(auto it=s.begin(); it!=s.end(); ++it) {
    cout << *it << " ";
}

2.4 set的高级应用

自定义排序规则：

cpp复制struct Person {
    string name;
    int age;
};

auto cmp = [](const Person& a, const Person& b) {
    return a.age < b.age;  // 按年龄排序
};

set<Person, decltype(cmp)> people(cmp);
people.insert({"Alice", 20});
people.insert({"Bob", 18});

与vector的性能对比：

频繁查找：set胜出
需要随机访问：vector胜出
内存占用：set因红黑树开销更大

3. 字符串处理专家string详解

string是我处理文本数据时的首选工具，它封装了丰富的字符串操作，比C风格字符数组安全易用得多。

3.1 string的输入输出陷阱

输入时的经典坑点：

cpp复制int n;
string s;
cin >> n;       // 读取整数后换行符留在缓冲区
getline(cin, s); // 直接读取到换行符，得到空字符串

// 正确做法：清除缓冲区
cin >> n;
cin.ignore();   // 忽略换行符
getline(cin, s);

多行输入处理技巧：

cpp复制vector<string> lines;
string line;
while(getline(cin, line)) {
    if(line.empty()) break;
    lines.push_back(line);
}

3.2 string的查找与截取

高效查找模式：

cpp复制string text = "The quick brown fox jumps over the lazy dog";

// 查找子串
size_t pos = text.find("fox");
if(pos != string::npos) {
    cout << "找到fox，位置：" << pos;
}

// 反向查找
pos = text.rfind("the");  // 从后向前找

子串操作的典型应用：

cpp复制string path = "/home/user/file.txt";

// 获取文件名
size_t slash = path.rfind('/');
string filename = path.substr(slash+1);

// 获取扩展名
size_t dot = filename.rfind('.');
string ext = filename.substr(dot+1);

3.3 string的修改与替换

安全替换策略：

cpp复制string s = "Hello World";

// 替换前先检查范围
if(s.length() >= 5) {
    s.replace(0, 5, "Hi");  // Hello -> Hi
}

// 批量替换所有匹配项
size_t pos = 0;
while((pos = s.find("l", pos)) != string::npos) {
    s.replace(pos, 1, "L");
    pos += 1;  // 避免无限循环
}