企业官网建设流程全解析

• 人工智能
• AI 技能
• 文档
• 开发工具

std.collection是 Cangjie 标准库中提供常见数据结构高效实现、抽象接口定义以及集合操作通用函数的包。它覆盖了列表、双端队列、栈、队列、哈希表、哈希集合、红黑树映射与有序集合等日常开发中最常用的容器类型，并配套一套可直接作用于任意Iterable的管道式集合操作函数（如filter、map、fold、zip等）。阅读本篇后，你将能够按需选型容器、理解各实现的时间复杂度与扩容策略，并直接使用文中示例快速上手 Cangjie 集合编程。

包定位：std.collection 提供什么

根据包概述文档（std/collection/collection_package_overview.md），collection 包提供了三大类能力：

1. 常见数据结构的高效实现：以具体类（class）形式提供，例如ArrayList、LinkedList、HashMap、HashSet、TreeMap、TreeSet、ArrayDeque、ArrayQueue、ArrayStack等；
2. 相关抽象接口的定义：以接口（interface）形式定义统一的操作契约，例如List、Map、Set、Queue、Stack、Deque以及只读变体ReadOnlyList、ReadOnlyMap、ReadOnlySet等；
3. 集合类型中常用的函数功能：面向迭代器的通用函数，例如all、any、map、filter、fold、reduce、zip、collect*系列转换函数等。

一个需要特别注意的边界是：collection 包提供的所有集合类型都不支持并发安全。从源码结构看，ConcurrentModificationException的存在正是为了在检测到不同步的并发修改时及时暴露问题（见 std/collection/collection_package_api/collection_package_exception.md）。如果业务场景需要并发安全的集合，应使用标准库中单独的并发集合包。

数据结构实现总览

std/collection/readme.md将包内全部容器分为"数据结构实现"与"集合操作函数"两大类。下表完整列出容器类型及其原型与说明：

接口层面的完整签名与每个方法的语义说明，见 std/collection/collection_package_api/collection_package_interface.md；类层面的构造器、属性、方法与运算符重载说明，见 std/collection/collection_package_api/collection_package_class.md。

接口体系：从只读到可写的继承层次

从接口文档的源码结构可以清晰看到 collection 包的接口设计遵循"只读能力 → 可写能力"的递进分层：

• 只读一族：ReadOnlyList、ReadOnlyMap、ReadOnlySet 只提供查询能力，例如get、contains、keys()、values()、subsetOf()；
• 可写一族：List 继承ReadOnlyList，新增add、remove、removeIf、clear及下标赋值运算符[]；Map 继承ReadOnlyMap，新增add、remove、replace、addIfAbsent、entryView等；Set 继承ReadOnlySet，新增add、remove、retain、clear等；
• 顺序增强：OrderedMap 在Map基础上增加first、last属性与removeFirst、removeLast、forward(mark, inclusive!)、backward(mark, inclusive!)定向遍历方法；OrderedSet 同理；
• 结构契约：Deque 提供addFirst/addLast/removeFirst/removeLast与first/last属性；Queue 提供add/peek/remove；Stack 同样提供add/peek/remove，但语义是"栈顶"；EquatableCollection 提供单元素与批量contains判定。

值得注意的是 MapEntryView 的value是可写属性：设置非空 value 时，若视图对应的键不存在，会在原始映射中新增元素；设置为None则会删除当前 Entry，删除后视图仍可继续使用。这是实现"通过视图读写映射"的关键入口。

树形容器特有的 forward / backward 定向遍历

OrderedMap与OrderedSet提供的forward(mark, inclusive!)与backward(mark, inclusive!)是面向有序容器的定向迭代能力（对应实现见 TreeMap 与 TreeSet）：

• forward(mark, inclusive!)：从第一个键（元素）大于等于 mark 的节点开始按升序遍历到最后一个元素，inclusive!决定当 mark 恰好命中首个元素时是否包含该起点，默认为true；
• backward(mark, inclusive!)：从第一个键（元素）小于等于 mark 的节点开始按降序遍历到第一个元素。

类实现深度剖析：底层原理与关键行为

ArrayList：可变长连续数组

