創(chuàng)建數(shù)組

字面量創(chuàng)建

• 可以使用數(shù)組字面量來初始化一個(gè)數(shù)組，它是一種以數(shù)組集合來寫一個(gè)或者多個(gè)值的簡(jiǎn) 寫方式。數(shù)組字面量寫做一系列的值，用逗號(hào)分隔，用方括號(hào)括起來

  
  
  01

字面量創(chuàng)建空數(shù)組

• 創(chuàng)建空數(shù)組的時(shí)候必須攜帶類型信息

• 如果內(nèi)容已經(jīng)提供了類型信息，比如說作為函數(shù)的實(shí)際參數(shù)或者已經(jīng)分類了的變量或常 量，你可以通過空數(shù)組字面量來創(chuàng)建一個(gè)空數(shù)組

  
  
  02

初始化器

• 使用初始化器有兩種方式
  類型
  Array<類型>()

03

初始化器參數(shù)

• init(repeating repeatedValue: Element, count: Int)

• init(arrayLiteral elements: Element...)

  
  
  04

• init<S>(_ elements: S) where S : Sequence, Self.Element == S.Element - init(from decoder: Decoder) throws

  
  
  05

數(shù)組遍歷和索引

數(shù)組遍歷

• For-In
• forEach方法

無法使用 break 或 continue 跳出或者跳過循環(huán)
使用 return 只能退出當(dāng)前一次循環(huán)的執(zhí)行體

06

• 同時(shí)得到索引和值 enumerated()

  
  
  07

• 使用 Iterator 遍歷數(shù)組

  
  
  08

索引

• startIndex 返回第一個(gè)元素的位置，對(duì)于數(shù)組來說，永遠(yuǎn)都是 0。
• endIndex 返回最后一個(gè)元素索引 +1 的位置，對(duì)于數(shù)組來說，等同于count 。
• 如果數(shù)組為空，startIndex 等于 endIndex 。

• indices 獲取數(shù)組的索引區(qū)間

  
  
  09

數(shù)組的查找操作

判斷是否包含指定元素

• contains(_:) 判斷數(shù)組是否包含給定元素
• contains(where:) 判斷數(shù)組是否包含符合給定條件的元素

判斷所有元素符合某個(gè)條件

• allSatisfy(_:) 判斷數(shù)組的每一個(gè)元素都符合給定的條件

  
  
  10

查找元素

• first 返回?cái)?shù)組第一個(gè)元素(optional)，如果數(shù)組為空，返回 nil 。
• last 返回?cái)?shù)組最后一個(gè)元素(optional)，如果數(shù)組為空，返回 nil 。
• first(where:) 返回?cái)?shù)組第一個(gè)符合給定條件的元素(optional)。
• last(where:) 返回?cái)?shù)組最后一個(gè)符合給定條件的元素(optional)。

11

查找索引

• firstIndex(of:) 返回給定的元素在數(shù)組中出現(xiàn)的第一個(gè)位置(optional)

• lastIndex(of:) 返回給定的元素在數(shù)組中出現(xiàn)的最后一個(gè)位置(optional)

  
  
  12

• firstIndex(where:) 返回符合條件的第一個(gè)元素的位置(optional)

• lastIndex(where:) 返回符合條件的最后一個(gè)元素的位置(optional)

  
  
  13

查找最大最小元素

• min() 返回?cái)?shù)組中最小的元素

• max() 返回?cái)?shù)組中最大的元素

  
  
  14

• min(by:) 利用給定的方式比較元素并返回?cái)?shù)組中的最小元素

• max(by:) 利用給定的方式比較元素并返回?cái)?shù)組中的最大元素

  
  
  15

數(shù)組添加和刪除

在末尾添加

• append(_:) 在末尾添加一個(gè)元素

• append(contentsOf: ) 在末尾添加多個(gè)元素

  
  
  16

在任意位置插入

