堆（Heap）本质上是一种特殊的树状数据结构，通常用完全二叉树来实现。它的主要特点是满足“堆属性”： * 大顶堆 (Max-Heap): 任何一个父节点的值都大于或等于它的所有子节点的值。这意味着，堆的根节点（顶部）存放的是整个堆中的最大值。 * 小顶堆 (Min-Heap): 任何一个父节点的值都小于或等于它的所有子节点的值。这意味着，堆的根节点（顶部）存放的是整个堆中的最小值。 C++中的实现 (std::priority_queue) std::priority_queue 默认实现的是一个大顶堆。 * int: 存储的元素类型。 * std::vector<int>: 实现堆所用的底层容器，vector是默认且最常用的选项。 * std::greater<int>: 比较函数。默认是std::less<int>（产生大顶堆）…
for (declaration : range_expression) { // 循环体 (loop body) // 在这里可以使用 declaration 来访问 range_expression 中的当前元素 } * declaration: 声明一个变量，用于在每次迭代中存储 range_expression 中的一个元素。 * 这个变量的类型通常可以由编译器通过 range_expression 中元素的类型自动推断（使用 auto），或者你可以显式指定类型。 * 你可以声明为值 (type var)、引用 (type& var) 或常量引用 (const type& var)，具体取决于你是否需要修改元素以及是否希望避免不必要的拷贝。 * range_expression: 一个可以被迭代的对象，例如： * STL 容器（如 std::vector, std::string,…
1. 计算数据流的中位数 中位数是将一个数据集分成数量相等的上下两部分的值。我们的核心思想就是维护这两个“部分”。 核心思想：双堆 我们使用两个堆来模拟被中位数分开的数据集： 1. 一个大顶堆 (Max-Heap) small_half: 用于存储数据流中较小的那一半数字。堆顶是这一半数据中的最大值。 2. 一个小顶堆 (Min-Heap) large_half: 用于存储数据流中较大的那一半数字。堆顶是这一半数据中的最小值。 为了让这两个堆能够正确地“分割”数据流，我们必须始终维持两个不变的规则： 1. 大小平衡: 两个堆的大小要么相等，要么大顶堆 small_half 比小顶堆 large_half 多一个元素。这样可以确保中位数总是在两个堆的顶部产生。 2. 数值关系: 大顶堆 small_half 中的所有元素都必须小于或等于小顶堆 large_half 中的所有元素。 算法步骤 每当一个新的数据 num 到来时，…
* 左值 (lvalue, locator value): 可以放在赋值运算符=左边的表达式。它代表一个有身份 (identity) 的、持久的对象或内存位置。你可以对它取地址（使用 &）。 * 右值 (rvalue, read value): 只能放在赋值运算符=右边的表达式。它代表一个没有身份的、临时的值。你通常不能对它取地址。 更现代、更准确的理解是基于“身份”： * 左值：有一个持久的身份（identity），在表达式结束后依然存在。就像一个有门牌号的房子。 * 右值：是一个即将被销毁的临时值，没有持久的身份。就像你刚算出来的 2+3 的结果 5，这个 5 只是一个临时值。 左值 (lvalue) 左值是指定了内存中某个位置的表达式。 特征： 1. 有持久的内存地址。 2. 可以通过地址访问。 3.…
C++20 中最具变革性的特性之一：范围库 (Ranges Library)，彻底改变了我们与标准模板库（STL）算法交互的方式，使代码更具表现力、更简洁、也更安全。 1. C++20 之前的问题：迭代器 在 C++20 之前，几乎所有的 STL 算法都依赖于一对迭代器 (begin, end) 来指定要操作的元素序列。这种设计虽然灵活，但存在诸多痛点： * 冗长和重复：每次调用算法，你都需要传递 container.begin() 和 container.end()。这非常啰嗦。 * 容易出错：很容易意外地传递不匹配的迭代器对（例如，一个来自 vector1 的 begin 和一个来自 vector2 的 end），这会导致未定义行为。…
C++添加了<=>运算符，当使用 a <=> b 时，它返回的不是一个简单的布尔值 (true/false) 或整数。 它返回一个特殊的比较类别对象 (comparison category object)。这个对象封装了 a 和 b 之间详细的排序关系。这些对象的类型都定义在 <compare> 头文件中。 最核心的返回类型有三种： 1. std::strong_ordering (强有序) 2. std::weak_ordering (弱有序) 3. std::partial_ordering (偏序) 理解返回对象的本质：与 0 比较 理解这些返回对象最简单的方式，…
向量 ![[OJ-1#vector]] 栈 std::stack 是一种后进先出（Last-In, First-Out，简称 LIFO）的数据结构。你可以把它想象成一摞盘子：你只能在最上面放盘子，也只能从最上面取盘子。最后放上去的盘子，最先被取出来。 在 C++ 中，std::stack 并不是一个独立的容器，而是一个容器适配器（container adapter）。这意味着它是在其他现有容器类型（如 std::vector, std::deque, std::list）的基础上实现的，通过限制这些底层容器的接口，来提供特定的栈功能。默认情况下，std::stack 使用 std::deque 作为其底层容器。 头文件： C++ #include <stack>…
<iterator>类 迭代器的选择与种类 函数名 描述 begin() / cbegin() 返回指向数组第一个元素的迭代器。cbegin() 返回一个 const 迭代器。 end() / cend() 返回指向数组末尾之后位置的迭代器。cend() 返回一个 const 迭代器。 rbegin() / crbegin() 返回指向数组最后一个元素的反向迭代器。 rend() / crend() 返回指向数组第一个元素之前位置的反向迭代器。 迭代器的操作： 通用迭代器 std::advance(it, n) * it：要移动的迭代器（按引用传递，会被修改） * n：移动的步数（整数，正数向前，负数向后） 特点：直接修改传入的迭代器，并且适用于所有迭代器类型 向前移动迭代器std::next(it, n) * it：…