提高组大纲2.2.2 C++程序设计

作者： 作者的头像   huolong , 时间：2026-08-16 21:36:53 , 所有人可见, 阅读  43

C++11 面向对象与 STL 模板讲义

本讲义重点剖析 C++11 中的面向对象编程（类与运算符重载）以及标准模板库（STL）的高级容器与算法。所有设计与代码实现均严格符合 C++11 标准，旨在帮助学习者建立深度的语言机制理解与高效的算法实现能力。

1. 类 (Class)

类是 C++ 面向对象编程的核心机制。它将数据（属性）与操作这些数据的函数（行为）封装在一起。

1.1 类的概念与简单应用

类可以看作是用户自定义的一种复合数据类型，它通过访问修饰符实现封装性。

1. 访问控制

  • public：外部代码可以自由访问的成员。
  • private：仅在类内部的成员函数可以访问，外部代码无法直接读取或修改，以此实现信息隐藏。
  • protected：类内部及派生类（子类）可以访问。

2. 构造函数与析构函数

  • 构造函数 (Constructor)：在对象被创建时自动调用，用于初始化成员变量。支持重载。
  • 析构函数 (Destructor)：在对象生命周期结束、被销毁时自动调用，用于释放对象占用的资源（如堆内存）。
C++11 类定义示例
#include <iostream>
#include <string>

class Student {
private:
    int id;
    std::string name;

public:
    // 构造函数与 C++11 成员初始化列表
    Student(int t_id, std::string t_name) : id(t_id), name(t_name) {}

    // 默认构造函数
    Student() : id(0), name("Unknown") {}

    // 析构函数
    ~Student() {
        // 在此处释放动态内存或资源
    }

    // 成员函数
    void display() const { // 使用 const 修饰，保证函数内不修改成员变量
        std::cout << "ID: " << id << ", Name: " << name << "\n";
    }
};

1.2 成员函数和运算符重载

运算符重载允许用户自定义内置运算符（如 +, -, <, == 等）在操作自定义类对象时的行为。这对于将自定义对象存入标准容器（如 std::set、std::priority_queue）至关重要。

1. 重载规则与准则

  • 不能创建新的运算符。
  • 重载后的运算符不能改变其原本的操作数个数。
  • 不能改变运算符的优先级与结合性。

2. 常用的运算符重载：关系运算符

将自定义结构体放入关联容器时，必须重载小于号 < 运算符。

示例：二维点坐标的比较与排序

在 $x$ 轴坐标不同时按 $x$ 升序排序，在 $x$ 相同的情况下按 $y$ 升序排序。

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

class Point {
public:
    int x, y;

    Point(int tx, int ty) : x(tx), y(ty) {}

    // 重载小于号：必须使用 const 修饰参数，且函数本身也需是 const
    // 满足严格弱序 (Strict Weak Ordering)
    bool operator<(const Point& other) const {
        if (x != other.x) {
            return x < other.x;
        }
        return y < other.y;
    }
};

int main() {
    std::vector<Point> points = {{3, 5}, {1, 2}, {3, 2}, {2, 8}};

    // 使用 std::sort 排序时，会自动调用重载的 operator<
    std::sort(points.begin(), points.end());

    for (const auto& p : points) {
        std::cout << "(" << p.x << ", " << p.y << ") ";
    }
    std::cout << "\n"; // 输出 (1, 2) (2, 8) (3, 2) (3, 5)
    return 0;
}

2. STL 模板与迭代器基础

2.1 容器与迭代器的核心设计思想

标准模板库（STL）将容器（数据结构）与算法解耦。而迭代器（Iterator）则充当了两者之间的桥梁，提供了一种统一访问容器中元素的方法，而无需暴露容器底层的存储细节。

迭代器的五种分类

  1. 输入迭代器 (Input Iterator)：只读，单向移动。
  2. 输出迭代器 (Output Iterator)：只写，单向移动。
  3. 前向迭代器 (Forward Iterator)：读写，单向移动。
  4. 双向迭代器 (Bidirectional Iterator)：读写，双向移动（支持 ++ 和 --）。如 std::set、std::list。
  5. 随机访问迭代器 (Random Access Iterator)：读写，支持在 $O(1)$ 时间内跨越任意步长（支持 ++, --, + n, - n, []）。如 std::vector、std::deque。

3. STL 高级工具与关联容器

3.1 std::pair 与 std::tuple

1. std::pair（对）

用于存储两个不同类型的值。在内部，其两个成员分别命名为 first 和 second。 * 性质：std::pair 默认实现了关系运算符。比较规则是先对比 first，若 first 相等，再对比 second。

2. std::tuple（元组）

