04 集合与序列

数组、字典、集合、元组、区间的全部常用操作,附复杂度与陷阱

04 集合与序列

三种集合,先看怎么选

ArrayDictionarySet
顺序保持插入顺序不保证任何顺序不保证任何顺序
查找按索引 O(1),按值 O(n)按键 O(1)按值 O(1)
元素要求无键必须 Hashable元素必须 Hashable
典型场景有序列表、频繁按下标访问键值映射、查表去重、成员判断、集合运算
字面量[1, 2, 3]["a": 1]Set([1, 2])

💭 拿不定主意时先写 Array。等出现"我要判重"或"按 key 查"的需求,再换成 Set 或 Dictionary——它们都是值类型,换起来不伤筋动骨。

数组

创建

1
2
3
4
5
6
7
8
let literal = [1, 2, 3]
let typed: [Int] = []
let repeated = Array(repeating: 0, count: 5)
let fromRange = Array(1...5)
let empty = [String]()

print(repeated, fromRange)
// prints: [0, 0, 0, 0, 0] [1, 2, 3, 4, 5]

⚠️ 空数组字面量必须给类型:let a: [Int] = [] 合法,let a = [] 是编译错误——编译器没有任何线索猜元素类型。

增删改查

操作写法复杂度
追加a.append(x) 或 a += [x]O(1) 摊销
插入a.insert(x, at: i)O(n)
删除指定位置a.remove(at: i)O(n)
删除末尾a.removeLast() / a.popLast()O(1)
按条件删除a.removeAll { $0 < 0 }O(n)
全部清空a.removeAll()O(n)
按下标读a[0]、a.first、a.lastO(1)
按下标写a[0] = 9O(1)
交换a.swapAt(i, j)O(1)
预分配容量a.reserveCapacity(1000)—
是否为空a.isEmptyO(1)
元素个数a.countO(1)
1
2
3
4
5
6
var nums = [3, 1, 4, 1, 5]
nums.append(9)
nums.insert(0, at: 0)
nums.remove(at: 0)
print(nums)
// prints: [3, 1, 4, 1, 5, 9]

构造与容量:几个少见的 init

除了字面量和 Array(repeating:count:),还有几个构造器值得认识:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
// 从 (键, 值) 序列一次性建字典
let pairs = [("a", 1), ("b", 2)]
print(Dictionary(uniqueKeysWithValues: pairs).keys.sorted())
// prints: ["a", "b"]

print(Dictionary(uniqueKeysWithValues: zip(1..., ["a", "b"]))[2] ?? "?")
// prints: b

// 键可能重复时,得自己定"留谁"的规则
let dup = [("a", 1), ("a", 2)]
print(Dictionary(dup, uniquingKeysWith: { first, _ in first })["a"] ?? -1)
// prints: 1

var arr = [1, 2, 3]
arr.removeAll(keepingCapacity: true)      // 清空元素,但留着已分配的内存
print(arr.isEmpty, arr.capacity >= 3)
// prints: true true
需求写法
从键值对建字典Dictionary(uniqueKeysWithValues:),键重复会崩 ⚠️
键重复时自己定规则Dictionary(_:uniquingKeysWith:)
重复元素只留一个Set(数组),或 Dictionary 做中间层
预分配容量a.reserveCapacity(n)、d.reserveCapacity(n)
看已分配多少a.capacity
清空但保留容量a.removeAll(keepingCapacity: true) 🝖

⚠️ Dictionary(uniqueKeysWithValues:) 碰到重复键直接崩(实测 Fatal error: Duplicate values for key: 'a'),它不负责替你决定留哪一个。数据来自外部(解析结果、用户输入)时,用 uniquingKeysWith: 版本把规则写清楚。

💭 还有一个冷门兄弟 ContiguousArray<Element>:它保证元素在一块连续内存里。元素是类或 @objc 协议类型时,它可能比 Array 少一层桥接开销;其他情况直接用 Array,别没事换类型。🝖

排序与变形

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
let nums = [3, 1, 4, 1, 5]

print(nums.sorted())
// prints: [1, 1, 3, 4, 5]
print(nums.sorted(by: >))
// prints: [5, 4, 3, 1, 1]
print(nums.reversed().map { $0 })
// prints: [5, 1, 4, 1, 3]