• insert(_:at:) 在指定的位置插入一個(gè)元素
• insert(contentsOf: at:) 在指定位置插入多個(gè)元素

17

字符串也是 Collection

• 字符串也是 Collection ，Element 是 Character 類型。

  
  
  18

移除單個(gè)元素

• remove(at:) 移除并返回指定位置的一個(gè)元素

• removeFirst() 移除并返回?cái)?shù)組的第一個(gè)元素

  
  
  19

• removeLast() 移除并返回?cái)?shù)組的最后一個(gè)元素

• popLast() 移除并返回?cái)?shù)組的最后一個(gè)元素(optional)，如果數(shù)組為空返回nil 。

  
  
  20

移除多個(gè)元素

• removeFirst(:) 移除數(shù)組前面多個(gè)元素

• removeLast(:) 移除數(shù)組后面多個(gè)元素

  
  
  21

• removeSubrange(_:) 移除數(shù)組中給定范圍的元素

• removeAll() 移除數(shù)組所有元素

• removeAll(keepingCapacity:) 移除數(shù)組所有元素，保留數(shù)組容量

  
  
  22

ArraySlice

移除多個(gè)元素

• ArraySlice 是數(shù)組或者其他 ArraySlice 的一段連續(xù)切片，和原數(shù)組共享內(nèi)存。

• 當(dāng)要改變 ArraySlice 的時(shí)候，ArraySlice 會(huì) copy 出來，形成單獨(dú)內(nèi)存。 - ArraySlice 擁有和 Array 基本完全類似的方法

  
  
  23

通過 Drop 得到 ArraySlice

• dropFirst(:) “移除”原數(shù)組前面指定個(gè)數(shù)的元素得到一個(gè) ArraySlice
• dropLast(:) “移除”原數(shù)組后面指定個(gè)數(shù)的元素得到一個(gè) ArraySlice

• drop(:) “移除”原數(shù)組符合指定條件的元素得到一個(gè) ArraySlice

  
  
  24

通過 prefix 得到 ArraySlice

• prefix() 獲取數(shù)組前面指定個(gè)數(shù)的元素組成的 ArraySlice
• prefix(upTo: ) 獲取數(shù)組到指定位置(不包含指定位置)前面的元素組成的 ArraySlice
• prefix(through: ) 獲取數(shù)組到指定位置(包含指定位置)前面的元素組成的 ArraySlice

• prefix(while: ) 獲取數(shù)組前面符合條件的元素(到第一個(gè)不符合條件的元素截止)組成的 ArraySlice

  
  
  25

通過 suffix 得到 ArraySlice

• suffix() 獲取數(shù)組后面指定個(gè)數(shù)的元素組成的 ArraySlice

• suffix(from: ) 獲取數(shù)組從指定位置到結(jié)尾(包含指定位置)的元素組成的 ArraySlice

  
  
  26

通過 Range 得到 ArraySlice

• 可以通過對(duì)數(shù)組下標(biāo)指定 Range 獲取 ArraySlice，可以使用閉區(qū)間、半開半閉區(qū)間、單側(cè)區(qū) 間、甚至可以只使用 ... 來獲取整個(gè)數(shù)組組成的 ArraySlice 。

  
  
  27

ArraySlice 轉(zhuǎn)為 Array

• ArraySlice 無法直接賦值給一個(gè) Array 的常量或變量，需要使用 Array(slice) 。

  
  
  28

ArraySlice 和原 Array 相互獨(dú)立

• ArraySlice 和原 Array 是相互獨(dú)立的，它們添加刪除元素不會(huì)影響對(duì)方

  
  
  29

重排操作

數(shù)組元素的隨機(jī)化

• shuffle() 在原數(shù)組上將數(shù)組元素打亂，只能作用在數(shù)組變量上。
• shuffled() 返回原數(shù)組的隨機(jī)化數(shù)組，可以作用在數(shù)組變量和常量上。

30

數(shù)組的逆序

