Data Structures and Algorithms

一、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...