var mutable = nums
mutable.sort()          // 原地排序,要求元素可比较
print(mutable)
// prints: [1, 1, 3, 4, 5]

⚠️ sorted() 返回新数组,sort() 原地改。看到没有 ed 后缀,就说明它在改你自己。这条规矩对 reversed / shuffled 也一样:shuffled() 返回新数组,shuffle() 打乱自己。

🔥 排序是稳定的:两个"相等"的元素会保持原来的相对顺序。这一点在按多个字段排序时特别有用——先按次要字段排一次,再按主要字段排一次,前一次的成果不会被打乱。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
struct Player { let first: String; let last: String }

// 已经按姓氏排好
var roster = [
    Player(first: "Sam", last: "Coffey"),
    Player(first: "Ashley", last: "Hatch"),
    Player(first: "Kristie", last: "Mewis"),
    Player(first: "Ashley", last: "Sanchez"),
]

roster.sort { $0.first < $1.first }      // 再按名字排
print(roster.map(\.last))
// prints: ["Hatch", "Sanchez", "Mewis", "Coffey"]
// 两个 Ashley 的先后没变:Hatch 还在 Sanchez 前面

💭 这条保证是从 Swift 5.8 起明确写进官方文档的(SE-0372)。老教程说"Swift 的排序不稳定",那是很久以前的信息。

切片

1
2
3
4
5
6
let nums = [3, 1, 4, 1, 5, 9]

print(nums.prefix(2), nums.suffix(2))
// prints: [3, 1] [5, 9]
print(nums.dropFirst(2), nums.dropLast(2))
// prints: [4, 1, 5, 9] [3, 1, 4, 1]

⚠️ 切片返回的是 ArraySlice,它保留原来的下标。这意味着:

1
2
3
4
5
6
7
let nums = [3, 1, 4, 1, 5, 9]

let slice = nums[2...4]
print(slice[0])
// 🛑 崩溃:下标越界
print(slice[slice.startIndex])
// prints: 4        ✅ 必须用切片的 startIndex

要恢复正常下标就 Array(slice)。这个坑每年都有一批人栽进去。

字典

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
var ages = ["Alice": 30, "Bob": 25]

ages["Carol"] = 28                 // 新增
ages["Alice"] = 31                 // 覆盖
ages["Bob"] = nil                  // 删除
print(ages.keys.sorted())
// prints: ["Alice", "Carol"]

print(ages["nobody", default: 0])
// prints: 0

ages["Dave", default: 0] += 1      // 不存在就先用默认值起手
print(ages["Dave"] ?? -1)
// prints: 1
操作写法备注
取值d[key]返回 Value?,键不存在就是 nil
带默认值取值d[key, default: 0]返回非可选值,🔥 常配合 += 计数;只读不会写入,+= 会顺手插入这个键
写入d[key] = value键已存在则覆盖
删除d[key] = nil 或 d.removeValue(forKey: key)后者返回被删掉的值
更新并取旧值d.updateValue(v, forKey: k)返回旧值 Value?
遍历for (k, v) in d顺序不保证
只取键 / 值d.keys / d.values都是视图,不复制
变换值d.mapValues { $0 * 2 }保留键类型
筛选d.filter { $0.value > 26 }返回新字典
合并d.merging(other) { old, new in new }冲突时由闭包决定留谁
分组Dictionary(grouping: items, by: { $0.kind })一行完成分组统计 🔥
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
let words = ["apple", "avocado", "banana", "blueberry", "cherry"]
let grouped = Dictionary(grouping: words) { $0.first! }
print(grouped["a"] ?? [])
// prints: ["apple", "avocado"]

let counts = words.reduce(into: [Character: Int]()) { result, word in
    result[word.first!, default: 0] += 1
}
print(counts["b"] ?? 0)
// prints: 2

集合