• reverse() 在原數(shù)組上將數(shù)組逆序，只能作用在數(shù)組變量上。

• reversed() 返回原數(shù)組的逆序“集合表示”，可以作用在數(shù)組變量和常量上，該方法不 會(huì)分配新內(nèi)存空間。

  
  
  31

數(shù)組的分組

• partition(by belongsInSecondPartition: (Element) throws -> Bool) 將數(shù)組以某個(gè) 條件分組，數(shù)組前半部分都是不符合條件的元素，數(shù)組后半部分都是符合條件的元素。

  
  
  32

數(shù)組的排序

• sort() 在原數(shù)組上將元素排序，只能作用于數(shù)組變量。
• sorted() 返回原數(shù)組的排序結(jié)果數(shù)組，可以作用在數(shù)組變量和常量上。

33

交換數(shù)組兩個(gè)元素

• swapAt(::) 交換指定位置的兩個(gè)元素
  
  34

拼接操作

字符串?dāng)?shù)組拼接

• joined() 拼接字符串?dāng)?shù)組里的所有元素為一個(gè)字符串

• joined(separator:) 以給定的分隔符拼接字符串?dāng)?shù)組里的所有元素為一個(gè)字符串

  
  
  35

元素為 Sequence 數(shù)組的拼接

• joined() 拼接數(shù)組里的所有元素為一個(gè)更大的 Sequence
• joined(separator:) 以給定的分隔符拼接數(shù)組里的所有元素為一個(gè)更大的 Sequence

36

數(shù)組探秘

數(shù)組的協(xié)議結(jié)構(gòu)

37

Sequence

• 一個(gè)序列 (sequence) 代表的是一系列具有相同類型的值，你可以對(duì)這些值進(jìn)行迭代。

  
  
  38

IteratorProtocol

• Sequence 通過創(chuàng)建一個(gè)迭代器來提供對(duì)元素的訪問。迭代器每次產(chǎn)生一個(gè)序列的值， 并且當(dāng)遍歷序列時(shí)對(duì)遍歷狀態(tài)進(jìn)行管理。

• 當(dāng)序列被耗盡時(shí)，next() 應(yīng)該返回 nil 。

  
  
  39

定義自己的 Sequence

40

Collection

• 一個(gè) Collection 是滿足下面條件的 Sequence
  穩(wěn)定的 Sequence，能夠被多次遍歷且保持一致
  除了線性遍歷以外，集合中的元素也可以通過下標(biāo)索引的方式被獲取到
  和 Sequence 不同，Collection 類型不能是無限的

  
  
  41

Array 的迭代器

42

Array 的下標(biāo)訪問

43

Array 的 buffer

44

_ContiguousArrayBuffer

45

_ContiguousArrayBuffer 的 getElement

46

UnsafeMutablePointer 的下標(biāo)操作

47

問題:endIndex vs count

48

索引

49

50

實(shí)現(xiàn)棧和隊(duì)列

Stack

• 棧( Stack )是一種后入先出( Last in First Out )的數(shù)據(jù)結(jié)構(gòu)，僅限定在棧頂進(jìn)行插 入或者刪除操作。棧結(jié)構(gòu)的實(shí)際應(yīng)用主要有數(shù)制轉(zhuǎn)換、括號(hào)匹配、表達(dá)式求值等等。

  
  
  51

Queue

• 隊(duì)列在生活中非常常見。排隊(duì)等位吃飯、在火車站買票、通過高速路口等，這些生活中 的現(xiàn)象很好的描述了隊(duì)列的特點(diǎn):先進(jìn)先出 ( FIFO, first in first out )，排在最前面的 先出來，后面來的只能排在最后面。

52

Set

• Set 是指具有某種特定性質(zhì)的具體的或抽象的對(duì)象匯總而成的集體。其中，構(gòu)成 Set 的 這些對(duì)象則稱為該 Set 的元素。