C++11 引入的通用结构，可以将任意数量、不同类型的元素组合在一起。 * 操作： * 创建：std::make_tuple(...)。 * 读取：使用 std::get<Index>(tuple_name)。 * 解包（拆分值）：使用 std::tie(var1, var2, ...) = tuple_name。

#include <iostream>
#include <utility>
#include <tuple>
#include <string>

void tuple_demo() {
    // 1. std::pair
    std::pair<int, std::string> p = std::make_pair(1, "Apple");
    std::cout << p.first << ": " << p.second << "\n";

    // 2. std::tuple (C++11)
    auto t = std::make_tuple(101, "Bob", 98.5);

    // 读取元素
    std::cout << "ID: " << std::get<0>(t) << ", Score: " << std::get<2>(t) << "\n";

    // 利用 std::tie 进行解包
    int id;
    std::string name;
    double score;
    std::tie(id, name, score) = t; 
}

3.2 std::set 与 std::multiset

1. 概念与底层结构

  • std::set：集合。内部元素自动保持有序（默认升序），且不允许重复元素。
  • std::multiset：多重集合。允许存储重复元素，并保持有序。
  • 底层：两者底层均采用红黑树（Red-Black Tree）实现。由于红黑树的高自平衡性质，插入、删除、查找操作的时间复杂度均为 $O(\log n)$。

2. 常用操作

  • insert(val)：插入元素。
  • find(val)：查找元素，若找到则返回其迭代器，否则返回 end()。
  • erase(val) / erase(iterator)：删除元素。
  • lower_bound(val)：返回第一个大于或等于 val 的元素的迭代器。
  • upper_bound(val)：返回第一个严格大于 val 的元素的迭代器。

3. multiset 删除时的易错点（陷阱）

  • s.erase(val)：会删除集合中所有值为 val 的元素。
  • s.erase(s.find(val))：只会删除单个值为 val 的元素（通过迭代器进行定向删除）。
#include <iostream>
#include <set>

void set_demo() {
    std::multiset<int> ms = {2, 5, 5, 5, 8};

    // 错误示范：ms.erase(5) 会把三个 5 全部删掉
    // 正确删除单个 5：
    auto it = ms.find(5);
    if (it != ms.end()) {
        ms.erase(it); // 只删去一个 5
    }

    for (int x : ms) std::cout << x << " "; // 输出 2 5 5 8
    std::cout << "\n";
}

3.3 std::deque 与 std::priority_queue

1. 双端队列 (std::deque)

deque（Double-ended queue）支持在头部和尾部以 $O(1)$ 的时间复杂度进行插入和删除。 * 物理结构：与 std::vector 的单一连续内存块不同，deque 是由多个分段连续的内存块（Chunk）组合而成的双向映射结构。它支持随机访问（即可以通过 [] 快速定位），但随机访问的实际效率略低于 vector。

2. 优先队列 (std::priority_queue)

优先队列本质上是一个二叉堆（Binary Heap）。其最显著特征是：队列中最大的元素（默认情况下）总是位于队头（堆顶）。 * 复杂度：插入和删除的时间复杂度为 $O(\log n)$，获取堆顶（top()）的复杂度为 $O(1)$。 * 定义格式： * 大顶堆（默认）：std::priority_queue<int> max_heap; * 小顶堆：std::priority_queue<int, std::vector<int>, std::greater<int>> min_heap;

#include <iostream>
#include <queue>
#include <vector>

void priority_queue_demo() {
    // 显式声明小顶堆
    std::priority_queue<int, std::vector<int>, std::greater<int>> pq;
    pq.push(30);
    pq.push(10);
    pq.push(20);

    while (!pq.empty()) {
        std::cout << pq.top() << " "; // 输出 10 20 30
        pq.pop();
    }
    std::cout << "\n";
}

3.4 std::map 与 std::multimap

map 是关联容器，存储“键-值”（Key-Value）对，内部通过键（Key）自动保持有序。

1. 常用操作与性质

  • 底层同为红黑树，插入、删除、查找键的复杂度均为 $O(\log n)$。
  • std::map 中的键不可重复，而 std::multimap 中的键可以重复。

2. operator[] 的副作用与防范

在 std::map 中，我们可以直接通过 m[key] = value 进行赋值。但必须注意： * 如果读取一个不存在的键（例如 int val = m[non_exist_key];），map 会自动在容器中插入该键，并将值初始化为默认值（如0），这会无意间增加容器的大小。 * 安全做法：读取前，先用 m.count(key) 或 m.find(key) 进行校验。 * 注意：std::multimap 没有重载 operator[]，只能通过 insert 插入 std::pair。

#include <iostream>
#include <map>
#include <string>

