DSA

一、两类检索，两套解法做后端的同学应该都有体会：检索这件事，本质上分两种。 第一种是精确检索——"查 id = 10086 的记录"、"查工资在 1万~2万之间的员工"。结果必须一个不多、一个不少，错了就是事故。 第二种是近似检索——"找和这段文字意思最像的文档"、"找长得最像的这张脸"。结果只要**"差不多"就行**，漏掉一两个冷门候选完全可以接受，但速度必须快到毫秒级。 这两种需求，各自催生了各自的事实标准： 精确检索 → B+ 树（MySQL InnoDB、PostgreSQL、SQLite 的默认索引结构） 近似检索 → HNSW（Milvus、Weaviate、Qdrant、FAISS 的主流索引结构） 它们名字里都带个"树"或"图"，但设计哲学天差地别。这篇把它们放一起掰开揉碎地对比——搞清楚它们各自解决什么问题、为什么长成这样、什么时候该用哪个。 二、B+ 树：为磁盘而生的"多路平衡树"2.1 ...

一、为什么需要string_view作为一个 C++ 工程师，我相信很多人和我一样，写过无数次这样的代码： 12345678void process(const std::string& str) { // 只是读取，不修改 std::cout << str.size() << std::endl;}process("hello");process(std::string("world"));process(std::string_view("test")); 每次调用 process("hello") 时，都会创建一个临时的 std::string 对象，拷贝字符串内容，然后在函数结束时销毁它。这是一种不必要的开销。 同样的问题也存在于从 std::string 中截取子串时： 12std::string s = "hello world";std::string substr = s.substr(0, 5); ...

系列导读：本文是"检索与 RAG"系列的第二篇——在《RAG检索增强生成——让大模型学会翻书作答》认识了 RAG 之后，本文深挖 RAG 的检索环节：为什么纯 BM25 词法检索会"权重大但不相关"，以及两阶段检索如何救赎。本系列阅读顺序： 《RAG检索增强生成——让大模型学会翻书作答》（认识 RAG） 本文《权重大却不相关——BM25检索失效场景与两阶段救赎》（深挖检索环节） 《RAG原理就一句话——检索、拼接、加工》（回归本质） 一、一个让人抓狂的现象：分数越高，越不对前司做经典 OA 系统时，我负责文档检索模块。文章通过 BM25 分片、倒排索引计算权重，前端搜索按权重排序返回"相关性最高的文档"。 一开始很顺。直到有一天，运营同事拿着截图来找我： "搜'差旅报销流程'，排第一的是一篇《2024 年度行政费用总结》——里面'报销'两个字出现了 27 次。我们想看的《差旅费报销实施细则》，排到了第七页。" 我第一反应是权重算错了。查了一遍公式，没错——B...

一、从一个问路的场景说起假设你站在一个陌生城市的街头，想要去市中心的火车站。你手里没有地图，只有一个指南针和一张标注了火车站方向的简易示意图。 你会怎么走？ 大多数人的选择是：朝着火车站的方向走，遇到岔路口就选那条看起来更靠近火车站的路。你不会绕到城市的另一头去试探，也不会把所有的路都走一遍。你只做一件事——每一步都选择看起来离目标最近的方向。 这种"跟着感觉走"的策略，在计算机科学中就叫做贪婪最佳优先搜索（Greedy Best-First Search，简称GBFS）。它是启发式搜索算法家族中最直观、最简单的一员，也是理解更复杂搜索算法（如A*）的基础。 二、GBFS的核心思想2.1 什么是启发式搜索在介绍GBFS之前，我们先来理解一个关键概念：启发函数（Heuristic Function）。 传统的搜索算法（如BFS、DFS）就像是蒙着眼睛找路——它们只知道自己走过了哪里，却不知道目标在哪里。而启发式搜索则像是睁开了眼睛，它通过一个"启发函数"来估算当前位置到目标的距离，从而引导搜索方向。 用一个简单的公式来表示： 1f(n) = ...

在现代分布式系统和微服务架构中，Protocol Buffers（protobuf）是一种广泛使用的高效序列化协议。然而，当处理大型结构体时，如何设计合理的分段更新机制和同步策略成为关键问题。本文将深入探讨protobuf中构建大型结构体的最佳实践。 一、大型结构体的挑战1. 为什么需要分段更新在单体应用或小型系统中，完整的对象序列化与反序列化通常没有问题。但在大型分布式系统中，大型结构体面临诸多挑战： 12345678910111213// 大型配置结构体示例message LargeConfig { string application_name = 1; map<string, string> environment_vars = 2; repeated DatabaseConfig databases = 3; repeated ServiceEndpoint services = 4; SecurityConfig security = 5; LoggingConfig logging = 6; Monit...

deque（double-ended queue，双端队列）是STL中一种重要的序列容器。与vector相比，deque在头部和尾部的插入删除操作具有常数时间复杂度优势。本文将深入探讨deque的内部实现机制、使用场景以及与vector的性能对比。 一、deque的基本特性1. 什么是dequedeque是一种双端队列容器，支持在常数时间内对两端进行插入和删除操作： 123456789101112131415161718192021222324252627#include <deque>#include <iostream>int main() { std::deque<int> dq; // 尾部操作 dq.push_back(1); dq.push_back(2); dq.push_back(3); // 头部操作 dq.push_front(0); dq.push_front(-1); // 支持随机访问 std::cout << "Element...

一、什么是 YAML？—— 不止于「另一种配置文件」YAML 全称 YAML Ain't Markup Language（YAML 不是标记语言），听着像绕口令，核心却是「反标记语言」的设计理念：用最简洁的语法描述数据结构，让人类一眼能看懂，机器也能轻松解析。 它诞生于 2001 年，初衷是替代 XML 的繁琐标签和 JSON 的大括号，如今已成为配置文件的「首选格式」—— 你在 Kubernetes、Docker Compose、Spring Boot、GitHub Actions 等场景中，随处可见它的身影。 核心定位：人类可读、机器可解析的数据序列化语言，专注于配置场景的简洁性和易用性。 二、为什么选择 YAML？—— 三大核心优势对比 XML、JSON，YAML 的优势一目了然： 特性 XML（繁琐） JSON（简洁但局限） YAML（平衡之选） 语法简洁度 需闭合标签（） 需大括号 / 引号，无注释 无多余符号，支持注释 可读性 低（标签冗余） 中（结构清晰但缺乏注释） 高（自然语言般的层级） 数据类型支持 需定义 schema...

步骤 1：说明编译与运行时工作目录的分离特性首先，我们必须明确一个基本原则：编译器的工作目录和程序运行时的工作目录是两个完全独立的概念。 1.1 编译时路径解析编译器（如GCC, Clang, MSVC）在处理源代码时，主要涉及两种路径： #include "my_header.h"：这种形式的包含指令，编译器会首先在包含该指令的源文件所在的目录下查找my_header.h。如果找不到，再在编译器指定的系统或用户包含路径（通过-I参数指定）中查找。 #include <iostream>：这种形式，编译器会直接在系统或用户指定的包含路径中查找，而不会在当前源文件目录中查找。 关键点：编译时的路径解析是为了定位源文件和头文件，以便将它们组合成一个翻译单元并生成目标文件（.o或.obj）。这个过程与程序最终运行时需要读取的数据文件（如配置、图片、资源）毫无关系。 1.2 运行时路径解析当你的程序被编译链接成可执行文件并启动时，操作系统会为其创建一个进程。这个进程拥有一个重要的属性：当前工作目录。 所有运行时的相对路径文件操作（如std::ifstr...

一、BM25 算法核心原理：从公式到 C++ 实现关注点BM25（Best Matching 25）是基于概率检索模型的改进算法，核心是在 TF-IDF 的基础上增加文档长度归一化和参数可调性，解决 “长文档过度匹配” 的问题。理解原理时，需重点关注与 C++ 实现强相关的设计点。 1.1 核心公式与参数意义BM25 的单术语 - 文档相关性评分公式如下： $score(q, d) = IDF(q) \times \frac{TF(q, d) \times (k_1 + 1)}{TF(q, d) + k_1 \times (1 - b + b \times \frac{len(d)}{avg_len})}$ 其中关键参数与 C++ 实现的关联的： $TF(q,d)$在文档$d$中的词频，需存储在倒排索引中，用float类型平衡精度与内存； $len(d)$文档$d$的长度（术语数），需在文档元数据中记录，用uint32_t节省内存； $avg_len$所有文档的平均长度，预处理阶段计算后全局缓存，避免重复计算； $k$词频饱和系数（通常取 1.2~2.0），控制...

一、Trie 树定位Trie 树（前缀树 / 字典树）是专为字符串设计的树形结构，核心价值是通过 “前缀共享” 减少内存冗余，同时实现 O (k)（k 为字符串长度）的插入 / 查询效率，尤其适合 “前缀相关场景”（如自动补全、拼写检查）。 二、核心结构：节点设计与前缀共享1. 节点结构体Trie 的最小单元是节点，需存储子节点映射和单词结尾标记，C++ 中用结构体实现最简洁： 123456789struct TrieNode { // 子节点：两种实现方案（按需选择） // 方案1：数组（仅适用于固定小字符集，如小写字母，速度快） TrieNode* children[26] = {nullptr}; // 方案2：哈希表（字符集不确定时用，如含数字/符号，灵活） // unordered_map<char, TrieNode*> children; bool isEnd = false; // 标记当前节点是否为某单词的结尾（避免前缀误判）}; 根节点是TrieNo...

导言在 C++ 开发中，频繁使用 new/delete 会导致内存碎片、系统调用开销大等问题，尤其在多线程场景下性能损耗显著。内存池作为一种高效的内存管理方案，通过预先申请大块内存、重复利用空闲内存的方式，能有效解决这些问题。 一、内存池核心设计思路1.1 解决的核心问题 内存碎片：原生 new/delete 分配的内存大小随机，长期使用会产生大量无法利用的小块内存（碎片）； 系统调用开销：每次 new 都会触发系统调用（如 brk/mmap），频繁调用会严重影响性能； 多线程安全：原生内存分配器的锁竞争会导致多线程场景下性能下降。 1.2 核心设计方案我们的内存池采用 “多池分治 + 无锁空闲链表 + 内存块复用” 的设计，具体如下： 多池分治：按内存大小划分 64 个内存池，分别管理 8~512 字节的内存（步长 8 字节），超过 512 字节的内存直接使用原生 new/delete； 无锁空闲链表：用原子操作（CAS）实现空闲内存的入队 / 出队，避免多线程锁竞争； 内存块复用：预先申请 4096 字节的大块内存（与...

一、STL 算法调用成员函数的典型错误在开始解决方案前，我们先明确最常见的错误模式，理解问题本质才能避免重复踩坑。 1.1 错误代码示例1234567891011121314151617181920212223242526#include <vector>#include <algorithm>#include <iostream>class NumberProcessor {private: int value;public: NumberProcessor(int v) : value(v) {} bool isEven() const { return value % 2 == 0; } // 筛选条件成员函数 void printValue() const { std::cout << value << " "; } // 操作成员函数 void add(int num) { va...

一、Vector 整体结构与 allocator 定位1.1 Vector 核心数据成员构成std::vector 作为动态数组容器，其核心数据结构由三个指针（或类似指针的迭代器）构成，分别指向： 数据区起始位置（begin）：指向已分配内存块的起始地址 有效数据结束位置（end）：指向当前已存储元素的下一个位置 内存块结束位置（capacity_end）：指向已分配内存块的末尾位置 1.2 allocator 在 Vector 中的核心定位std::allocator 作为 Vector 的内存分配器组件，承担以下核心职责： 提供类型安全的内存分配 / 释放接口 解耦容器逻辑与底层内存管理实现 实现元素构造与内存分配的分离操作 支持自定义内存分配策略的扩展接口 二、std::allocator 核心接口与内存分配流程2.1 allocator 核心成员函数 allocate(size_t n)：分配能够存储 n 个元素的未初始化内存块，返回指向内存块起始位置的指针，内存大小为 n * sizeof (T) deallocate(T p, size_t n)*：...

STL标准模板库（重点）：C++工具（类模板与函数模板） STL标准模板库 本质上就是数据结构和算法 C语言标准库未直接提供 C++标准库直接提供 定义：高效C程序库，含基本数据结构和算法，属C标准库，采用泛型编程 泛型编程：抽象数据类型，用泛型代替具体类型，编写通用代码 六大组件 容器（重要）：存储数据（数据结构） 序列式容器：vector、list、deque等 关联式容器：set、map等 无序关联式容器：unordered_set、unordered_map等 迭代器：访问容器元素，泛型指针（例：vector::iterator） 算法：操作容器元素的普通函数（例：std::sort） 适配器：适配作用 容器适配器：stack、queue、priority_queue 迭代器适配器 函数适配器：bind、bind1st、bind2nd、function等 函数对象：实现定制化操作 空间配置器：管理内存（使用、原理、源码） 六大组件 容器 作用：存放数据 1、序列式容器 模型理解 array 静态数组，大小固定的数...

一、需求与设计分析1.1 核心需求根据 C++ Primer 11.3.6 练习要求，工具需满足以下功能： 规则加载：从map.txt读取替换规则（每行格式：待替换单词 替换后的短语） 文本处理：读取file.txt中的待转换文本，将匹配规则的单词替换为对应短语 结果输出：将替换后的文本写入output.txt 灵活性：支持通过命令行参数自定义规则文件、输入文件和输出文件路径 鲁棒性：处理文件打开失败、格式错误等异常情况 1.2 示例输入输出 规则文件（map.txt）：定义替换映射 12345678brb be right backk okay?y whyr areu youpic picturethk thanks!l8r later 待转换文本（file.txt）：包含缩写词的原始文本 123where r uy dont u send me a pick thk l8r 预期输出（output.txt）：替换后的标准文本 123where are youwhy dont you send me a pictureokay? thanks! later ...

导言作为具备一定工程实践经验的中级软件工程师，在日常软件开发工作流中，C++ 标准模板库（Standard Template Library，STL）的容器与算法体系已成为不可或缺的编程工具。vector 的动态内存管理机制、map 的有序键值对存储特性，以及 sort 算法的高效执行范式，这些看似常规的编程操作，实则蕴含着深邃的计算机科学设计思想。通过研读侯捷所著《STL 源码剖析》，得以系统性解构 STL 的底层实现逻辑，深刻体会到 "知其然更知其所以然" 在软件工程领域的重要价值。 一、数据结构：从应用层到实现层的认知跃迁在数据结构层面，STL 核心容器的底层实现机制在书中得到细致解析。以 vector 容器为例，其动态数组特性不仅体现在可扩展的存储容量上，更在于其内存管理策略的精妙设计。当容器容量不足时，vector 采用指数级扩容策略（通常为原容量的 2 倍或 1.5 倍，依具体实现而定），通过重新分配内存空间、元素迁移及旧内存释放的流程，在空间复杂度与时间复杂度之间实现了高效平衡。这种 "以空间换时间" 的策略，有效规避了频繁内...

引言：迭代器的核心价值在 C++ 标准模板库 (STL) 中，迭代器扮演着 "胶水" 的角色，它连接了容器与算法，使算法能够独立于具体容器类型工作。这种抽象机制带来了极大的灵活性 —— 同一个排序算法可以作用于向量 (vector)、链表 (list) 或数组 (array)，只需它们提供兼容的迭代器。 迭代适配器则是在基础迭代器之上的增强，通过包装现有迭代器，提供反向遍历、插入操作等特殊行为，进一步扩展了迭代器的能力。本文将系统解析迭代器的分类、实现原理及迭代适配器的应用场景。 一、迭代器基础：概念与分类1.1 迭代器的本质迭代器本质上是一种泛化的指针，它重载了*、->、++等运算符，使开发者能够以统一的方式访问容器中的元素，而不必关心容器的内部实现细节。 1234567891011121314151617181920212223#include <vector>#include <list>#include <iostream>// 通用打印函数，适用于任何提供输入迭代器的容器template<typenam...

一、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_ << ")" << std::...

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

一、内部实现机制 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 交互（...

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

导言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)，但实际性能可能略优于 vect...

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