1
2
3
4
5
6
7
var seen: Set<Int> = [1, 2, 3]
seen.insert(4)
seen.insert(4)                 // 重复插入无效果
print(seen.count)
// prints: 4
print(seen.contains(3))
// prints: true
运算写法含义
并集a.union(b)两边的元素合起来(自动去重)
交集a.intersection(b)两边都有的
差集a.subtracting(b)在 a 不在 b
对称差a.symmetricDifference(b)只在一侧出现
子集a.isSubset(of: b)参数可以是任何序列
超集a.isSuperset(of: b)
无交集a.isDisjoint(with: b)
原地版本a.formUnion(b) 等直接改 a,避免复制 🝖
1
2
3
4
5
6
7
let a: Set = [1, 2, 3, 4]
print(a.union([5, 6]).sorted())
// prints: [1, 2, 3, 4, 5, 6]
print(a.subtracting([1, 2]).sorted())
// prints: [3, 4]
print(a.symmetricDifference([3, 9]).sorted())
// prints: [1, 2, 4, 9]

🔥 判断"两个数组有没有重复元素"时,把其中一个转成 Set 再 isDisjoint,比双层循环快得多。

⚠️ Set 里的元素必须实现 Hashable。自定义类型加上 Hashable 后,编译器通常能自动合成实现——但如果你的类型有 Double 字段,别用它当哈希依据,NaN 会让集合行为变得不可预测。

固定长度与"只看不抄":InlineArray 和 Span 🆕

Array 的元素放在堆上,长度随时可变。Swift 6.2 带来了两个"反着来"的兄弟:

  • InlineArray<N, T>:长度写在类型里,元素直接内联存放,没有堆分配。
  • Span<T>:一段借来的只读视图,拿到它不拷贝任何数据。
1
2
3
4
5
6
7
8
var buffer: InlineArray<3, Int> = [1, 2, 3]
buffer[0] = 9
print(buffer.count, buffer[0])
// prints: 3 9

let numbers = [10, 20, 30]
print(numbers.span[1], numbers.span.count)     // 借出来看一眼,不复制
// prints: 20 3

⚠️ 两个实测会碰到的限制:

你想写的结果
for x in buffer(遍历 InlineArray)for-in loop requires 'InlineArray<3, Int>' to conform to 'Iterable', which is only available in macOS 27.0 or newer
把 Span 存进属性、或从函数里返回the 'get' accessor cannot return a ~Escapable result / a function cannot return a ~Escapable result——Span 是 ~Escapable 的,不许比出借它的那个值活得久

💭 这两个类型是给性能敏感代码准备的(省掉堆分配、也能天然避免数据竞争)。日常业务照旧用 Array;读到它们时,知道是"更快但更受限的数组"就够。

元组

元组是"临时打包几个值"的轻量工具,没有命名类型,也不能实现协议。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
let pair = (name: "Alice", age: 30)
print(pair.name, pair.1)
// prints: Alice 30

let (n, a) = pair          // 解构
print(n, a)
// prints: Alice 30

let (_, onlyAge) = pair    // 用 _ 忽略不需要的部分
print(onlyAge)
// prints: 30
能做不能做
带标签或按位置访问不能遵守协议(除了有限的比较)
作为函数返回值返回多个值不能加方法或属性
逐元素比较(最多 6 个元素)不能递归包含自身
swap(&a, &b) 交换两个变量元素超过 6 个就无法比较大小
1
2
3
4
print((1, "b") < (2, "a"))
// prints: true
print((1, 2) < (1, 3))
// prints: true

💭 元组适合"就地返回两三个值",一旦发现这个组合要传给多个函数,就该升级成 struct——有名字的类型比 (String, Int, Bool) 好懂得多。

区间与序列

1
2
3
4
5
6
7
8
print(Array(1...5))
// prints: [1, 2, 3, 4, 5]
print((1...5).map { $0 * $0 })
// prints: [1, 4, 9, 16, 25]
print(Array(stride(from: 0, to: 10, by: 3)))
// prints: [0, 3, 6, 9]
print(Array((1...5).reversed()))
// prints: [5, 4, 3, 2, 1]

..< 是半开区间 Range,... 是闭区间 ClosedRange。Range 可以表示空区间(5..<5),ClosedRange 不行。