ArrayList<T>实现 List 接口，是一种线性动态数组（类定义见 std/collection/collection_package_api/collection_package_class.md）。与定长Array不同，它创建时无需指定大小，插入时若容量不足会自动重新分配更大的内存并复制原有元素。文档明确提示：动态数组可节省内存并按需扩容，但重新分配内存时可能带来性能下降，因此需要谨慎权衡使用场景。

关键行为要点：

• 默认容量：init()构造默认容量为 16；init(capacity)可指定初始容量，容量为负时抛IllegalArgumentException；
• 批量构造：支持init(elements: Collection<T>)、init(size, initElement)（按函数规则生成 size 个元素）以及静态工厂ArrayList.of(Array<T>)；
• 扩容策略：reserve(additional)在剩余容量不足时，取"原始容量的 1.5 倍向下取整"与"additional + 已使用容量"两者中的较大值进行扩容；additional小于等于 0 或剩余容量充足时不发生扩容；当additional + 已使用容量超过Int64.Max时抛OverflowException；
• 索引访问：get(index)越界时返回None（安全），而下标运算符list[index]越界时抛IndexOutOfBoundsException（严格）；
• 范围操作：slice(range)与remove(range)支持Range<Int64>切片/删除；若 range 为hasEnd = false的构造实例，end 不生效，切片会取到原数组最后一个元素；step不等于 1 时抛IllegalArgumentException；切片返回全新对象，与原列表无引用关系；
• 条件删除：removeIf(predicate)删除所有满足条件的元素；若 predicate 内部对列表进行了增删改，会抛ConcurrentModificationException；
• 排序 API 已标记废弃：sortBy、sort()、sortDescending()等标注为deprecated，文档建议改用 sort 包中的sort函数（见 std/sort/sort_package_api/sort_package_funcs.md）；
• 扩展接口：为ArrayList扩展了Equatable<ArrayList<T>>（对应位置元素相等即相等）、ToString（输出形如"[elem1, elem2, elem3]"）。

ArrayDeque / ArrayQueue / ArrayStack：基于数组的线性容器

三个类均以数组为底层存储，区别在于操作约束：

• ArrayDeque<T>（实现Deque<T>，见 ArrayDeque_class.md）：可调整大小的循环数组实现，支持两端插入删除；默认容量 8，每次扩容默认增加 50%；无扩容时插入、删除、查看的时间复杂度为 O(1)。removeFirst/removeLast在空队列时返回None；
• ArrayQueue<T>（实现Queue<T>）：循环队列，尾部插入（add）、头部删除（remove）、只读查看（peek），空队列时peek/remove返回None；默认容量同为 8，扩容逻辑与 ArrayDeque 一致；
• ArrayStack<T>（实现Stack<T>）：数组 + 栈顶指针实现，仅支持在顶部插入删除；默认容量 8，reserve在剩余空间不足时扩容至size + additional；iterator()的遍历顺序即出栈顺序，toArray()同样按出栈顺序输出。

LinkedList：双向链表与节点操作

LinkedList<T>实现双向链表（类定义见 LinkedList_class.md），每个节点含前驱/后继指针，支持双向遍历。文档特别强调两点：

• 迭代器失效规则：对集合中元素的修改不会使迭代器失效，只有添加和删除元素会使迭代器失效；
• 节点悬空风险：通过firstNode/lastNode/nodeAt(index)（时间复杂度 O(n)）获得的LinkedListNode，若对应节点被链表删除，会变成悬空节点，对其任何操作（访问next/prev/value）都会抛IllegalStateException。

链表还提供addFirst/addLast（返回新节点）、addBefore/addAfter（在指定节点前/后插入）、remove(node)、splitOff(node)（从指定节点处将链表一分为二，node 成为新链表首节点）、forward(node)/backward(node)（从节点向尾部/头部遍历）等节点级操作。

HashMap：哈希表实现

HashMap<K, V>要求键满足K <: Hashable & Equatable<K>，实现Map接口（见 HashMap_class.md）。文档描述其原理：将数据映射到动态数组（哈希表），每个元素按哈希值定位；查找、插入、删除的时间复杂度通常为 O(1)；由于底层数组大小动态变化，哈希表不能保证元素顺序不可变。

