第三章：STL容器和算法增强

📚 章节概述

现代C++对STL（Standard Template Library）进行了大量增强，引入了新的容器类型、改进了现有容器的接口、增加了许多实用的算法。本章将深入探讨这些增强特性，帮助您编写更高效、更表达力强的代码。

🎯 学习目标

学完本章后，您将能够：

  • 掌握std::array的特性和使用场景
  • 理解无序容器（unordered_map、unordered_set）的优势
  • 熟练使用emplace系列函数提高性能
  • 掌握现代STL算法的使用方法
  • 理解全局begin/end函数的便利性
  • 掌握容器适配器的现代用法
  • 学会设计自定义比较器和哈希函数

1. std::array - 固定大小数组容器

📖 理论讲解

std::array是C++11引入的固定大小数组容器，它结合了C风格数组的性能和STL容器的便利性。

💡 核心特性

  • 固定大小：编译时确定大小，无运行时开销
  • 栈分配：对象存储在栈上，不涉及动态内存分配
  • STL兼容：支持迭代器、算法等STL特性
  • 边界检查：at()方法提供边界检查

🔍 基本用法

#include <array>
#include <algorithm>

// 1. 声明和初始化
std::array<int, 5> arr1 = {1, 2, 3, 4, 5};
std::array<int, 5> arr2{};  // 零初始化
std::array<std::string, 3> str_arr = {"hello", "world", "cpp"};

// 2. 访问元素
std::cout << arr1[0] << std::endl;        // 不检查边界
std::cout << arr1.at(0) << std::endl;     // 检查边界
std::cout << arr1.front() << std::endl;   // 第一个元素
std::cout << arr1.back() << std::endl;    // 最后一个元素

// 3. 容器信息
std::cout << "Size: " << arr1.size() << std::endl;
std::cout << "Empty: " << arr1.empty() << std::endl;
std::cout << "Max size: " << arr1.max_size() << std::endl;

// 4. 迭代器支持
for (auto it = arr1.begin(); it != arr1.end(); ++it) {
    std::cout << *it << " ";
}

// 5. 范围for循环
for (const auto& element : arr1) {
    std::cout << element << " ";
}

🚀 高级特性

// 1. 填充和交换
std::array<double, 3> arr1;
arr1.fill(3.14);  // 所有元素设为3.14

std::array<double, 3> arr2 = {1.0, 2.0, 3.0};
arr1.swap(arr2);  // 交换两个数组的内容

// 2. 获取原始指针
int* raw_data = arr1.data();  // 获取底层数组指针

// 3. 结构化绑定（C++17）
std::array<int, 3> point = {10, 20, 30};
auto [x, y, z] = point;

// 4. 比较操作
std::array<int, 3> a1 = {1, 2, 3};
std::array<int, 3> a2 = {1, 2, 4};
bool equal = (a1 == a2);  // false
bool less = (a1 < a2);    // true（字典序比较）

🎯 使用场景

  1. 固定大小数据：坐标点、颜色值、小型查找表
  2. 性能关键代码：避免动态分配的开销
  3. 与C API交互：需要原始数组指针的场景
  4. 模板参数：大小是模板参数的算法

⚠️ 注意事项

  • 大小必须在编译时确定
  • 对象较大时要注意栈空间限制
  • 不支持动态调整大小

2. 无序容器 (Unordered Containers)

📖 理论讲解

无序容器基于哈希表实现，提供平均O(1)的查找、插入和删除性能，是对传统基于红黑树的有序容器的重要补充。

💡 核心特性

  • 哈希表实现：基于哈希表，不保持元素顺序
  • 性能优势：平均O(1)时间复杂度的操作
  • 自动扩容：根据负载因子自动调整哈希表大小
  • 自定义哈希：支持自定义哈希函数和相等比较

🔍 基本用法

#include <unordered_map>
#include <unordered_set>

// 1. unordered_map基本操作
std::unordered_map<std::string, int> word_count;

// 插入和访问
word_count["apple"] = 3;
word_count["banana"] = 2;
word_count.insert({"cherry", 1});

// 查找
auto it = word_count.find("apple");
if (it != word_count.end()) {
    std::cout << "Found: " << it->first << " = " << it->second << std::endl;
}

// 2. unordered_set基本操作
std::unordered_set<int> unique_numbers = {1, 2, 3, 4, 5};

// 插入
unique_numbers.insert(6);
auto [iter, inserted] = unique_numbers.insert(3);  // C++17结构化绑定
if (!inserted) {
    std::cout << "Element already exists" << std::endl;
}