集合的三個(gè)特性

• 確定性 :給定一個(gè)集合，任給一個(gè)元素，該元素或者屬于或者不屬于該集合，二者必居其一。
• 互斥性 : 一個(gè)集合中，任何兩個(gè)元素都認(rèn)為是不相同的，即每個(gè)元素只能出現(xiàn)一次。
• 無序性 : 一個(gè)集合中，每個(gè)元素的地位都是相同的，元素之間是無序的。

Swift 里面的集合

• Swift 的集合類型寫做 Set<Element>，這里的 Element 是 Set 要儲(chǔ)存的類型。不同與數(shù) 組，集合沒有等價(jià)的簡(jiǎn)寫。

創(chuàng)建 Set

• 使用初始化器語法來創(chuàng)建一個(gè)確定類型的空 Set

• 使用數(shù)組字面量創(chuàng)建 Set

  
  
  53

Set 類型的哈希值

• 為了能讓類型儲(chǔ)存在 Set 當(dāng)中，它必須是可哈希的——就是說類型必須提供計(jì)算它自身哈希值的方法。
• 所有 Swift 的基礎(chǔ)類型(比如 String, Int, Double, 和 Bool)默認(rèn)都是可哈希的，并且可以用于 Set 或者 Dictionary 的鍵。

54

• 自定義類型需要實(shí)現(xiàn) Hashable 協(xié)議

  
  
  55

訪問和修改 Set

遍歷 Set

• 可以用for-in遍歷set

• 因?yàn)?Set 是無序的，如果要順序遍歷 Set，使用 sorted()方法。

  
  
  56

訪問 Set

• 使用 count 獲取 Set 里元素個(gè)數(shù)

• 使用 isEmpty 判斷 Set 是否為空

  
  
  57

添加元素

• insert(_:) 添加一個(gè)元素到 Set

• update(with:) 如果已經(jīng)有相等的元素，替換為新元素。如果 Set 中沒有，則插入。

  
  
  58

移除元素

• filter(_:) 返回一個(gè)新的 Set，新 Set 的元素是原始 Set 符合條件的元素。

  
  
  59

• remove(_:) 從 Set 當(dāng)中移除一個(gè)元素，如果元素是 Set 的成員就移除它，并且返回移除的 值，如果合集沒有這個(gè)成員就返回 nil 。

• removeAll() 移除所有元素

  
  
  60

• removeFirst() 移除 Set 的第一個(gè)元素，因?yàn)?Set 是無序的，所以第一個(gè)元素并不是放入的 第一個(gè)元素。

  
  
  61

執(zhí)行 Set 操作

基本 Set 操作的定義

62

• intersection(_:) 交集，由屬于A且屬于B的相同元素組成的集合，記作A∩B(或B∩A)。
• union(_:) 并集，由所有屬于集合A或?qū)儆诩螧的元素所組成的集合，記作A∪B(或B∪A)。
• symmetricDifference(_:) 對(duì)稱差集，集合A與集合B的對(duì)稱差集定義為集合A與集合B中所有不屬 于A∩B的元素的集合。

• subtracting(_:) 相對(duì)補(bǔ)集，由屬于A而不屬于B的元素組成的集合，稱為B關(guān)于A的相對(duì)補(bǔ)集，記 作A-B或A\B。

  
  
  63

Set 判斷方法

• isSubset(of:) 判斷是否是另一個(gè) Set 或者 Sequence 的子集 - isSuperset(of:) 判斷是否是另一個(gè) Set 或者 Sequence 的超集
• isStrictSubset(of:) 和 isStrictSuperset(of:) 判斷是否是另一個(gè) Set 的子集或者超集，但是 又不等于另一個(gè) Set 。

• isDisjoint(with:) 判斷兩個(gè) Set 是否有公共元素，如果沒有返回 true，如果有返回 false

  
  
  64

Set 算法

• 給定一個(gè)集合，返回這個(gè)集合所有的子集

