這篇文章會用 TDD 手刻 myUnion、myIntersect、mySubtract，搞懂集合的聯集、交集、差集底層怎麼跑。再來看 + 和 - 運算子怎麼操作集合，順便幫 Collection 篇做個總收尾
| Kotlin | C# LINQ | 備註 |
|---|---|---|
union(other) |
Union(other) |
Kotlin 回傳 Set；C# 回傳延遲的 IEnumerable |
intersect(other) |
Intersect(other) |
同上，兩邊都會去除重複 |
subtract(other) |
Except(other) |
C# 叫 Except，名字差很多但功能一樣 |
list + element |
Append(element) |
Kotlin 回傳新 List，不會去除重複 |
list - element |
無直接對應 | Kotlin 回傳新 List |
list + otherList |
Concat |
要注意回傳型別這一欄的差異：Kotlin 的三個集合運算會立刻算出一個 Set，C# 的 Union / Intersect / Except 則是回傳延遲執行的 IEnumerable<T>，語意上會去除重複但不是 Set 型別。Kotlin 的 + 和 - 運算子是語法糖，底層呼叫 plus 和 minus 函式
@Test
fun `union two integer sets`() {
val a = listOf(1, 2, 3)
val b = listOf(3, 4, 5)
val result = a.myUnion(b)
assertEquals(setOf(1, 2, 3, 4, 5), result)
}
@Test
fun `union preserves order`() {
val a = listOf(3, 1)
val b = listOf(4, 1, 2)
val result = a.myUnion(b).toList()
assertEquals(listOf(3, 1, 4, 2), result)
}
@Test
fun `union removes duplicates within same list`() {
val a = listOf(1, 1, 2)
val b = listOf(2, 3, 3)
assertEquals(setOf(1, 2, 3), a.myUnion(b))
}
@Test
fun `union handles null elements`() {
val a = listOf(1, null)
val b = listOf(null, 2)
assertEquals(setOf(1, null, 2), a.myUnion(b))
}
聯集把兩邊的元素合在一起，重複的只留一份。第二個測試驗順序，先出現的優先，3 在 a 裡先出現，所以 3 排第一。最後一個測試確認 null 不會出問題，LinkedHashSet 允許一個 null 元素，去除重複的邏輯一樣套用
infix fun <T> Iterable<T>.myUnion(other: Iterable<T>): Set<T> {
val result = LinkedHashSet<T>()
for (element in this) {
result.add(element)
}
for (element in other) {
result.add(element)
}
return result
}
用 LinkedHashSet 而不是 HashSet，因為聯集需要保留插入順序。先把 this 的元素加進去，再加 other 的。LinkedHashSet 自動去除重複，已經存在的元素不會被加第二次，順序也不會改變
跟 day 25 手刻的 myDistinct 不同，這裡用 LinkedHashSet 是因為它同時負責去除重複和維護順序。myDistinct 的做法是用 HashSet 追蹤已見過的元素，另外用 ArrayList 維護順序。兩種做法的效果一樣，但 union 的寫法更簡潔(順帶一提，stdlib 的 distinct() 走的是 toMutableSet().toList()，toMutableSet() 回傳的正是 LinkedHashSet，跟這裡同一招)
加了 infix 修飾詞，所以可以寫成 a myUnion b。stdlib 的 union 也是 infix 函式
兩個迴圈可以縮成 toMutableSet() 加 addAll(other)，行為一模一樣只是更精簡，stdlib 就是這樣寫的。細節留到後面的「與 stdlib 原始碼比較」一起看
@Test
fun `intersect two integer sets`() {
val a = listOf(1, 2, 3, 4)
val b = listOf(3, 4, 5, 6)
val result = a.myIntersect(b)
assertEquals(setOf(3, 4), result)
}
@Test
fun `intersect no overlap`() {
val a = listOf(1, 2)
val b = listOf(3, 4)
assertEquals(emptySet<Int>(), a.myIntersect(b))
}
@Test
fun `intersect preserves order from first`() {
val a = listOf(4, 3, 2, 1)
val b = listOf(1, 3)
val result = a.myIntersect(b).toList()
assertEquals(listOf(3, 1), result)
}
交集只保留兩邊都有的元素。順序跟第一個集合走，所以 [4, 3, 2, 1] 和 [1, 3] 的交集是 [3, 1]，不是 [1, 3]
infix fun <T> Iterable<T>.myIntersect(other: Iterable<T>): Set<T> {
val otherSet = other.toHashSet()
val result = LinkedHashSet<T>()
for (element in this) {
if (otherSet.contains(element)) {
result.add(element)
}
}
return result
}
先把 other 轉成 HashSet，查詢效率 O(1)。然後走 this 的每個元素，如果在 otherSet 裡面就加進結果
為什麼不直接 for (element in other) 來查詢？因為如果 other 是 List，contains 是 O(n)，整個操作就變成 O(n²)。轉成 HashSet 只需要一次 O(n)，之後每次查詢 O(1)，總共 O(n + m)
這個實作已經是 stdlib 的形狀，差別只在 stdlib 用 retainAll 取代手動迴圈，後面的「與 stdlib 原始碼比較」會對照原始碼
@Test
fun `subtract integers`() {
val a = listOf(1, 2, 3, 4, 5)
val b = listOf(3, 4)
val result = a.mySubtract(b)
assertEquals(setOf(1, 2, 5), result)
}
@Test
fun `subtract all`() {
val a = listOf(1, 2, 3)
val b = listOf(1, 2, 3, 4)
assertEquals(emptySet<Int>(), a.mySubtract(b))
}
@Test
fun `subtract preserves order`() {
val a = listOf(5, 3, 1, 4, 2)
val b = listOf(3, 4)
val result = a.mySubtract(b).toList()
assertEquals(listOf(5, 1, 2), result)
}
差集是「我有但你沒有」的元素。[1, 2, 3, 4, 5] 扣掉 [3, 4] 剩下 [1, 2, 5]
要注意差集有方向性，誰扣誰結果完全不一樣。第二個測試就是在講這件事：a 是 [1, 2, 3]、b 是 [1, 2, 3, 4]，a 的元素全都在 b 裡面，所以 a.mySubtract(b) 是空集合；反過來寫 b.mySubtract(a) 得到的卻是 [4]。聯集和交集左右對調，內容還是一樣(只有順序可能不同)，差集是這三個運算裡唯一不對稱的
infix fun <T> Iterable<T>.mySubtract(other: Iterable<T>): Set<T> {
val otherSet = other.toHashSet()
val result = LinkedHashSet<T>()
for (element in this) {
if (!otherSet.contains(element)) {
result.add(element)
}
}
return result
}
跟 intersect 幾乎一樣，差別只在判斷條件反過來：intersect 是 contains 才加，subtract 是 !contains 才加
跟 intersect 同一個道理，stdlib 用 removeAll 一行取代手動迴圈，邏輯本身沒有更多可改的地方，後面的原始碼比較段落會放在一起看
union / intersect / subtract 是集合運算，回傳 Set<T>。plus 和 minus 是不同的東西，它們定義在 Collection / Iterable 上、回傳 List，不會去除重複。要注意 stdlib 另有定義在 Set<T> 上的 plus overload，那個版本回傳 Set 而且會去除重複；這裡手刻的是 List 版本
myPlus 有兩個 overload，單一元素和集合各一個，測試要分開顧。重點放在「不改動原集合」跟「重複的元素照留」
@Test
fun `plus appends element without mutating original`() {
val original = listOf(1, 2, 3)
val result = original.myPlus(4)
assertEquals(listOf(1, 2, 3, 4), result)
assertEquals(listOf(1, 2, 3), original) // 原集合沒被動到
}
@Test
fun `plus keeps duplicates`() {
assertEquals(listOf(1, 2, 2), listOf(1, 2).myPlus(2))
}
@Test
fun `plus collection appends every element`() {
val original = listOf(1, 2)
val result = original.myPlus(listOf(2, 3))
assertEquals(listOf(1, 2, 2, 3), result)
assertEquals(listOf(1, 2), original) // 原集合一樣沒被動到
}
@Test
fun `plus accepts an Iterable that is not a Collection`() {
val result = listOf(1, 2).myPlus(sequenceOf(3, 4).asIterable())
assertEquals(listOf(1, 2, 3, 4), result)
}
第三個測試驗集合版：[1, 2] 加上 [2, 3] 得到 [1, 2, 2, 3]，兩個 2 都在，這跟 union 是完全不同的行為
最後一個測試特別挑了一個不是 Collection 的 Iterable，也就是 Sequence.asIterable() 的回傳值。現在看起來多餘，但後面 Refactor 會依 is Collection 把實作拆成兩條路，這個測試涵蓋的正是拿不到 size 的那條
myMinus 的測試重點在兩個 overload 的行為差異：單一元素只移除第一個符合者，集合版本移除所有符合者
@Test
fun `minus single element removes only the first match`() {
val list = listOf(1, 2, 3, 2, 1)
assertEquals(listOf(1, 3, 2, 1), list.myMinus(2))
}
@Test
fun `minus collection removes every match`() {
val list = listOf(1, 2, 3, 2, 1)
assertEquals(listOf(1, 3, 1), list.myMinus(listOf(2)))
}
@Test
fun `minus does not mutate original`() {
val original = listOf(1, 2, 3)
original.myMinus(2)
assertEquals(listOf(1, 2, 3), original)
}
先做 myPlus
fun <T> Collection<T>.myPlus(element: T): List<T> {
val result = ArrayList<T>(size + 1)
result.addAll(this)
result.add(element)
return result
}
fun <T> Collection<T>.myPlus(elements: Iterable<T>): List<T> {
val result = ArrayList<T>()
result.addAll(this)
for (element in elements) {
result.add(element)
}
return result
}
plus 建立一份新的 List，把原本的元素複製過去，再加上新元素。原本的集合不會被改動
加入單一元素的版本預先分配 size + 1 的容量，避免 ArrayList 擴容
在 Kotlin stdlib 裡，list + element 會被編譯器轉換成 list.plus(element) 的呼叫。day 09 初探 operator 時提過，+ / - 這些運算子背後其實是對應名稱的函式，這裡的 plus / minus 就是那套機制套在集合上的實際應用。day 33 會把 operator overloading 完整講一遍
再做 myMinus
fun <T> Iterable<T>.myMinus(element: T): List<T> {
val result = ArrayList<T>()
var removed = false
for (item in this) {
if (!removed && item == element) {
removed = true
} else {
result.add(item)
}
}
return result
}
fun <T> Iterable<T>.myMinus(elements: Iterable<T>): List<T> {
val removeSet = elements.toHashSet()
val result = ArrayList<T>()
for (item in this) {
if (!removeSet.contains(item)) {
result.add(item)
}
}
return result
}
兩個 minus 版本行為不一樣，這是個容易踩到的坑
減去單一元素時，只移除第一個符合的。[1, 2, 3, 2, 1].myMinus(2) 得到 [1, 3, 2, 1]，第二個 2 還在
減去一個集合時，移除所有符合的。[1, 2, 3, 2, 1].myMinus(listOf(2)) 得到 [1, 3, 1]，兩個 2 都被拿掉了
為什麼？因為減去集合的版本用 HashSet 存要移除的元素，每次比對都會命中。單一元素版本用 removed flag 控制只移除一次
val list = listOf(1, 2, 3, 2, 1)
list.myMinus(2) // [1, 3, 2, 1] — 只移除第一個 2
list.myMinus(listOf(2)) // [1, 3, 1] — 移除所有 2
這兩組函式沒有 Lambda 參數，也就沒有 inline 的必要，結構上已經跟 stdlib 一致。唯一可以再靠近一點的是集合版 myPlus：stdlib 會先判斷 elements 是不是 Collection，是的話就用 ArrayList(size + elements.size) 預先分配容量，不是才退回沒有精確容量的 ArrayList(this) 再 addAll
fun <T> Collection<T>.myPlus(elements: Iterable<T>): List<T> {
if (elements is Collection) {
val result = ArrayList<T>(this.size + elements.size)
result.addAll(this)
result.addAll(elements)
return result
}
val result = ArrayList<T>(this)
result.addAll(elements)
return result
}
剛才那個傳 Sequence.asIterable() 的測試到這裡就派上用場了，改完之後兩條路都要是綠的，不然只有走 is Collection 的情況被驗到
這是整個 Collection 篇最後一次 Refactor。is Collection 在這裡的用途跟 day 22 myTake 那次不一樣：myTake 拿 size 是為了判斷「要的比有的還多，直接 toList() 走人」，這裡拿 size 是為了把容量一次開好。共通點是兩邊都靠 is Collection 換到「事先知道有幾個元素」這個資訊
原始碼位置：kotlin.collections 的 _Collections.kt
stdlib 的三個集合運算都是 infix 函式，底層做法跟我們幾乎一樣
public infix fun <T> Iterable<T>.union(other: Iterable<T>): Set<T> {
val set = this.toMutableSet() // toMutableSet() 回傳 LinkedHashSet，已含 this 的元素
set.addAll(other)
return set
}
public infix fun <T> Iterable<T>.intersect(other: Iterable<T>): Set<T> {
val set = this.toMutableSet()
set.retainAll(other)
return set
}
public infix fun <T> Iterable<T>.subtract(other: Iterable<T>): Set<T> {
val set = this.toMutableSet()
set.removeAll(other)
return set
}
stdlib 的 union 先用 toMutableSet() 把 this 收進一個 LinkedHashSet，再 addAll(other)，跟我們手動跑兩個迴圈的效果一樣，只是更精簡。intersect 用 retainAll 而不是手動迴圈。toMutableSet() 回傳 LinkedHashSet，保留插入順序。retainAll 移除不在 other 裡面的元素，效果跟我們的做法一樣
stdlib 的 plus 和 minus 定義在 _Collections.kt 裡，有多個 overload(單一元素、Array、Iterable、Sequence)。我們只實作了最常用的兩個
集合運算篇兩篇到這裡結束。day 25 靠 HashSet 去除重複，做出 distinct / distinctBy；day 26 把 HashSet 的查詢特性推到聯集、交集、差集，再帶出 plus / minus 這組「不會去除重複、回傳 List」的運算子。同樣是處理重複與成員關係，回傳 Set 還是 List、會不會去除重複，是這部分最需要分清楚的地方
而這也是整個 Collection 篇的收尾。從 day 05 的 filter 走到這裡手刻了超過 50 個函式，可以發現幾乎所有函式都遵循類似的模式
inline fun <T> Iterable<T>.myXxx(predicate: (T) -> Boolean): List<T> {
val result = ArrayList<T>() // 建立結果容器
for (element in this) { // 走過每個元素
// 某種判斷邏輯
result.add(element) // 符合就加進去
}
return result // 回傳新 List
}
inline + for 迴圈 + ArrayList 累積 + 回傳新 List。這個模式好讀、好寫，大多數場景效能也夠
但這個模式有個共同的代價：每個函式都會立刻分配一個新的容器，單獨呼叫沒問題，串成一條鏈就未必了。這也是下一篇進入 Sequence 的重點
| 函式 | 篇號 | 用途 |
|---|---|---|
myDistinct |
day 25 | 去掉重複元素，保留首次出現的順序 |
myDistinctBy |
day 25 | 依 selector 算出的鍵去除重複 |
myUnion |
day 26 | 聯集，兩邊元素合一份回傳 Set |
myIntersect |
day 26 | 交集，只留兩邊都有的元素 |
mySubtract |
day 26 | 差集，留下「我有你沒有」的元素 |
myPlus |
day 26 | 加入元素或集合，回傳新 List，不會去除重複 |
myMinus |
day 26 | 移除元素或集合，回傳新 List |
集合運算的底層還是 HashSet。union 用 LinkedHashSet 收集兩邊的元素，intersect 和 subtract 用 toHashSet() 把另一邊轉成 Set 來加速查詢。plus 和 minus 不一樣，它們操作 List、不會去除重複，行為跟集合運算有明顯差異
最容易混在一起的是 subtract 和集合版的 minus，兩個都是「扣掉另一邊有的元素」，實作也都是把另一邊轉成 HashSet 再逐一比對，差別只在裝結果的容器：subtract 回傳 Set，重複的元素只留一份；minus 回傳 List，重複的元素原封不動留著。listOf(1, 2, 2, 3).subtract(listOf(3)) 得到 [1, 2]，listOf(1, 2, 2, 3).minus(listOf(3)) 得到 [1, 2, 2]
Collection 篇到這裡結束。下一篇開始 Sequence 篇，從 Eager 到 Lazy，看看為什麼鏈式操作需要延遲執行
同步刊登於 Blog
圖片來源：AI 產生
iThome鐵人賽
看影片追技術