C / C++ / 系统课时

检查项目复杂度和内存问题

检查项目复杂度和内存问题

任务管理器功能跑通后,还要确认它在任务数量增长时不会突然变慢,也不会因动态内存错误变得不稳定。本节从链表、哈希索引和堆三个核心结构入手,核对时间复杂度、所有权、数组边界、扩容与释放路径,并用 Sanitizer 做一次动态验证。

学习目标

  • 能写出新增、查找、删除和优先级操作的主要时间复杂度,并发现不必要的线性扫描。
  • 能明确任务对象、哈希桶节点和堆数组的内存所有权,避免泄漏、越界和重复释放。
  • 能使用编译器 Sanitizer 对越界、释放后访问和重复释放进行动态检查。

先把复杂度账算清楚

设任务数为 nn,哈希桶数为 bb。如果项目同时维护链表、哈希表和二叉堆,常见目标复杂度如下:

操作 合理实现 主要复杂度
按 ID 查找 哈希表定位桶,再处理冲突链 平均 O(1)O(1),最坏 O(n)O(n)
遍历全部任务 顺序扫描链表或数组 O(n)O(n)
插入优先级堆 追加后向上调整 O(log⁡n)O(\log n)
查看最高优先级 读取堆顶 O(1)O(1)
删除堆顶 末尾元素移到堆顶后向下调整 O(log⁡n)O(\log n)
按 ID 删除任务 哈希定位任务,但同步删除堆元素若先线性找位置 常见为 O(n)O(n)

重点不是让所有操作都变成 O(1)O(1),而是确认实现与设计预期一致。例如已经有哈希索引,却仍在每次按 ID 查询时遍历链表,就等于没有利用索引;如果删除任意任务时需要在线性扫描堆中找位置,这个 O(n)O(n) 成本应被明确记录,而不是误写成 O(log⁡n)O(\log n)。

明确谁负责释放任务对象

链表、哈希表和堆如果都保存同一个 Task *,最危险的问题不是“指针多”,而是“谁拥有它”。建议只指定一个结构拥有 Task 对象,其余结构只保存非拥有型指针或任务 ID。销毁索引时只释放索引自己的节点或数组,不能再次释放共享的 Task。

任务对象在链表、哈希表与堆之间的所有权关系

检查删除路径时,要从一个任务被移除的入口一路追踪到最终 free。如果哈希桶节点、堆数组和链表节点都引用同一任务,应先从各索引中移除引用,再由唯一所有者释放任务。反过来先 free(task) 再让堆或哈希表继续访问该指针,会形成 use-after-free。

检查堆数组和哈希桶边界

动态数组要始终维护 0 <= size <= capacity。写入 items[size] 之前必须确保容量足够;realloc 失败时不能直接覆盖原指针,否则原内存地址会丢失。下面是片段示例,假设已有 Heap 类型,其中 items 为指针数组,capacity 为当前容量。

c
#include <stdbool.h>
#include <stdint.h>
#include <stdlib.h>

static bool heap_reserve(Heap *heap, size_t need) {
    if (need <= heap->capacity) {
        return true;
    }

    size_t new_capacity = heap->capacity == 0 ? 8 : heap->capacity;
    while (new_capacity < need) {
        if (new_capacity > SIZE_MAX / 2) {
            return false;
        }
        new_capacity *= 2;
    }

    Task **tmp = realloc(heap->items, new_capacity * sizeof *tmp);
    if (tmp == NULL) {
        return false;
    }

    heap->items = tmp;
    heap->capacity = new_capacity;
    return true;
}

哈希表也要检查桶下标是否始终落在 [0, bucket_count)。最常见的安全写法是先确保 bucket_count > 0,再使用 hash % bucket_count。销毁哈希表时,需要释放每条冲突链上的索引节点,最后再释放桶数组;是否释放节点引用的 Task,则必须服从前面的所有权约定。

用 Sanitizer 跑一次动态检查

GCC 或 Clang 可以在测试构建中同时启用 AddressSanitizer 和 UndefinedBehaviorSanitizer。下面是命令模板;执行前把 <PATH> 替换为项目目录,把 <SOURCE_FILES> 替换为项目实际的 .c 源文件列表。

bash
cd "<PATH>"
cc -std=c11 -Wall -Wextra -Wpedantic -g -O1 -fsanitize=address,undefined -fno-omit-frame-pointer <SOURCE_FILES> -o taskmgr
ASAN_OPTIONS=detect_leaks=1 ./taskmgr

预期结果

text
编译成功时编译器不输出错误。
程序正常结束时可以有自身业务输出,但不应出现 AddressSanitizer 或 UndefinedBehaviorSanitizer 的错误诊断。

实际路径和源文件名会因项目而异。如果出现 heap-buffer-overflow,优先检查堆数组容量、哈希桶下标和循环边界;出现 heap-use-after-free 时检查删除后是否仍有索引持有旧指针;出现 double-free 时检查是否有两个结构都把同一个 Task 当成所有者。

按释放路径完成验收

最后不要只验证“退出时没有崩溃”。先创建多批任务,再执行查找、优先级调整、删除和重复扩容,确保每条修改路径都被覆盖。删除任务后再次按 ID 查询应明确返回“未找到”,堆中也不应残留指向已释放任务的指针。

项目可以用三条不变量收口:所有索引下标都在合法范围内;每块动态内存都有且只有一个明确的释放责任方;结构变化后复杂度仍与设计一致。静态检查复杂度和所有权,再用 Sanitizer 覆盖真实运行路径,才能把“能运行”提升为“可长期运行”。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

检查项目复杂度和内存问题

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通