HespethornのBlog

一、函数对象的本质函数对象（也称为仿函数，Functor）是*重载了函数调用运算符***operator()**的类或结构体的实例。这种特殊的设计使它能够像普通函数一样被调用，同时又具备对象的所有特性。 12345678910111213141516// 一个简单的函数对象类struct Add { // 重载函数调用运算符 int operator()(int a, int b) const { return a + b; }};// 使用方式int main() { Add add; int result = add(3, 5); // 像函数一样调用对象 // 也可以直接使用临时对象 int result2 = Add()(10, 20); return 0;} 从本质上讲，函数对象是一个带行为的对象，而普通函数是一段可执行代码。这种本质差异决定了它们在功能和适用场景上的不同。 二、函数对象与普通函数的核心区别2.1...

导言在现代 C++ 开发中，lambda 表达式（匿名函数）已经成为编写简洁高效代码的重要工具。尤其在配合 STL 算法（如for_each）时，lambda 表达式能够消除编写命名函数或函数对象的额外开销，使代码更加紧凑直观。 一、Lambda 表达式的基本语法lambda 表达式的完整语法结构如下： 123[capture](parameters) mutable noexcept -> return_type { // 函数体} 各组成部分的含义： [capture]：捕获列表，定义 lambda 表达式可以访问的外部变量 (parameters)：参数列表，与普通函数的参数列表类似 mutable：可选修饰符，允许修改按值捕获的变量 noexcept：可选修饰符，指定函数不会抛出异常 -> return_type：返回类型，当函数体只有 return 语句时可省略 {}：函数体，包含具体的执行逻辑 1.1 最简单的 Lambda 表达式最简化的 lambda...

导言堆排序是一种基于二叉堆数据结构的高效排序算法，具有 O (n log n) 的时间复杂度和原地排序的特性。使用模板实现堆排序可以使其灵活适用于各种数据类型，并支持自定义比较规则。 一、堆排序算法原理堆排序主要分为两个阶段： 建堆阶段：将无序数组构建成一个二叉堆（最大堆或最小堆） 排序阶段：反复提取堆顶元素（最大值或最小值），并调整剩余元素维持堆特性 二叉堆是一种完全二叉树，对于最大堆，每个父节点的值大于或等于其子节点的值；对于最小堆，每个父节点的值小于或等于其子节点的值。 二、模板类实现下面是完整的HeapSort模板类实现，基于提供的框架结构： 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788#include <vector>#include...

一、引言上一篇文章介绍了unordered_map存放自定义类型的六种方法的理论框架，本文将通过完整可运行的代码示例，详细展示每种方法的具体实现细节。这六种方法是通过 2 种哈希实现方式与 3 种相等性比较方式组合而成，每种组合都有其独特的实现要点。 二、基础准备首先定义基础的Point类和测试函数，作为六种方法的共同基础： 12345678910111213141516171819202122232425262728293031323334353637383940#include <iostream>#include <unordered_map>#include <string>#include <functional>// 自定义点类型class Point {private: int x; int y;public: Point(int x_ = 0, int y_ = 0) : x(x_), y(y_) {} int getX() const {...

导言快速排序是一种高效的分治排序算法，平均时间复杂度为 O (n log n)。使用 C++ 模板实现快速排序可以使其适用于各种数据类型，配合比较器还能灵活调整排序规则。 一、快速排序算法原理快速排序的核心思想是： 选择一个元素作为 "基准"(pivot) 将数组分区，所有比基准值小的元素移到基准前面，比基准值大的元素移到基准后面 递归地对前后两个子数组进行排序 这种分治策略使快速排序成为实际应用中最快的排序算法之一。 二、模板类实现下面是完整的MyQsort模板类实现，支持任意可比较的数据类型和自定义比较规则： 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687#include <vector>#include <functional>#include...

引言std::unordered_map是 C++ 标准库中提供的无序关联容器，与std::map不同，它通过哈希表实现，因此需要两个关键组件：哈希函数（用于计算键的哈希值）和相等性比较函数（用于判断两个键是否相等）。当使用自定义类型作为unordered_map的键时，我们需要显式提供这两种组件。 一、核心概念std::unordered_map的模板定义如下： 1234567template< class Key, class T, class Hash = std::hash<Key>, // 哈希函数类型 class KeyEqual = std::equal_to<Key>, // 相等性比较类型 class Allocator = std::allocator<std::pair<const Key, T>>> class unordered_map; Hash类型必须满足Hash概念：Hash对象的operator()接受const...

一、关联式容器与无序关联容器的核心区别关联式容器（如set、map、multiset、multimap）和无序关联式容器（如unordered_set、unordered_map、unordered_multiset、unordered_multimap）是 C++ STL 中两种不同的数据结构，核心区别在于底层实现和特性： 关联式容器：基于红黑树（一种自平衡二叉搜索树）实现，元素按照键（key）的有序性存储，默认通过less比较键的大小。 无序关联式容器：基于哈希表实现，元素存储顺序与键的大小无关，依赖哈希函数计算存储位置，通过键的哈希值快速访问元素。 二、如何选择：关联式容器 vs 无序关联式容器选择需根据具体场景的需求，主要从以下维度判断： 2.1 有序性需求 需要元素有序：优先选择关联式容器。例如： 需遍历元素时按键的大小排序（如set遍历默认升序）； 需频繁执行范围查询（如map::lower_bound、map::upper_bound获取键在[a, b]之间的元素）。 无需有序性：优先选择无序关联式容器，其插入、查找、删除的平均效率更高。 2.2...

引言C++ 标准模板库（STL）提供了一系列功能丰富的容器，这些容器不仅封装了数据结构，还提供了大量成员函数用于操作数据。此外，STL 还包含许多与容器配合使用的非成员函数，它们扩展了容器的功能，使操作更加灵活。 一、通用成员函数几乎所有 STL 容器都提供了一组基础的通用成员函数，用于获取容器信息、修改容器状态等。 1.1 基本信息函数12345678910111213141516171819202122#include <iostream>#include <vector>#include <list>int main() { std::vector<int> vec = {1, 2, 3, 4, 5}; std::list<std::string> lst = {"apple", "banana", "cherry"}; // 容器大小相关 std::cout...

引言在 C++ 中使用std::map存储自定义类型作为键时，需要确保该类型能够被正确比较大小，因为std::map是一个有序关联容器，其内部通过比较操作来组织元素。本文将介绍三种方法来解决map中存放pair<Point, string>元素的问题，其中Point是一个自定义点类型。 核心概念std::map要求其键类型必须支持比较操作（默认使用<运算符）。对于自定义类型Point，我们需要通过以下三种方式之一提供比较能力： 为Point类重载<运算符 定义一个比较结构体（仿函数） 为Point准备std::less的特化模板 代码示例首先定义基础的Point类： 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051#include <math.h>#include <iostream>#include <set>using std::cout;using...

引言在 C++ 中，迭代器 (iterator) 和指针 (pointer) 是两个密切相关但又有所区别的概念。它们都可以用来访问内存中的数据，都支持类似的操作符 (如*和->)，但应用场景和功能范围却有显著差异。本文将深入解析迭代器与指针的关系、区别及各自的应用场景。 核心概念指针的本质指针是 C++ 从 C 语言继承而来的概念，是一个变量，其值为另一个变量的内存地址。指针直接指向内存中的某个位置，可以是： 普通变量的地址 数组元素的地址 动态分配内存的地址 函数的地址 迭代器的本质迭代器是 C++ 标准库提供的一种抽象，它模拟了指针的行为，为各种容器提供了统一的访问接口。迭代器可以看作是...

一、remove_if 算法原理与实现细节1.1 核心功能与特性remove_if是 C++ 标准库中用于条件过滤的算法，它能移除容器中满足特定条件的元素。需要特别注意的是： 执行的是逻辑删除而非物理删除 不会改变容器的大小（size） 返回指向新的逻辑末尾的迭代器 1.2 底层实现逻辑123456789101112131415// 模拟标准库remove_if实现逻辑template<class ForwardIt, class UnaryPredicate>ForwardIt remove_if(ForwardIt first, ForwardIt last, UnaryPredicate p) { // 跳过不符合删除条件的元素 first = std::find_if(first, last, p); if (first != last) { // 用后面的元素覆盖需要删除的元素 for (ForwardIt i = std::next(first); i != last; ++i)...

一、基础概念与设计原理在 C++ 开发中，std::unique_ptr与std::vector组合是动态内存管理的常用方案，既灵活又安全。unique_ptr独占所有权的特性，使其与容器存储场景天然适配，容器全权负责指针生命周期。 二、完整实现示例1. 定义基础类定义Point类，包含虚析构函数以支持多态： 123456789101112131415161718#include <iostream>#include <vector>#include <memory> class Point {private: int x_; int y_;public: Point(int x = 0, int y = 0) : x_(x), y_(y) { std::cout << "Point构造: (" << x_ << "," << y_ << ")" <<...

导言LRU（Least Recently Used，最近最少使用）算法是一种常用的缓存淘汰策略，其核心思想是：当缓存空间满时，优先淘汰最近最少使用的元素。在 C++ 中，结合list容器的splice()函数可以高效实现 LRU 算法，因为splice()能以 O (1) 的时间复杂度调整元素位置，非常适合维护元素的访问顺序。 一、LRU 算法的核心需求实现 LRU 算法需要支持以下操作： 访问元素：如果元素存在于缓存中，将其标记为 “最近使用”；如果不存在，需要插入新元素。 插入元素：当缓存未满时直接插入；当缓存已满时，删除 “最近最少使用” 的元素后再插入新元素。 维护顺序：始终保持元素的排列顺序与访问时间相关（最近使用的在前端，最少使用的在末端）。 二、数据结构设计为了高效实现 LRU，我们需要两种数据结构配合： list容器：用于存储缓存元素，最近使用的元素放在链表头部，最少使用的放在尾部。 unordered_map容器：用于快速查找元素在list中的位置（存储元素键与list迭代器的映射），支持 O (1)...

一、sort ()：容器元素的排序利器sort()是 C++ 标准库中用于排序的函数，其核心功能是对容器中的元素进行升序或自定义规则排序。不过，并非所有容器都支持sort()，它仅适用于随机访问迭代器的容器（如vector、deque、array等），而像list、set等容器则有自己的排序方式。 1. 基本用法sort()的函数原型如下（以vector为例）： 1234567#include <algorithm> // 需包含算法库// 升序排序（默认）sort(begin_iterator, end_iterator);// 自定义排序规则sort(begin_iterator, end_iterator, comparator); 其中，begin_iterator和end_iterator指定排序的范围（左闭右开），comparator是一个自定义的比较函数或 lambda 表达式，用于定义排序规则。 2. 实战示例 默认升序排序： 12345678910111213#include <vector>#include...

一、erase 方法的功能定位vector 的 erase 方法是 STL 中用于从容器中移除元素的核心函数，其主要功能是： 从 vector 中删除单个元素或一段连续范围内的元素 调整容器大小以反映元素数量的变化 维护剩余元素的连续性和内存布局 返回一个迭代器，指向被删除元素的下一个元素 erase 方法是破坏性操作，会改变容器的状态和内部布局，同时可能影响现有迭代器的有效性。 二、迭代器参数的语法特征与使用场景vector 的 erase 方法有两种重载形式，分别适用于不同的删除场景： 2.1 单个元素删除1iterator erase(iterator position); 参数：指向要删除元素的迭代器 返回值：指向被删除元素下一个元素的有效迭代器 使用场景：已知要删除元素的确切位置时 2.2 范围元素删除1iterator erase(iterator first, iterator...

一、内部实现机制 vector：基于动态数组实现，元素存储在连续的内存空间中，通过单一指针管理内存块 list：基于双向链表实现，每个元素包含数据域和两个指针域（前驱和后继），元素分散存储在内存中 二、核心性能差异 操作 vector list 随机访问（按索引访问） O (1)，高效支持 O (n)，不支持直接索引访问 头部插入 / 删除 O (n)，需移动所有元素 O (1)，只需调整指针 尾部插入 / 删除 O (1)（平均） O(1) 中间插入 / 删除 O (n)，需移动插入点后的所有元素 O (1)，只需调整附近元素的指针 内存分配 可能需要整体扩容（复制所有元素） 每次插入新元素单独分配内存 迭代器类型 随机访问迭代器 双向迭代器 缓存利用率 高（连续内存，缓存局部性好） 低（元素分散，容易缓存失效） 三、功能差异 vector： 支持[]运算符和at()方法进行随机访问 提供reserve()方法预分配内存 元素在内存中连续存储，可直接获取数据指针（data()方法） 适合与 C API...

导言deque（双端队列）是另一种常用的序列容器，与 vector 相比，它在两端的插入删除操作上有独特优势。以下是 deque 高效操作的策略和特性： 一、deque 的特性与优势deque 与 vector 的核心区别在于内存布局： deque 采用分段连续内存结构，由多个固定大小的内存块组成 支持 O (1) 时间复杂度的两端插入和删除操作 不需要像 vector 那样在扩容时复制所有元素 二、高效插入元素 两端插入效率最高deque 在头部和尾部的插入操作都是 O (1) 时间复杂度，这是它相比 vector 的主要优势： 123456789std::deque<int> dq;// 尾部插入dq.push_back(10);dq.emplace_back(20); // 更高效，直接构造// 头部插入（vector不擅长的操作）dq.push_front(5);dq.emplace_front(3); // 直接在头部构造 中间插入的特点与 vector 类似，deque 的中间插入仍需移动元素，时间复杂度为 O (n)，但实际性能可能略优于...

一、vector 容器概述vector 是 C++ 标准模板库（STL）中 最用的序列容器之一，它基于动态数组实现，能够存储同类型元素并支持高效的随机访问。自 C++98 标准首次引入以来，vector 凭借其灵活的内存管理和优秀的性能表现，成为了 C++ 开发者处理动态数据集合的首选工具。 与静态数组相比，vector 的核心优势在于自动内存管理—— 它会根据元素数量动态调整内部存储空间，无需开发者手动分配和释放内存。这种特性使得 vector 在处理元素数量不确定的场景时尤为便捷，同时保持了数组的随机访问效率。 vector 的核心特性可以概括为： 连续的内存空间分配，支持随机访问 动态扩容机制，自动管理内存 尾部插入 / 删除操作效率高 中间插入 / 删除操作可能导致大量元素移动 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566#include...

一、智能指针循环引用问题的处理1.1 循环引用的产生与危害循环引用是shared_ptr使用过程中最常见的问题之一，当两个或多个shared_ptr形成引用闭环时就会产生循环引用。这种情况下，每个shared_ptr的引用计数都无法降到 0，导致其所管理的对象无法被释放，最终造成内存泄漏。 典型的循环引用场景： 双向链表节点相互引用 父对象持有子对象的shared_ptr，子对象同时持有父对象的shared_ptr 观察者模式中，观察者与被观察者相互持有shared_ptr 1.2 循环引用示例12345678910111213141516171819202122232425262728293031#include <memory>#include <iostream>class B; // 前向声明class A {public: std::shared_ptr<B> b_ptr; A() { std::cout << "A constructed\n";...

一、引言引入智能指针（Smart Pointer）是 C++ 为解决动态内存管理问题而设计的工具，其核心目的是自动管理动态分配的内存（堆内存），避免手动管理内存时常见的错误（如内存泄漏、野指针、二次释放等），提高代码的安全性和健壮性。 二、智能指针基础2.1 具体解决的问题手动使用new分配内存和delete释放内存时，容易出现以下问题，而智能指针通过自动化机制解决了这些问题： 内存泄漏 手动管理时，若忘记调用delete释放已分配的内存，或因异常、分支跳转等导致delete未执行，会造成内存泄漏（内存被占用且无法回收）。 智能指针通过RAII（资源获取即初始化）...