• 默认初始容量为 16；add(key, value)对已存在的键返回旧值（Option封装），键不存在返回None；
• 支持addIfAbsent（键不存在才添加）、replace（键存在才替换，返回旧值）、removeIf（遍历删除满足条件的键值对，predicate 内改动容器会抛ConcurrentModificationException）；
• keys()返回EquatableCollection<K>，values()返回Collection<V>，toArray()返回键值对数组；
• 下标运算符map[key]读取键不存在时抛NoneValueException，写入时map[key] = value等效于add；
• 重复键处理：通过数组/集合构造时，按迭代器顺序后面的键值对覆盖前面的键值对；
• 为HashMap扩展了Equatable（键值对完全相等即相等）与ToString（形如"[(k1, v1), (k2, v2), (k3, v3)]"）。

HashSet：基于 HashMap 的集合

HashSet<T>要求T <: Hashable & Equatable<T>，是基于HashMap实现的Set实例（见 HashSet_class.md）。文档明确指出：HashSet 的容量、内存布局、时间性能与 HashMap 完全相同；元素无序且不允许重复，添加已存在的元素返回false。

除常规的增删查改外，HashSet 还提供：

• 集合代数运算符：&（交集）、|（并集）、-（差集），返回新HashSet；
• retain(all!: Set<T>)仅保留与入参集合重复的元素；
• subsetOf(other)判断是否为ReadOnlySet子集；
• removeIf在 predicate 内部改动容器时抛ConcurrentModificationException。

TreeMap / TreeSet：红黑树支撑的有序容器

• TreeMap<K, V>（要求K <: Comparable<K>，见 TreeMap_class.md）：基于平衡二叉搜索树（文档及包概述均指明为红黑树）实现OrderedMap，提供有序的键值对存储，适合数据库、缓存、查找表等需要有序键值对的场景。iterator()按 Key 从小到大顺序迭代；支持forward/backward定向遍历、first/last、removeFirst/removeLast；
• TreeSet<T>（要求T <: Comparable<T>，见 TreeSet_class.md）：基于 TreeMap 实现OrderedSet，自动排序且去重，同样支持forward/backward、集合代数运算符与subsetOf。

HashMapIterator 与并发修改保护

HashMapIterator<K, V>是 HashMap 的专用迭代器（见 HashMapIterator_class.md），其next()返回?(K, V)，并且是唯一允许在遍历中调用remove()删除"next 函数刚返回元素"的入口——但该 remove 每次 next 后只能调用一次。迭代器检测到不同步的并发修改时抛ConcurrentModificationException。

ConcurrentModificationException（见 collection_package_exception.md）的典型抛出场景包括：

• 使用for-in遍历容器过程中修改容器（HashMapIterator.remove()除外）；
• 使用生命周期较短的视图类型（如MapEntryView）时，其所在容器内容被修改。

集合操作函数：面向迭代器的函数式工具

std/collection/readme.md将包内通用函数完整列出，这些函数大多采用"先传入参数/谓词，返回一个作用于Iterable<T>的函数"的柯里化风格，便于与 pipeline 表达式（|>）配合。下表为完整清单：

函数完整签名与边界行为见 std/collection/collection_package_api/collection_package_function.md。其中几个值得注意的细节：

• skip的边界：count == 0时相当于不跳过返回原迭代器；count >= 迭代器大小时跳过所有元素返回空迭代器；
• take的边界：count == 0返回空迭代器；count >= 迭代器大小时取走全部元素返回原迭代器；
• step是"步进"语义，与skip不同：每次调用next()都会跳过 count 个元素，直到迭代器耗尽；
• collectString的默认分隔符为空字符串，示例中展示了用delimiter: ">"拼接的场景。

实战示例：从样例看典型用法

仓库在 std/collection/collection_package_samples 目录下提供了多个可验证的官方示例（均带<!-- verify -->标记），以下选取四个典型场景。

1. 迭代器函数 + pipeline 管道式操作

来自 sample_iterator.md 的示例演示了filter、step、skip、forEach、collectString、contains的组合用法：

