普贤教程 › 生态包

数据结构

集合、前缀树、布隆过滤器、位向量、图、区间、二分。都是纯函数 + 显式状态，编译进二进制即用。本页示例为本机实测输出。

集合

import set

var s = st_new()
st_add(s, "a")
st_add(s, "b")
print(st_len(s))            # 2
print(st_to_list(s))        # [a, b]
print(st_has(s, "a"))       # true
print(st_union(s, st_from_list(["b", "c"])))   # {a: true, b: true, c: true}  ← 返回集合本身（dict）

内部用 dict 存（值作键、true 作值），所以元素必须是字符串或可哈希标量。

前缀树（Trie）

import trie

var t = tr_new()
tr_insert(t, "px")
tr_insert(t, "python")
print(tr_keys_with_prefix(t, "p"))     # [px, python]
print(tr_search(t, "px"))              # true
print(tr_longest_prefix(t, "python3")) # python

典型用途：命令补全、敏感词前缀过滤、路由前缀表。tr_longest_prefix 找「输入串的最长已注册前缀」，比逐个 starts_with 快得多。

布隆过滤器

import bloom

var bf = bloom_new(1000, 3).ok()        # 1000 位、3 个哈希函数
bloom_add(bf, "hello")
print(bloom_may_contain(bf, "hello"))   # Ok(true)
print(bloom_may_contain(bf, "world"))   # Ok(false)   ← 一定不在
print(bloom_false_positive_rate(bf))

布隆的语义是「可能在 / 一定不在」true 不代表存在（可能误判），false 才可靠。所以它只能做「前置过滤」：说不在就可以省一次查询；说在还要去真源确认。用它做「用户是否存在」的判定会出错。

位向量

import bitset

var bs = bs_new(16).ok()
bs_set(bs, 3)
bs_set(bs, 7)
print(bs_count(bs))     # 2
print(bs_to_list(bs))   # [3, 7]
print(bs_test(bs, 3))   # true

适合做「100 万个布尔标记」这类场景：1e6 个 bool 是 1 MB 内存（list 元素是对象，远不止），bitset 是 125 KB。

图

import graph

var g = gr_new()
gr_add_edge(g, "a", "b")
gr_add_edge(g, "b", "c")
print(gr_nodes(g))                 # [a, b, c]
print(gr_bfs(g, "a"))              # Ok([a, b, c])
print(gr_shortest_path(g, "a", "c"))  # Ok([a, b, c])
print(gr_topo(g))                  # 拓扑序（无环时）

邻接表实现，BFS/DFS/拓扑序/最短路径（无权）/连通分量。**不是**带权图的最短路——要 Dijkstra 得自己在外层维护优先队列（datastruct 里有堆）。

区间

import interval

print(iv_overlap(iv_new(1, 5).ok(), iv_new(3, 8).ok()))   # true
print(iv_contains(iv_new(1, 9).ok(), 5))                  # true
print(iv_union(...)) / iv_intersect(...) / iv_merge(...)

闭区间。适合排班、时间窗合并、IP 段判断。

二分

import bisect

var a = [1, 3, 5, 7]
print(bi_left(a, 5))       # 2   ← 第一个 >= 5 的下标
print(bi_right(a, 5))      # 3   ← 第一个 > 5 的下标
print(bi_insort_left(a, 4))    # 保持有序地插入
print(bi_nearest(a, 6))        # 最接近的元素

左右之分的记忆法left 是「插在相等元素的左边」（>=），right 是「插在右边」（>）。要用二分统计「有多少个小于 x」，用 bi_left 的下标。数组必须先有序——二分不会帮你检查。

其它数据结构

包	提供
`datastruct`	堆（`ds_heap_`）、LRU（`ds_lru_`）
`collections`	`each` / `unique` / `flatten` / `zip_lists` / `chunk` / `group_by` / `sort_by`
`counter`	频次统计（见模式页）

选型速查

需求	用什么	复杂度
去重 / 交并差	`set`	O(1) 查询
前缀检索	`trie`	O(长度)
「大概率不存在」快速否掉	`bloom`	O(k)
海量布尔标记	`bitset`	位级
有序数组查找	`bisect`	O(log n)
优先级调度	`ds_heap_*`	O(log n)