C++ STL 容器与算法如何使用 - 面试题

C++ STL 容器与算法

C++ 标准模板库（STL）提供了丰富的容器和算法，是 C++ 编程的重要组成部分。熟练掌握 STL 可以显著提高开发效率和代码质量。

序列容器

std::vector

动态数组，连续内存存储
支持随机访问，O(1) 时间复杂度
尾部插入和删除效率高 O(1)，中间插入删除 O(n)
自动扩容，通常容量翻倍

cpp
#include <vector>
#include <iostream>

int main() {
    // 创建 vector
    std::vector<int> vec = {1, 2, 3, 4, 5};
    
    // 访问元素
    std::cout << vec[0] << std::endl;  // 1
    std::cout << vec.at(1) << std::endl;  // 2（带边界检查）
    
    // 添加元素
    vec.push_back(6);  // 尾部添加
    vec.emplace_back(7);  // 原地构造
    
    // 插入元素
    vec.insert(vec.begin() + 2, 100);  // 在位置 2 插入
    
    // 删除元素
    vec.pop_back();  // 删除最后一个
    vec.erase(vec.begin());  // 删除第一个
    
    // 容量信息
    std::cout << "Size: " << vec.size() << std::endl;
    std::cout << "Capacity: " << vec.capacity() << std::endl;
    
    // 预留空间
    vec.reserve(100);  // 预留至少 100 个元素的空间
    
    // 调整大小
    vec.resize(50, 0);  // 调整为 50 个元素，新元素初始化为 0
    
    return 0;
}

std::deque

双端队列，分段连续内存
支持两端快速插入删除 O(1)
支持随机访问 O(1)
内存开销比 vector 大

cpp
#include <deque>

int main() {
    std::deque<int> dq = {1, 2, 3};
    
    // 两端操作
    dq.push_front(0);  // 头部添加
    dq.push_back(4);    // 尾部添加
    
    dq.pop_front();     // 头部删除
    dq.pop_back();      // 尾部删除
    
    // 随机访问
    std::cout << dq[1] << std::endl;
    
    return 0;
}

std::list

双向链表，非连续内存
任意位置插入删除 O(1)
不支持随机访问
额外内存开销（每个节点两个指针）

cpp
#include <list>

int main() {
    std::list<int> lst = {1, 2, 3, 4, 5};
    
    // 插入元素
    auto it = lst.begin();
    std::advance(it, 2);
    lst.insert(it, 100);  // 在位置 2 插入
    
    // 删除元素
    lst.erase(lst.begin());  // 删除第一个
    
    // 链表特有操作
    lst.splice(lst.end(), lst, lst.begin());  // 移动元素
    lst.sort();  // 排序
    lst.unique();  // 去重
    lst.reverse();  // 反转
    
    return 0;
}

关联容器

std::map

键值对容器，按键排序
基于红黑树实现
查找、插入、删除 O(log n)
键唯一

cpp
#include <map>
#include <string>

int main() {
    std::map<std::string, int> scores;
    
    // 插入元素
    scores["Alice"] = 90;
    scores["Bob"] = 85;
    scores.insert({"Charlie", 95});
    
    // 访问元素
    std::cout << scores["Alice"] << std::endl;  // 90
    
    // 查找元素
    auto it = scores.find("Bob");
    if (it != scores.end()) {
        std::cout << "Bob's score: " << it->second << std::endl;
    }
    
    // 删除元素
    scores.erase("Alice");
    
    // 遍历
    for (const auto& [name, score] : scores) {
        std::cout << name << ": " << score << std::endl;
    }
    
    return 0;
}

std::unordered_map

键值对容器，无序
基于哈希表实现
平均查找、插入、删除 O(1)
最坏情况 O(n)

cpp
#include <unordered_map>

int main() {
    std::unordered_map<std::string, int> cache;
    
    cache["key1"] = 100;
    cache["key2"] = 200;
    
    // 快速查找
    auto it = cache.find("key1");
    if (it != cache.end()) {
        std::cout << it->second << std::endl;
    }
    
    return 0;
}

std::set

有序集合，元素唯一
基于红黑树实现
查找、插入、删除 O(log n)

cpp
#include <set>

int main() {
    std::set<int> s = {5, 3, 1, 4, 2};
    
    // 插入元素
    s.insert(6);
    
    // 查找元素
    auto it = s.find(3);
    if (it != s.end()) {
        std::cout << "Found: " << *it << std::endl;
    }
    
    // 删除元素
    s.erase(1);
    
    // 遍历（自动排序）
    for (int val : s) {
        std::cout << val << " ";
    }
    
    return 0;
}

容器适配器

std::stack

后进先出（LIFO）
基于 deque 或 vector 实现

cpp
#include <stack>

int main() {
    std::stack<int> stk;
    
    stk.push(1);
    stk.push(2);
    stk.push(3);
    
    while (!stk.empty()) {
        std::cout << stk.top() << " ";
        stk.pop();
    }
    
    return 0;
}

std::queue

先进先出（FIFO）
基于 deque 实现

cpp
#include <queue>

int main() {
    std::queue<int> q;
    
    q.push(1);
    q.push(2);
    q.push(3);
    
    while (!q.empty()) {
        std::cout << q.front() << " ";
        q.pop();
    }
    
    return 0;
}

std::priority_queue

优先级队列
默认大顶堆

cpp
#include <queue>

int main() {
    std::priority_queue<int> pq;  // 大顶堆
    
    pq.push(3);
    pq.push(1);
    pq.push(4);
    pq.push(2);
    
    while (!pq.empty()) {
        std::cout << pq.top() << " ";
        pq.pop();
    }
    
    // 小顶堆
    std::priority_queue<int, std::vector<int>, std::greater<int>> minPq;
    
    return 0;
}

