Разработчики реализуют собственные версии методов myContains и myElementAt для глубокого понимания алгоритмов поиска в Kotlin

這篇文章會用 TDD 手刻 myContains、myElementAt、myElementAtOrNull、myElementAtOrElse，收束篩選與尋找篇 @Test fun `contains returns true when element exists`() { val numbers = listOf(1, 2, 3, 4, 5) assertTrue(numbers.myContains(3)) } @Test fun `contains returns false when element not found`() { val numbers = listOf(1, 2, 3) assertFalse(numbers.myContains(99)) } @Test fun `contains on empty list returns false`() { val empty = emptyList<Int>() assertFalse(empty.myContains(1)) } @Test fun `contains with string`() { val words = listOf("hello", "world") assertTrue(words.myContains("hello")) assertFalse(words.myContains("foo")) } 測試的範圍說明一下。contains 沒有例外，找不到就回傳 false，所以涵蓋找得到、找不到、空集合就夠了，不用硬湊例外案例 換成共用的 employees 資料也一樣。contains 比的是元素本身，Employee 是 data class，所以 id、name、department、salary、age 全部相同才算同一筆 val alice = employees[0] employees.myContains(alice) // true employees.myContains(Employee(99, "Zoe", "Engineering", 90000, 29)) // false fun <T> Iterable<T>.myContains(element: T): Boolean { if (this is Collection) { return contains(element) } for (item in this) { if (item == element) { return true } } return false } 先用 is Collection 檢查。Collection 介面本身就有 contains 方法，委派過去能讓具體實作用自己的方式比對。HashSet 的 contains 是 O(1)，ArrayList 還是 O(n) 線性掃描，但有最佳化的實作就能直接吃到，不要自己遍歷 一般 Iterable 就只能 for 迴圈逐一比對了 day 08 已經有 myIndexOf 了，「存不存在」這個問題可以直接問它 fun <T> Iterable<T>.myContains(element: T): Boolean { if (this is Collection) { return contains(element) } return myIndexOf(element) >= 0 } 少一個自己寫的迴圈，多一層既有函式的重用。等一下看 stdlib 原始碼，會發現它就是這樣寫的 in 運算子的真相 Kotlin 裡寫 3 in numbers 會編譯成 numbers.contains(3)。這個 in 是 contains 的 operator 語法糖 要讓自己的函式支援 in 語法，除了加上 operator 修飾，函式名稱還必須精確叫 contains operator fun <T> Iterable<T>.contains(element: T): Boolean { ... } 我們的 myContains 不能寫成 3 in list 來呼叫，而且問題不是出在沒加 operator。函式名稱不是 contains，就算硬加上 operator，編譯器也會直接丟出 'operator' modifier is not applicable to function: illegal function name. 拒絕你 // 編譯不過：名字不是 contains operator fun <T> Iterable<T>.myContains(element: T): Boolean { ... } // 呼叫端也寫不出來，in 只認 contains，不會去找 myContains 3 in numbers 這也是為什麼本篇維持 myContains 這個名字、不加 operator，完整機制留到 day 33 再講 簡單預告一下：Kotlin 的 operator 關鍵字讓特定命名的函式可以用運算子呼叫。contains 對應 in，plus 對應 +，get 對應 []。命名要精確對上，少一個字母都不行 @Test fun `elementAt returns element at index`() { val numbers = listOf(10, 20, 30, 40, 50) assertEquals(30, numbers.myElementAt(2)) } @Test fun `elementAt throws on negative index`() { val numbers = listOf(1, 2, 3) assertThrows<IndexOutOfBoundsException> { numbers.myElementAt(-1) } } @Test fun `elementAt throws on out of bounds`() { val numbers = listOf(1, 2, 3) assertThrows<IndexOutOfBoundsException> { numbers.myElementAt(10) } } myElementAtOrNull 的測試把 assertThrows 換成 assertNull，myElementAtOrElse 則多測 Lambda 是否收到 index 作為參數 @Test fun `elementAtOrNull returns null on out of bounds`() { val numbers = listOf(1, 2, 3) assertNull(numbers.myElementAtOrNull(10)) assertNull(numbers.myElementAtOrNull(-1)) } @Test fun `elementAtOrElse passes index to lambda`() { val numbers = listOf(1, 2, 3) assertEquals(20, numbers.myElementAtOrElse(10) { index -> index * 2 }) } employees 的例子更接近日常查表情境 employees.myElementAt(2).name // Charlie employees.myElementAtOrNull(99) // null employees.myElementAtOrElse(99) { Employee(-1, "Unknown", "N/A", 0, 0) } fun <T> Iterable<T>.myElementAt(index: Int): T { if (this is List) { return get(index) } if (index < 0) { throw IndexOutOfBoundsException("Index $index is out of bounds.") } var count = 0 for (element in this) { if (count == index) { return element } count++ } throw IndexOutOfBoundsException("Index $index is out of bounds of collection of size $count.") } is List 分支直接呼叫 get(index)，在 ArrayList 這類 RandomAccess 實作上是 O(1)(LinkedList 仍要走過去，是 O(n))。一般 Iterable 則一定要跑迴圈數到那個位置 myElementAtOrNull 把拋例外改成回傳 null fun <T> Iterable<T>.myElementAtOrNull(index: Int): T? { if (this is List) { return if (index in 0..lastIndex) get(index) else null } if (index < 0) { return null } var count = 0 for (element in this) { if (count == index) { return element } count++ } return null } 注意 is List 分支不能直接呼叫 get(index)，因為 index 超出範圍會拋例外。要先檢查 index in 0..lastIndex myElementAtOrElse 更有意思 inline fun <T> Iterable<T>.myElementAtOrElse( index: Int, defaultValue: (Int) -> T ): T { if (this is List) { return if (index in 0..lastIndex) get(index) else defaultValue(index) } if (index < 0) { return defaultValue(index) } var count = 0 for (element in this) { if (count == index) { return element } count++ } return defaultValue(index) } defaultValue 是一個 Lambda，接收 index 作為參數。超出範圍時不是回傳固定值，而是讓呼叫端自己決定怎麼算出預設值。比 OrNull 更有彈性 // 超出範圍就用 index 自己算 numbers.myElementAtOrElse(10) { index -> index * 2 } C# 沒有對應的 ElementAtOrElse。想做類似的事得自己寫 extension method 或用三元運算子 Lambda 預設值 vs 固定預設值，差別在 lazy 計算。固定值 getOrDefault(expensiveCall()) 不管要不要都先算好；Lambda 版只在落到 default 那條路時才呼叫，適合預設值很貴(資料庫查詢、IO、複雜運算)的情境 // 預設值當參數傳入，呼叫前就先求值：不管 key 存不存在，DB 查詢都會執行 map.getOrDefault(key, queryDatabase()) // Lambda 版只在缺值時才呼叫 map.getOrElse(key) { queryDatabase() } 函式式語言傳統都偏好 lambda 版的 default。stdlib 把這個模式做得很廣，getOrElse、getOrPut、computeIfAbsent 都是同樣的做法，把「需要時才算」做進 API 設計裡 回頭看三個函式，迴圈的部分長得一模一樣。最通用的是 myElementAtOrElse，越界時要做什麼完全由 Lambda 決定，那 myElementAt 就可以改成委派給它，越界的 Lambda 直接拋例外 fun <T> Iterable<T>.myElementAt(index: Int): T { if (this is List) { return get(index) } return myElementAtOrElse(index) { throw IndexOutOfBoundsException("Index $index is out of bounds.") } } stdlib 的 Iterable<T>.elementAt 就是這樣做的：自己只留 List 的快速路徑，剩下的交給 elementAtOrElse，連例外都是在 Lambda 裡拋的 原始碼位置：kotlin.collections 的 _Collections.kt stdlib 的 elementAt 跟我們結構相同，都有 is List 的最佳化分支 elementAtOrElse 有個小差異。stdlib 定義在 Iterable<T> 上的版本是一般函式，沒有 inline；只有 List<T> 的多載版本標了 @InlineOnly inline，因為 List 版只是一行 index 檢查加 get，inline 掉最划算。我們手刻的 Iterable 版直接加了 inline，比 stdlib 激進一點，行為則一致 contains 在 stdlib 有兩個版本。Collection<T> 介面本身就有 contains 成員方法，由各個實作類別自己決定怎麼比對；stdlib 另外提供 Iterable<T> 的擴充版本，給不是 Collection 的一般 Iterable 用 public operator fun <T> Iterable<T>.contains(element: T): Boolean { if (this is Collection) return contains(element) return indexOf(element) >= 0 } 跟我們 Refactor 後的 myContains 是同一個結構：先委派給 Collection 的成員方法，不是 Collection 就問 indexOf。注意它有 operator 修飾，名字也叫 contains，所以一般 Iterable 寫 3 in iterable 才有得編譯 Kotlin 支援的 operator 函式不少，這裡列幾個常見的 day 26 會用到 plus 和 minus 做集合運算，day 33 會完整講解 operator 多載的機制 篩選與尋找篇到這裡結束了。從 day 05 到 day 09，走過的路線是 filter 系列(篩出多個) → first / last / single(找一個) → any / all / none / count(問有沒有) → find / indexOf(找位置) → contains / elementAt(存在性和直接取值) 這些操作有個共同模式：for 迴圈 + 條件判斷 + 決定什麼時候停。any、first、indexOf、contains 一找到就回傳，後面的元素連看都不用看；filter、count、single、last 則非得跑完整個集合才知道答案。結構都很單純，差別只在停的時機和回傳值 myFilter 是 day 03 手刻、day 04 加上 inline 的，day 05 只做回顧，所以沒列進來 in 不是關鍵字魔法，寫 3 in list 編譯出來就是 list.contains(3)，而且函式名稱少一個字母都不行。day 33 會把整套 operator 的規則講完 elementAt 的三個變體則是 Kotlin 處理「越界」的一貫做法：拋例外、回傳 null、用 Lambda 算預設值。同一個問題給三種強度的答案，讓 caller 自己選。這個模式在 first / firstOrNull 上已經看過一次，後面還會一直出現 下一篇進入轉換篇。Lambda 的簽名從 (T) -> Boolean(判斷)變成 (T) -> R(轉換)，複雜度會稍微上升。day 10 從 map / mapNotNull / mapIndexed 開始 同步刊登於 Blog 圖片來源：AI 產生