void map_demo() {
    std::map<std::string, int> ages;
    ages["Alice"] = 20;

    // 不推荐的做法：直接读取不存在的键，会导致ages大小增至2
    // int age = ages["Bob"]; 

    // 推荐做法：安全检索
    std::string target = "Bob";
    if (ages.find(target) != ages.end()) {
        std::cout << target << "'s age is " << ages[target] << "\n";
    } else {
        std::cout << target << " not found.\n";
    }
}

3.5 位集合 (std::bitset)

bitset 可以看作是一个仅存储 0 或 1 的紧凑型数组，能够极大地压缩内存空间。

1. 空间效率

在 C++ 中，bool 变量占用 1 字节（8 位）的内存，而 bitset 每一个元素在物理层只占用 1 位（Bit），空间开销缩减到原来的 $\frac{1}{8}$。

2. 运算效率

bitset 支持位移运算（<<, >>）及位逻辑运算（&, |, ^）。由于它采用按机器字长（32位或64位）并行处理的优化机制，其位运算的速度大约是普通循环的 32 或 64 倍。这一性质常在状态压缩、连通性判定等算法中作为高效率工具。

3. 常用操作

  • set(pos)：将第 pos 位置为 1（若不传参，则全部置为 1）。
  • reset(pos)：将第 pos 位置为 0。
  • flip(pos)：翻转第 pos 位。
  • count()：返回 1 的个数。
  • any()：若存在 1，返回 true。
  • none()：若不存在 1，返回 true。
#include <iostream>
#include <bitset>

void bitset_demo() {
    std::bitset<8> b; // 定义长度为 8 的位集合，初始化为 00000000
    b.set(2);         // 变为 00000100 (低位在右侧)
    b.set(4);         // 变为 00010100

    std::cout << "bitset: " << b << "\n";
    std::cout << "Count of 1s: " << b.count() << "\n"; // 输出 2

    std::bitset<8> b_another("00001100");
    auto combined = b & b_another; // 位与运算：00000100
    std::cout << "Combined AND: " << combined << "\n";
}

3.6 算法模板库中的常用函数

C++ 引入了大量高度优化的泛型算法函数：

  1. std::lower_bound / std::upper_bound：
    • 在已排序区间内进行二分查找。
    • lower_bound(beg, end, val)：返回第一个 $\ge$ val 的迭代器。
    • upper_bound(beg, end, val)：返回第一个 $>$ val 的迭代器。
  2. std::unique：
    • 将相邻的重复元素移到区间末尾。若要实现全局去重，必须先用 sort 排序，之后配合 erase 物理清空尾部冗余部分。
    • vec.erase(std::unique(vec.begin(), vec.end()), vec.end());
  3. std::next_permutation / std::prev_permutation：
    • 获取当前序列按字典序排列的下一个/上一个全排列。
    • 若想获取所有全排列，起始数组必须呈升序状态。
  4. std::nth_element：
    • 在 $O(n)$ 时间内对区间进行局部排序，使第 $k$ 小的元素处于第 $k$ 个位置。它能以接近线性的极高速度找出中位数或第 $k$ 极值。
#include <iostream>
#include <vector>
#include <algorithm>

void algorithm_demo() {
    std::vector<int> v = {1, 3, 3, 3, 5, 7};

    // 1. lower_bound/upper_bound
    auto low = std::lower_bound(v.begin(), v.end(), 3); // 指向第一个 3
    auto up = std::upper_bound(v.begin(), v.end(), 3);   // 指向 5
    std::cout << "Count of 3s: " << (up - low) << "\n";  // 输出 3

    // 2. 全排列演示
    std::vector<int> p = {1, 2, 3};
    do {
        for (int x : p) std::cout << x << " ";
        std::cout << "| ";
    } while (std::next_permutation(p.begin(), p.end()));
    std::cout << "\n";
}

4. 综合练习题与解析

练习题 1：利用映射实现离散化（坐标压缩）

题目描述： 在 $1 \times 10^9$ 的数轴上有 $N$ 个点被标记了权值。因为 $N \le 10^5$ 较小，而坐标范围极大，我们无法直接开辟如此巨大的数组。 请编写一个程序，读入 $N$ 个点的坐标，将它们在保证原有相对大小关系不变的情况下，映射（压缩）到 $[0, N-1]$ 的紧凑区间内，并输出每个原始坐标压缩后的新索引值。

C++11 实现与解析

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

// 求解函数
void coordinate_compression(const std::vector<int>& raw_coords) {
    // 1. 利用 std::set 自动去重并升序排序的特征进行初步整理
    std::set<int> ordered_set(raw_coords.begin(), raw_coords.end());

    // 2. 将整理后的每一个不重复坐标映射至从 0 开始的排名
    std::map<int, int> rank_map;
    int rank = 0;
    for (int coord : ordered_set) {
        rank_map[coord] = rank++;
    }

    // 3. 输出原始坐标对应的排名
    std::cout << "Compressed coordinates: \n";
    for (int coord : raw_coords) {
        std::cout << coord << " -> " << rank_map[coord] << "\n";
    }
}