// 查找
if (unique_numbers.count(3) > 0) {
    std::cout << "Found number 3" << std::endl;
}

// 删除
unique_numbers.erase(2);

🚀 性能调优

// 1. 预分配空间
std::unordered_map<std::string, int> map;
map.reserve(1000);  // 预分配空间，避免频繁rehash

// 2. 负载因子控制
std::cout << "Load factor: " << map.load_factor() << std::endl;
std::cout << "Max load factor: " << map.max_load_factor() << std::endl;
map.max_load_factor(0.5);  // 设置最大负载因子

// 3. 桶信息
std::cout << "Bucket count: " << map.bucket_count() << std::endl;
for (size_t i = 0; i < map.bucket_count(); ++i) {
    std::cout << "Bucket " << i << " size: " << map.bucket_size(i) << std::endl;
}

🎯 自定义哈希和比较

// 1. 自定义类型的哈希
struct Point {
    int x, y;
    bool operator==(const Point& other) const {
        return x == other.x && y == other.y;
    }
};

// 自定义哈希函数
struct PointHash {
    std::size_t operator()(const Point& p) const {
        return std::hash<int>()(p.x) ^ (std::hash<int>()(p.y) << 1);
    }
};

std::unordered_set<Point, PointHash> point_set;
point_set.insert({1, 2});
point_set.insert({3, 4});

// 2. 使用Lambda作为哈希函数
auto string_hash = [](const std::string& s) {
    return std::hash<std::string>()(s);
};

auto string_equal = [](const std::string& a, const std::string& b) {
    return a == b;
};

std::unordered_set<std::string, decltype(string_hash), decltype(string_equal)> 
    custom_set(0, string_hash, string_equal);

3. emplace系列函数 - 原地构造

📖 理论讲解

emplace系列函数允许在容器中直接构造对象，避免了临时对象的创建和拷贝/移动操作，提高了性能。

💡 核心概念

  • 原地构造：直接在容器的内存位置构造对象
  • 完美转发：保持参数的值类别（左值/右值）
  • 性能优化：避免不必要的拷贝和移动操作
  • 异常安全：构造失败不会影响容器状态

🔍 基本用法

#include <vector>
#include <map>

class Person {
public:
    std::string name;
    int age;
    
    Person(std::string n, int a) : name(std::move(n)), age(a) {
        std::cout << "Person constructed: " << name << std::endl;
    }
    
    Person(const Person& other) : name(other.name), age(other.age) {
        std::cout << "Person copied: " << name << std::endl;
    }
};

// 1. vector的emplace_back vs push_back
std::vector<Person> people;

// 使用push_back（会创建临时对象）
people.push_back(Person("Alice", 25));  // 构造临时对象，然后移动

// 使用emplace_back（直接构造）
people.emplace_back("Bob", 30);  // 直接在vector中构造对象

// 2. map的emplace vs insert
std::map<int, Person> person_map;

// 使用insert
person_map.insert({1, Person("Charlie", 35)});  // 创建临时pair和Person

// 使用emplace
person_map.emplace(2, "David", 40);  // 直接构造pair和Person

// 3. 其他容器的emplace操作
std::set<Person> person_set;
person_set.emplace("Eve", 28);  // 直接构造Person对象

🚀 高级用法

// 1. emplace_hint - 提供插入位置提示
std::map<int, std::string> ordered_map;
auto hint = ordered_map.end();
for (int i = 100; i >= 1; --i) {
    hint = ordered_map.emplace_hint(hint, i, "value" + std::to_string(i));
}

// 2. try_emplace - 仅在键不存在时插入（C++17）
std::map<std::string, int> scores;
scores.try_emplace("Alice", 100);  // 插入成功
scores.try_emplace("Alice", 200);  // 不会插入，Alice已存在

// 3. insert_or_assign - 插入或赋值（C++17）
scores.insert_or_assign("Bob", 150);   // 插入新元素
scores.insert_or_assign("Alice", 200); // 更新现有元素

// 4. 复杂对象的emplace
class ComplexObject {
    std::vector<int> data;
    std::string label;
public:
    ComplexObject(std::initializer_list<int> init, std::string l) 
        : data(init), label(std::move(l)) {}
};

std::vector<ComplexObject> objects;
objects.emplace_back({1, 2, 3, 4, 5}, "first object");

🎯 性能对比

// 性能测试示例
class ExpensiveObject {
    std::vector<int> large_data;
public:
    ExpensiveObject(size_t size) : large_data(size, 42) {
        std::cout << "Expensive object created" << std::endl;
    }
    