import std.collection.* main() { let arr = [-1, 2, 3, 4, 5, 6, 7, 8, 9] arr |> filter{a: Int64 => a > 0} |> // filter -1 step<Int64>(2) |> // [2, 4, 6, 8] skip<Int64>(2) |> // [6, 8] forEach<Int64>(println) let str = arr |> filter{a: Int64 => a % 2 == 1} |> collectString<Int64>(delimiter: ">") println(str) println(arr |> contains(6_i64)) return 0 }

运行结果：

6 8 3>5>7>9 true

可以看到，step（步进 2 取 [2,4,6,8]）与skip（跳过前 2 个得 [6,8]）的语义差异、以及collectString指定分隔符的效果一目了然。

2. HashMap 的增查删

来自 sample_hashmap_get_add_contains.md 与 sample_hashmap_add_remove_clear.md：

import std.collection.* main() { var map: HashMap<String, Int64> = HashMap<String, Int64>() map.add("a", 99) // map : [("a", 99)] map.add("b", 100) // map : [("a", 99), ("b", 100)] var a = map.get("a") var bool = map.contains("a") print("a=${a.getOrThrow()} ") print("bool=${bool.toString()}") map.add(all: [("d", 11), ("e", 12)]) // 批量添加 map.remove("d") // 按键删除，返回 Option 封装的旧值 map.clear() // 清空 return 0 }

运行结果：a=99 bool=true。注意get返回Option<V>，需用getOrThrow()解包；contains用于键存在性判断。

3. ArrayList 的增改查、删除与切片

来自 sample_arraylist_add.md、sample_arraylist_get_set.md 与 sample_arraylist_remove_clear_slice.md：

import std.collection.* main() { var list: ArrayList<Int64> = ArrayList<Int64>(10) // 容量为 10 list.add(all: [1, 2, 3]) // list: [1, 2, 3] list[1] = 120 // 下标写：list: [1, 120, 3] var b = list.get(2) // b = 3 list.add(12, at: 1) // list: [1, 12, 120, 3] list.remove(at: 1) // 删除索引 1 处元素 list.add(all: [1, 2, 3], at: 0) // 从索引 0 批量插入 let r: Range<Int64> = 1..=2 : 1 var sublist: ArrayList<Int64> = list.slice(r) // sublist: [2, 3] return 0 }

运行结果（对应示例输出）：b=3,c=120,d=2；b=99,g=1,m=2。这里展示了add(element, at:)指定索引插入、add(all: Collection, at:)批量插入、remove(at:)、slice(range)切片与下标赋值list[i] = v的完整用法。

4. TreeSet 与 HashSet：有序 vs 无序

来自 sample_treeset_add_iterator_remove.md：

import std.collection.* main() { var set: TreeSet<String> = TreeSet<String>() set.add("peach") set.add("banana") set.add("apple") set.add("orange") var itset = set.iterator() for (e in itset) { println(e) } set.remove("banana") println(set) return 0 }

运行结果（有序、去重）：

apple banana orange peach [apple, orange, peach]

而 sample_hashset_add_iterator_remove.md 中HashSet的遍历顺序不固定（示例输出仅为其中一种可能），两者对比可直观理解"有序集合"与"哈希集合"的语义差异。

使用建议与注意事项

综合包文档与类文档，使用 collection 包时有以下几点需要留意：

1. 按语义选型：需要随机索引访问选ArrayList；频繁在中间增删选LinkedList；先进先出选ArrayQueue；后进先出选ArrayStack；两端操作选ArrayDeque；快速键值查找选HashMap；需要有序键值对/有序去重集合选TreeMap/TreeSet；
2. 键与元素的约束：HashMap/HashSet要求键/元素实现Hashable & Equatable；TreeMap/TreeSet要求键/元素实现Comparable。编译器会通过where约束在编译期检查；
3. 遍历中不要修改容器：除HashMapIterator.remove()外，遍历过程中对容器增删改会触发ConcurrentModificationException；
4. 关注扩容开销：数组类容器在扩容时存在复制开销（扩容策略为原始容量的 1.5 倍向下取整与需求量的较大者），对容量敏感的场景可预先通过init(capacity)或reserve预留空间；
5. 线程安全边界：本包所有容器均非并发安全，并发场景请使用标准库的并发集合包。

完整 API 索引（含每个类/接口/异常的 JSON 元数据）位于 std/collection/collection_package_index，需要查阅精确签名时可直接对照。

• 人工智能
• AI 技能
• 文档
• 开发工具