思路1 - 位

• 思路:解這道題的思想本質(zhì)上就是元素選與不選的問題，于是我們就可以想到用二進(jìn)制來代 表選與不選的情況?！?”代表這個(gè)元素已經(jīng)選擇，而“0”代表這個(gè)元素沒有選擇。假如三 個(gè)元素 A B C ，那么 101 就代表 B 沒有選擇，所以 101 代表的子集為 AC 。

  
  
  65

思路2 - 遞歸

• 思路:如果只有一個(gè)元素，那么它的子集有兩個(gè)，分別是本身和空集，然后在已經(jīng)有一個(gè)元素的 子集的基礎(chǔ)上，第二個(gè)元素有兩種選法，那就是加入到前面的子集里面或者不加入到前面的子集 里面，也就是選與不選的問題。而前面的子集一共有兩個(gè)，對(duì)每一個(gè)子集都有來自于下一個(gè)元素 的加入和不加入兩種選法。那么就可以得出兩個(gè)元素的子集一共有四個(gè)。依次類推，就可以得出 n 的元素所有子集(這里 n 個(gè)元素的子集一共有 2n 個(gè)，非空子集一共有 2n-1 個(gè))。

  
  
  66

Set 實(shí)現(xiàn)探秘

從 Set 的 insert 說起

67

_NativeSet 的 find 方法

68

HashTable

69

70

線性探測(cè)的開放尋址法

71

_NativeSet 的 insertNew

72

HashTable 的 insertNew

73

_NativeSet 的 uncheckedInitialize

74

字典

Dictionary

• 字典儲(chǔ)存無序的互相關(guān)聯(lián)的同一類型的鍵和同一類型的值的集合
• 字典類型的全寫方式 Dictionary<Key, Value>，簡(jiǎn)寫方式 [Key: Value]，建議使用簡(jiǎn)寫方式
• 字典的 key 必須是可哈希的

創(chuàng)建空字典

• 初始器方式
• 簡(jiǎn)寫方式

• 字面量方式

  
  
  75

字面量創(chuàng)建字典

• [key 1: value 1, key 2: value 2, key 3: value 3]

  
  
  76

count 和 isEmpty

• 可以使用 count 只讀屬性來找出 Dictionary 擁有多少元素
• 使用布爾量 isEmpty 屬性檢查字典是否為空

遍歷字典

• For-In 循環(huán)
• 可以通過訪問字典的 keys 和 values 屬性來取回可遍歷的字典的鍵或值的集合
• Swift 的 Dictionary 類型是無序的。要以特定的順序遍歷字典的鍵或值，使用鍵或值的 sorted() 方法

77

字典常用操作

添加或更新元素

• 使用下標(biāo)添加或更新元素
• 使用 updateValue(_:forKey:) 方法添加或更新元素，返回一個(gè)字典值類型的可選項(xiàng)值

移除元素

• 使用下標(biāo)腳本語法給一個(gè)鍵賦值 nil 來從字典當(dāng)中移除一個(gè)鍵值對(duì)
• 使用 removeValue(forKey:)來從字典里移除鍵值對(duì)。這個(gè)方法移除鍵值對(duì)如果他們存在的 話，并且返回移除的值，如果值不存在則返回 nil 。

合并兩個(gè)字典

• merge(_:uniquingKeysWith:)

78

firstIndex

• 雖然字典是無序的，但是每個(gè)kv對(duì)在擴(kuò)容之前的位置是穩(wěn)定的。如果你需要保持順序的kv對(duì) 可以使用 KeyValuePairs

  
  
  79

字典實(shí)現(xiàn)探秘

從下標(biāo)操作談起

80

Dictionary._Variant 的 setValue

81

_NativeDictionary 的 setValue

82

_NativeDictionary 的 _insert

83

_NativeDictionary 的 uncheckedInitialize

84

_NativeDictionary 的 findKey

85