    ExpensiveObject(const ExpensiveObject& other) : large_data(other.large_data) {
        std::cout << "Expensive object copied" << std::endl;
    }
    
    ExpensiveObject(ExpensiveObject&& other) noexcept : large_data(std::move(other.large_data)) {
        std::cout << "Expensive object moved" << std::endl;
    }
};

std::vector<ExpensiveObject> container;

// push_back: 构造临时对象 + 移动
container.push_back(ExpensiveObject(1000));

// emplace_back: 直接构造，更高效
container.emplace_back(1000);

4. 新增STL算法

📖 理论讲解

现代C++为STL算法库增加了许多实用的算法，特别是条件检查算法和搜索算法，让代码更加表达力强。

💡 条件检查算法

#include <algorithm>
#include <vector>

std::vector<int> numbers = {1, 3, 5, 7, 9, 2, 4, 6, 8, 10};

// 1. all_of - 检查是否所有元素都满足条件
bool all_positive = std::all_of(numbers.begin(), numbers.end(),
                                [](int n) { return n > 0; });

// 2. any_of - 检查是否有任何元素满足条件
bool has_even = std::any_of(numbers.begin(), numbers.end(),
                           [](int n) { return n % 2 == 0; });

// 3. none_of - 检查是否没有元素满足条件
bool no_negative = std::none_of(numbers.begin(), numbers.end(),
                               [](int n) { return n < 0; });

std::cout << "All positive: " << all_positive << std::endl;
std::cout << "Has even: " << has_even << std::endl;
std::cout << "No negative: " << no_negative << std::endl;

🚀 搜索和查找算法

// 1. find_if_not - 查找第一个不满足条件的元素
auto first_even = std::find_if_not(numbers.begin(), numbers.end(),
                                  [](int n) { return n % 2 == 1; });

// 2. copy_if - 复制满足条件的元素
std::vector<int> even_numbers;
std::copy_if(numbers.begin(), numbers.end(), std::back_inserter(even_numbers),
             [](int n) { return n % 2 == 0; });

// 3. partition_copy - 将元素分为两组
std::vector<int> odds, evens;
std::partition_copy(numbers.begin(), numbers.end(),
                   std::back_inserter(odds), std::back_inserter(evens),
                   [](int n) { return n % 2 == 1; });

// 4. is_sorted - 检查序列是否已排序
bool sorted = std::is_sorted(numbers.begin(), numbers.end());

// 5. is_partitioned - 检查是否已分区
bool partitioned = std::is_partitioned(numbers.begin(), numbers.end(),
                                      [](int n) { return n % 2 == 1; });

🎯 数值算法

#include <numeric>

// 1. accumulate的现代版本 - reduce（C++17）
int sum = std::accumulate(numbers.begin(), numbers.end(), 0);
int product = std::accumulate(numbers.begin(), numbers.end(), 1,
                             std::multiplies<int>());

// 2. iota - 生成递增序列
std::vector<int> sequence(10);
std::iota(sequence.begin(), sequence.end(), 1);  // 1, 2, 3, ..., 10

// 3. inner_product - 内积
std::vector<int> a = {1, 2, 3};
std::vector<int> b = {4, 5, 6};
int dot_product = std::inner_product(a.begin(), a.end(), b.begin(), 0);

// 4. adjacent_difference - 相邻差值
std::vector<int> differences;
std::adjacent_difference(numbers.begin(), numbers.end(),
                        std::back_inserter(differences));

5. 迭代器增强和全局函数

📖 理论讲解

现代C++引入了全局的begin、end等函数，提供了统一的接口来访问容器和数组的迭代器。

💡 全局迭代器函数

#include <iterator>