标准库还提供了两个"按规律生成序列"的函数,写算法题和爬格子时很好用:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
// sequence(first:next:):从第一个值开始,靠闭包推出下一个;返回 nil 就结束
let powers = sequence(first: 1, next: { $0 < 100 ? $0 * 2 : nil })
print(Array(powers))
// prints: [1, 2, 4, 8, 16, 32, 64, 128]

// sequence(state:next:):状态自带,适合递推
let fib = sequence(state: (0, 1)) { (pair: inout (Int, Int)) -> Int? in
    defer { pair = (pair.1, pair.0 + pair.1) }
    return pair.0
}
print(Array(fib.prefix(7)))
// prints: [0, 1, 1, 2, 3, 5, 8]

print(Array(repeatElement("x", count: 3)))
// prints: ["x", "x", "x"]

💭 它们是惰性的:不 prefix、不 Array(...) 就不会真的算下去。拿不到终止条件时记得自己截断,否则会一直生成下去。

自己造一个序列:IteratorProtocol

标准库的 Sequence 不是魔法,它只要求一件事:能给出一个"下一个值"。你的类型只要实现 next(),就能用上 map、filter、reduce、for-in 全套工具:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
struct Countdown: Sequence, IteratorProtocol {
    var current: Int

    mutating func next() -> Int? {
        guard current > 0 else { return nil }   // 返回 nil 表示"没有了"
        defer { current -= 1 }
        return current
    }
}

print(Array(Countdown(current: 3)))
// prints: [3, 2, 1]
print(Countdown(current: 4).map { $0 * 10 })
// prints: [40, 30, 20, 10]
for x in Countdown(current: 2) { print(x) }
// prints:
//   2
//   1

两个协议的分工:

协议要求你能得到
IteratorProtocolmutating func next() -> Element?一个能一步步取值的东西
SequencemakeIterator()for-in、map、filter、reduce、contains… 全套免费

💭 当类型自己就是迭代器(同时遵守两个协议)时,标准库会用默认实现替你写 makeIterator(),所以上面只写了 next()。这就是"遵守一个协议,白拿一整套算法"的最好例子。

想临时凑一个序列、又不想专门定义类型时,用 AnyIterator 和 AnySequence:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
var i = 0
let counter = AnyIterator { () -> Int? in
    i += 1
    return i <= 3 ? i : nil
}
print(Array(counter))
// prints: [1, 2, 3]

// 承接上文:Countdown 已定义
let seq = AnySequence(Countdown(current: 3))
print(seq.reduce(0, +))
// prints: 6
类型用途
AnyIterator用一个闭包当场造出迭代器
AnySequence把任意序列包起来,藏掉具体类型(类型擦除)
sequence(first:next:) / sequence(state:next:)连类型都不用定义,见上一节

⚠️ Sequence 有一个出了名的特性:它不保证能被遍历两次。如果序列是"一次性"的(比如网络流、文件句柄),第一次 for-in 之后第二次就没数据了。需要重复遍历就遵守 Collection,或者先 Array(seq) 存下来。

高阶函数速查

这张表是 Swift 写起来最爽的部分,值得整块记住。