STL 算法

排序算法：

cpp
#include <algorithm>
#include <vector>

int main() {
    std::vector<int> vec = {5, 2, 8, 1, 9, 3};
    
    // 排序
    std::sort(vec.begin(), vec.end());
    
    // 部分排序
    std::partial_sort(vec.begin(), vec.begin() + 3, vec.end());
    
    // 第 n 大元素
    std::nth_element(vec.begin(), vec.begin() + 2, vec.end());
    
    return 0;
}

查找算法：

cpp
int main() {
    std::vector<int> vec = {1, 2, 3, 4, 5};
    
    // 二分查找（需要有序）
    auto it = std::lower_bound(vec.begin(), vec.end(), 3);
    
    // 查找
    auto found = std::find(vec.begin(), vec.end(), 3);
    
    // 计数
    int count = std::count(vec.begin(), vec.end(), 3);
    
    return 0;
}

变换算法：

cpp
int main() {
    std::vector<int> vec1 = {1, 2, 3};
    std::vector<int> vec2(3);
    
    // 复制
    std::copy(vec1.begin(), vec1.end(), vec2.begin());
    
    // 变换
    std::transform(vec1.begin(), vec1.end(), vec2.begin(),
                  [](int x) { return x * 2; });
    
    // 填充
    std::fill(vec2.begin(), vec2.end(), 0);
    
    // 生成
    std::generate(vec2.begin(), vec2.end(),
                  []() { return rand() % 100; });
    
    return 0;
}

数值算法：

cpp
#include <numeric>

int main() {
    std::vector<int> vec = {1, 2, 3, 4, 5};
    
    // 求和
    int sum = std::accumulate(vec.begin(), vec.end(), 0);
    
    // 内积
    std::vector<int> vec2 = {2, 3, 4, 5, 6};
    int product = std::inner_product(vec.begin(), vec.end(),
                                      vec2.begin(), 0);
    
    // 差分
    std::vector<int> diff(vec.size());
    std::adjacent_difference(vec.begin(), vec.end(), diff.begin());
    
    return 0;
}

迭代器

迭代器分类：

输入迭代器：只读，单向
输出迭代器：只写，单向
前向迭代器：读写，单向
双向迭代器：读写，双向
随机访问迭代器：读写，随机访问

cpp
int main() {
    std::vector<int> vec = {1, 2, 3, 4, 5};
    
    // 正向迭代器
    for (auto it = vec.begin(); it != vec.end(); ++it) {
        std::cout << *it << " ";
    }
    
    // 反向迭代器
    for (auto it = vec.rbegin(); it != vec.rend(); ++it) {
        std::cout << *it << " ";
    }
    
    // 常量迭代器
    for (auto it = vec.cbegin(); it != vec.cend(); ++it) {
        std::cout << *it << " ";
    }
    
    return 0;
}

函数对象与 Lambda

Lambda 表达式：

cpp
int main() {
    std::vector<int> vec = {5, 2, 8, 1, 9};
    
    // 简单 lambda
    std::sort(vec.begin(), vec.end(), [](int a, int b) {
        return a < b;
    });
    
    // 捕获变量
    int threshold = 5;
    auto it = std::find_if(vec.begin(), vec.end(),
                           [threshold](int x) {
                               return x > threshold;
                           });
    
    // 可变 lambda
    int sum = 0;
    std::for_each(vec.begin(), vec.end(), [&sum](int x) mutable {
        sum += x;
    });
    
    return 0;
}

std::function：

cpp
#include <functional>

int main() {
    std::function<int(int, int)> add = [](int a, int b) {
        return a + b;
    };
    
    std::cout << add(10, 20) << std::endl;
    
    return 0;
}

最佳实践

1. 选择合适的容器

cpp
// 需要随机访问，频繁尾部插入
std::vector<int> vec;

// 需要频繁两端插入
std::deque<int> dq;

// 需要频繁中间插入删除
std::list<int> lst;

// 需要按键查找
std::map<std::string, int> mp;

// 需要快速查找，不关心顺序
std::unordered_map<std::string, int> ump;

2. 预分配空间

cpp
std::vector<int> vec;
vec.reserve(1000);  // 预先分配空间，避免多次重新分配

3. 使用 emplace 代替 push

cpp
std::vector<std::pair<int, int>> vec;

// 推荐
vec.emplace_back(1, 2);  // 原地构造

// 不推荐
vec.push_back(std::make_pair(1, 2));  // 可能产生临时对象

4. 使用移动语义

cpp
std::vector<std::string> vec;
std::string str = "Hello";

vec.push_back(std::move(str));  // 移动而非拷贝

5. 使用算法代替循环

cpp
std::vector<int> vec = {1, 2, 3, 4, 5};

// 推荐
int sum = std::accumulate(vec.begin(), vec.end(), 0);

// 不推荐
int sum = 0;
for (int val : vec) {
    sum += val;
}

性能考虑

时间复杂度：

vector::push_back: 平均 O(1)，最坏 O(n)
list::insert: O(1)
map::find: O(log n)
unordered_map::find: 平均 O(1)，最坏 O(n)

空间复杂度：

vector: 连续内存，无额外开销
list: 每个节点额外两个指针
map: 每个节点额外三个指针（红黑树）
unordered_map: 每个节点额外一个指针 + 哈希表开销

缓存友好性：

vector: 最好（连续内存）
deque: 中等（分段连续）
list: 最差（分散内存）