int main() {
    // 原始坐标范围很大且不连续
    std::vector<int> raw = {1000000000, 250, 1000000000, 5000, 250};
    coordinate_compression(raw);
    return 0;
}

解题思路： 离散化（坐标压缩）是信息学竞赛中处理稀疏大维空间数据的常用技巧。 1. 首先，我们把坐标全部塞入 std::set。借由红黑树性质，集合会自动剔除重复项，并把剩余的物理位置按从小到大排好，时间复杂度为 $O(N \log N)$。 2. 随后，我们用一个顺序循环提取出集合中的元素，依次绑定到自增的整型变量 rank（从 0 开始），存入关联容器 std::map<int, int> 中。 3. 最后，通过 $O(\log N)$ 的时间复杂度对每一个原始坐标直接查询其对应的离散化索引。整体算法框架简洁，有助于提高代码的实现效率。

练习题 2：使用优先队列和哈希表求解动态中位数

题目描述： 设计一个数据结构，支持以下两个操作： 1. add_num(int num)：向数据结构中添加一个整数。 2. find_median()：返回当前所有已添加元素的中位数。 若元素总数为奇数，返回中间那个数；若元素总数为偶数，返回中间偏左那个数（例如有 4 个数，排序后为 1, 2, 3, 4，返回 2）。

C++11 实现与解析

#include <iostream>
#include <queue>
#include <vector>

class MedianFinder {
private:
    // 大顶堆，存储所有数字中较小的一半
    std::priority_queue<int, std::vector<int>, std::less<int>> max_heap;
    // 小顶堆，存储所有数字中较大的一半
    std::priority_queue<int, std::vector<int>, std::greater<int>> min_heap;

public:
    MedianFinder() {}

    void add_num(int num) {
        // 1. 如果大顶堆为空，或者当前值小于大顶堆堆顶，则放入大顶堆
        if (max_heap.empty() || num <= max_heap.top()) {
            max_heap.push(num);
        } else {
            min_heap.push(num);
        }

        // 2. 调整两个堆的平衡性
        // 我们约定让大顶堆（max_heap）存储的元素个数可以等于小顶堆，
        // 或者比小顶堆多一个（当总数为奇数时，中位数即为大顶堆堆顶）
        if (max_heap.size() > min_heap.size() + 1) {
            min_heap.push(max_heap.top());
            max_heap.pop();
        } else if (min_heap.size() > max_heap.size()) {
            max_heap.push(min_heap.top());
            max_heap.pop();
        }
    }

    int find_median() const {
        // 由于调整机制保证了大顶堆的大小始终 >= 小顶堆的大小
        // 奇数时大顶堆多一个，中位数即为大顶堆顶
        // 偶数时两堆一样大，由于题目要求偏左的值，依然是大顶堆顶
        if (max_heap.empty()) return 0;
        return max_heap.top();
    }
};

int main() {
    MedianFinder finder;
    finder.add_num(5);
    finder.add_num(1);
    std::cout << "Current median: " << finder.find_median() << "\n"; // 排序后：[1, 5]，返回 1

    finder.add_num(8);
    std::cout << "Current median: " << finder.find_median() << "\n"; // 排序后：[1, 5, 8]，返回 5

    finder.add_num(3);
    std::cout << "Current median: " << finder.find_median() << "\n"; // 排序后：[1, 3, 5, 8]，返回 3
    return 0;
}

解题思路： 本题若每次在查找中位数时进行完整排序，其时间复杂度为 $O(n \log n)$，在频繁调用时会面临运行时间长的局限。 因此，本算法采用“对顶堆”设计策略： * 我们用两个堆来动态瓜分所有的数字。左边的大顶堆存放前半部分较小的数，右边的小顶堆存放后半部分较大的数。 * 通过设定两堆大小的严格约束：$size(max_heap) \in [size(min_heap), size(min_heap) + 1]$。只要不满足这一比例，就通过把一侧的堆顶转移到另一侧来实现平衡。 * 这样，中位数的信息总是能以 $O(1)$ 的时间复杂度从大顶堆的堆顶直接读取。每次数据插入的开销也仅为堆调整的 $O(\log n)$，整体时间性能较为优秀。

—— 本文来自火龙信奥（义乌睿码科技）：义乌青少年信息学奥赛与编程教育平台，专注 CSP-J/S、NOIP、GESP 竞赛培训，线上线下融合教学，助力编程升学。网址：hlcoding.com