函数作用示例 → 结果
map一对一变换[1,2].map { $0 * 2 } → [2, 4]
compactMap变换并丢掉 nil["1","x"].compactMap(Int.init) → [1]
flatMap展平一层嵌套[[1,2],[3]].flatMap { $0 } → [1, 2, 3]
filter保留满足条件的[1,2,3].filter { $0 > 1 } → [2, 3]
reduce折叠成一个值[1,2,3].reduce(0, +) → 6
reduce(into:)折叠进可变容器见上面的词频统计
sorted(by:)自定义排序[3,1].sorted(by: >) → [3, 1]
first(where:)第一个满足条件的[1,2].first { $0 > 1 } → 2
allSatisfy是否全部满足[2,4].allSatisfy { $0.isMultiple(of: 2) } → true
contains(where:)是否存在满足的[1,2].contains { $0 > 1 } → true
min() / max()最小 / 最大[3,1].min() → 1
min(by:) / max(by:)用自定义规则找极值[3,1].min(by: >) → 3(“按 > 排最前"就是最大那个)
firstIndex(of:) / firstIndex(where:)找位置,找不到给 nil[3,1,4].firstIndex(of: 4) → 2
lastIndex(of:) / lastIndex(where:)从后往前找[1,2,1].lastIndex(of: 1) → 2
prefix / suffix前 / 后 N 个[1,2,3].prefix(2) → [1, 2]
dropFirst / dropLast丢掉前 / 后 N 个[1,2,3].dropFirst() → [2, 3]
zip拉链式配对zip([1,2], ["a","b"]) → [(1,"a"), (2,"b")]
enumerated带下标["a"].enumerated() → [(0, "a")]
joined拼接["a","b"].joined(separator: "-") → "a-b"
shuffled / randomElement随机[1,2].randomElement() → 随机一个或 nil

同一个任务,三种写法

统计一段文本里每个单词出现的次数——这是最常遇到的小需求,也是最能看出风格差异的地方。

1
2
3
4
5
6
7
8
let words = ["apple", "banana", "apple", "cherry", "banana", "apple"]

let counts = words.reduce(into: [String: Int]()) { result, word in
    result[word, default: 0] += 1
}

print(counts["apple"] ?? 0)
// prints: 3

一次遍历、不产生中间数组,result[word, default: 0] += 1 这个写法本身也足够清楚。🔥

1
2
3
4
5
6
7
let words = ["apple", "banana", "apple", "cherry", "banana", "apple"]

let groups = Dictionary(grouping: words) { $0 }
let counts = groups.mapValues(\.count)

print(counts["apple"] ?? 0)
// prints: 3

思路更直白:“先按自己分组,再数每组的数量”,代价是多存了一份分组数据。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
let words = ["apple", "banana", "apple", "cherry", "banana", "apple"]

var counts: [String: Int] = [:]
for word in words {
    if let n = counts[word] {
        counts[word] = n + 1
    } else {
        counts[word] = 1
    }
}

print(counts["apple"] ?? 0)
// prints: 3

毫无技巧,也毫无误解空间。团队风格保守时它反而是最好的选择。

序列、集合、惰性

Swift 的集合协议是一条链,理解它能解释很多"为什么这里能用那里不能用”。

协议提供的能力谁遵守
Sequence能 for-in,能 map / filter几乎所有容器
Collection上面全部 + 下标、count、可多次遍历Array Dictionary Set String
BidirectionalCollection还能从后往前Array String
RandomAccessCollection索引移动是 O(1)Array

Sequence 只有一次机会:如果某个序列是"单遍"的(比如从网络读流),遍历两次会出问题:

1
2
3
let s = [1, 2, 3].lazy.map { $0 * 2 }
print(s.first ?? 0)
// prints: 2

⚠️ .lazy 会把变换推迟到真正取值时才发生。链式操作很长时它能省掉中间数组。但它只是包装:底层是可多次遍历的集合(Array、Range)时,遍历几遍都没事;底层本身是单遍序列(读流、通道)时,第二遍就是空的——这才是那个经典 bug。

复杂度速查

操作ArrayDictionary / Set
按下标 / 键访问O(1)O(1) 平均
追加 / 插入末尾 O(1) 摊销,中间 O(n)O(1) 平均(可能触发扩容重哈希)
删除末尾 O(1),中间 O(n)O(1) 平均
按值查找O(n)O(1) 平均
是否包含O(n)O(1) 平均
遍历O(n)O(n)

陷阱速查

陷阱说明
越界访问a[i] 不检查,越界直接崩溃;用 a.indices.contains(i) 或 a.first
ArraySlice 下标切片保留原数组下标,用 startIndex 而不是 0
边遍历边改for x in a 迭代的是取值那一刻的快照,循环里改 a 不会崩但结果容易想错;真正会崩的是按下标一边走一边删(for i in a.indices { a.remove(at: i) } → Fatal error: Index out of range),要先收集下标再删
字典顺序遍历字典的顺序不保证,需要稳定顺序就 sorted()
first 返回可选值a.first 是 Element?,空数组得到 nil
contains 用在 Set 上更快[Int] 上判重是 O(n),Set 上是 O(1)
大数组用 += 单个元素用 append,+= 每次都会构造数组字面量
最后修改 September 20, 2026: 更新 (25684a4ed)