// 1. 全局begin/end函数
template<typename Container>
void print_container(const Container& c) {
    // 适用于STL容器和C风格数组
    for (auto it = std::begin(c); it != std::end(c); ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;
}

// 2. 使用示例
std::vector<int> vec = {1, 2, 3, 4, 5};
int arr[] = {6, 7, 8, 9, 10};

print_container(vec);  // STL容器
print_container(arr);  // C风格数组

// 3. 其他全局函数
auto vec_size = std::size(vec);     // C++17
auto arr_size = std::size(arr);     // C++17
bool vec_empty = std::empty(vec);   // C++17
auto vec_data = std::data(vec);     // C++17

🚀 迭代器适配器

// 1. 反向迭代器
std::vector<int> numbers = {1, 2, 3, 4, 5};
std::copy(numbers.rbegin(), numbers.rend(),
          std::ostream_iterator<int>(std::cout, " "));  // 5 4 3 2 1

// 2. 插入迭代器
std::vector<int> source = {1, 2, 3};
std::vector<int> dest;

// back_inserter - 在末尾插入
std::copy(source.begin(), source.end(), std::back_inserter(dest));

// front_inserter - 在开头插入（需要支持push_front的容器）
std::deque<int> deq;
std::copy(source.begin(), source.end(), std::front_inserter(deq));

// inserter - 在指定位置插入
std::vector<int> target = {10, 20, 30};
std::copy(source.begin(), source.end(),
          std::inserter(target, target.begin() + 1));

// 3. 流迭代器
// 从输入流读取
std::istringstream iss("1 2 3 4 5");
std::vector<int> from_stream;
std::copy(std::istream_iterator<int>(iss), std::istream_iterator<int>(),
          std::back_inserter(from_stream));

// 输出到流
std::copy(from_stream.begin(), from_stream.end(),
          std::ostream_iterator<int>(std::cout, " "));

6. 容器适配器的现代用法

📖 理论讲解

容器适配器（stack、queue、priority_queue）在现代C++中也得到了增强，支持更多的操作和更好的性能。

💡 stack的现代用法

#include <stack>

// 1. 基本操作
std::stack<int> st;
st.push(1);
st.push(2);
st.push(3);

std::cout << "Stack size: " << st.size() << std::endl;
while (!st.empty()) {
    std::cout << "Top: " << st.top() << std::endl;
    st.pop();
}

// 2. emplace操作（C++11）
std::stack<std::pair<int, std::string>> pair_stack;
pair_stack.emplace(1, "first");   // 直接构造pair
pair_stack.emplace(2, "second");

// 3. 自定义底层容器
std::stack<int, std::vector<int>> vector_stack;   // 使用vector作为底层
std::stack<int, std::deque<int>> deque_stack;     // 使用deque作为底层（默认）

🚀 queue和priority_queue

#include <queue>

// 1. queue的现代用法
std::queue<std::string> message_queue;
message_queue.emplace("First message");   // 直接构造string
message_queue.emplace("Second message");

while (!message_queue.empty()) {
    std::cout << "Processing: " << message_queue.front() << std::endl;
    message_queue.pop();
}

// 2. priority_queue的高级用法
// 默认是最大堆
std::priority_queue<int> max_heap;
max_heap.push(3);
max_heap.push(1);
max_heap.push(4);
max_heap.push(1);
max_heap.push(5);

std::cout << "Max heap: ";
while (!max_heap.empty()) {
    std::cout << max_heap.top() << " ";
    max_heap.pop();
}
std::cout << std::endl;

// 3. 自定义比较器的priority_queue
auto cmp = [](const std::pair<int, std::string>& a,
              const std::pair<int, std::string>& b) {
    return a.first > b.first;  // 最小堆（按first排序）
};

std::priority_queue<std::pair<int, std::string>,
                   std::vector<std::pair<int, std::string>>,
                   decltype(cmp)> min_heap(cmp);

min_heap.emplace(3, "three");
min_heap.emplace(1, "one");
min_heap.emplace(4, "four");

std::cout << "Min heap: ";
while (!min_heap.empty()) {
    auto [priority, value] = min_heap.top();  // C++17结构化绑定
    std::cout << "(" << priority << ", " << value << ") ";
    min_heap.pop();
}
std::cout << std::endl;

7. 自定义比较器和哈希函数

📖 理论讲解

为了在有序容器和无序容器中使用自定义类型，需要提供适当的比较器和哈希函数。

💡 自定义比较器

// 1. 函数对象比较器
struct Point {
    int x, y;
    Point(int x, int y) : x(x), y(y) {}
};

struct PointCompare {
    bool operator()(const Point& a, const Point& b) const {
        if (a.x != b.x) return a.x < b.x;
        return a.y < b.y;
    }
};

std::set<Point, PointCompare> ordered_points;
ordered_points.emplace(3, 4);
ordered_points.emplace(1, 2);
ordered_points.emplace(2, 3);

// 2. Lambda比较器
auto lambda_cmp = [](const Point& a, const Point& b) {
    return std::tie(a.x, a.y) < std::tie(b.x, b.y);  // 使用tie简化比较
};

std::set<Point, decltype(lambda_cmp)> lambda_set(lambda_cmp);

// 3. 成员函数指针比较器
struct Person {
    std::string name;
    int age;
};

std::vector<Person> people = {{"Alice", 25}, {"Bob", 30}, {"Charlie", 20}};

// 按年龄排序
std::sort(people.begin(), people.end(),
          [](const Person& a, const Person& b) { return a.age < b.age; });

// 按名字排序
std::sort(people.begin(), people.end(),
          [](const Person& a, const Person& b) { return a.name < b.name; });

🚀 自定义哈希函数

// 1. 特化std::hash
namespace std {
    template<>
    struct hash<Point> {
        std::size_t operator()(const Point& p) const noexcept {
            return std::hash<int>()(p.x) ^ (std::hash<int>()(p.y) << 1);
        }
    };
}

// 现在可以直接使用Point作为unordered_set的键
std::unordered_set<Point> point_set;
point_set.insert({1, 2});

// 2. 复合类型的哈希
struct Edge {
    Point from, to;
    
    bool operator==(const Edge& other) const {
        return from.x == other.from.x && from.y == other.from.y &&
               to.x == other.to.x && to.y == other.to.y;
    }
};

struct EdgeHash {
    std::size_t operator()(const Edge& e) const {
        auto h1 = std::hash<Point>()(e.from);
        auto h2 = std::hash<Point>()(e.to);
        return h1 ^ (h2 << 1);
    }
};

std::unordered_set<Edge, EdgeHash> edge_set;

// 3. 组合哈希函数
template<typename T>
void hash_combine(std::size_t& seed, const T& v) {
    std::hash<T> hasher;
    seed ^= hasher(v) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
}

struct ComplexKey {
    std::string str;
    int num;
    double val;
    
    bool operator==(const ComplexKey& other) const {
        return str == other.str && num == other.num && val == other.val;
    }
};

struct ComplexKeyHash {
    std::size_t operator()(const ComplexKey& k) const {
        std::size_t seed = 0;
        hash_combine(seed, k.str);
        hash_combine(seed, k.num);
        hash_combine(seed, k.val);
        return seed;
    }
};

🧪 实践练习

练习1：词频统计器

// 实现一个高效的词频统计器
class WordCounter {
public:
    void add_text(const std::string& text);
    void print_top_words(int n) const;
    std::vector<std::pair<std::string, int>> get_word_frequencies() const;
    
private:
    // 选择合适的容器类型
};

练习2：LRU缓存

// 使用STL容器实现LRU缓存
template<typename Key, typename Value>
class LRUCache {
public:
    LRUCache(size_t capacity);
    void put(const Key& key, const Value& value);
    std::optional<Value> get(const Key& key);
    
private:
    size_t capacity_;
    // 选择合适的数据结构
};

练习3：图的邻接表表示

// 使用现代STL容器实现图的邻接表
template<typename Vertex>
class Graph {
public:
    void add_vertex(const Vertex& v);
    void add_edge(const Vertex& from, const Vertex& to);
    std::vector<Vertex> get_neighbors(const Vertex& v) const;
    bool has_edge(const Vertex& from, const Vertex& to) const;
    
private:
    // 选择合适的容器组合
};

📝 本章小结

现代C++的STL增强为我们提供了更丰富、更高效的工具：

🎯 容器选择指南

需求推荐容器原因
固定大小数组std::array栈分配，性能最优
快速查找std::unordered_map/setO(1)平均时间复杂度
有序遍历std::map/set自动排序，O(log n)操作
频繁插入删除std::list/deque适合的内存布局
随机访问std::vector连续内存，缓存友好

🚀 性能优化技巧

  1. 使用emplace而非insert/push：减少临时对象创建
  2. 预分配容器空间：避免频繁的内存重分配
  3. 选择合适的容器：根据使用模式选择最优容器
  4. 自定义哈希函数：为用户类型提供高效哈希
  5. 利用移动语义：减少不必要的拷贝操作

🎯 最佳实践

  • 优先使用STL算法而非手写循环
  • 为自定义类型提供合适的比较器和哈希函数
  • 使用范围for循环和auto简化代码
  • 利用结构化绑定提高代码可读性
  • 注意容器的异常安全性

STL容器和算法的现代化增强让C++编程变得更加高效和表达力强，掌握这些特性是现代C++开发的重要基础。

🔗 相关资源

# c++
Logo
码道开发者社区

码道开发者社区，聚焦华为云码道 CodeArts 代码智能体，沉淀 Agent、Skill、鸿蒙开发实战内容，供开发者查阅资料、交流技术、分享工程实践

更多推荐

cover

状态丢失排障：Claude 持久记忆的跨会话局限与知芽 Notebook Skill 单元记忆如何沉淀可复用知识资产

avatar 码道开发者社区
cover

GitHub不再让一个模型写到底：HydraFusion多模型编排，官方评测成本降低67%

avatar 码道开发者社区
cover

【AI智能体】Codex 制作RAG知识库应用实战操作详解

avatar 码道开发者社区