前言

有需要的同學(xué)可以訂閱專(zhuān)欄：Swift數(shù)據(jù)結(jié)構(gòu)和算法專(zhuān)題
代碼地址：Swift數(shù)據(jù)結(jié)構(gòu)和算法代碼

正文

在本章中，我們將關(guān)注標(biāo)準(zhǔn)庫(kù)開(kāi)箱即用的三個(gè)主要數(shù)據(jù)結(jié)構(gòu)：數(shù)組、字典和集合持搜。

數(shù)組

數(shù)組是一種通用的通用容器，用于存儲(chǔ)有序的元素集合劫樟，它在各種 Swift 程序中普遍使用。我們可以使用數(shù)組字面量創(chuàng)建數(shù)組织堂，數(shù)組字面量是由方括號(hào)括起來(lái)的以逗號(hào)分隔的值列表叠艳。例如：

let people = ["Brian", "Stanley", "Ringo"]

Swift 使用協(xié)議定義數(shù)組。這些協(xié)議中的每一個(gè)都在陣列上分層了更多功能易阳。例如附较，一個(gè)數(shù)組是一個(gè)序列，這意味著我們可以至少迭代一次潦俺。它也是一個(gè)集合拒课，這意味著它可以被多次非破壞性地遍歷，并且可以使用下標(biāo)運(yùn)算符進(jìn)行訪問(wèn)事示。數(shù)組也是一個(gè)RandomAccessCollection早像，它保證了效率很魂。

Swift Array 被稱為泛型集合扎酷，因?yàn)樗梢蕴幚砣魏晤?lèi)型遏匆。事實(shí)上，大部分 Swift 標(biāo)準(zhǔn)庫(kù)都是用通用代碼構(gòu)建的幅聘。與任何數(shù)據(jù)結(jié)構(gòu)一樣，我們應(yīng)該注意某些值得注意的特征帝蒿。首先 其中包括秩序的概念荐糜。數(shù)組中的元素是明確排序的葛超。以上述人員數(shù)組為例，“Brian”排在“Stanley”之前绣张。數(shù)組中的所有元素都有一個(gè)對(duì)應(yīng)的從零開(kāi)始的整數(shù)索引。例如侥涵，上面示例中的 people 數(shù)組具有三個(gè)索引，一個(gè)對(duì)應(yīng)于每個(gè)元素芜飘。我們可以通過(guò)編寫(xiě)以下代碼來(lái)檢索數(shù)組中元素的值：

people[0] // "Brian" 
people[1] // "Stanley" 
people[2] // "Ringo" 
復(fù)制代碼

順序由數(shù)組數(shù)據(jù)定義結(jié)構(gòu)，不應(yīng)被視為理所當(dāng)然嗦明。某些數(shù)據(jù)結(jié)構(gòu)，例如 Dictionary娶牌，具有較弱的順序概念。

隨機(jī)訪問(wèn)

如果數(shù)據(jù)結(jié)構(gòu)可以在恒定時(shí)間內(nèi)處理元素檢索裙戏，則隨機(jī)訪問(wèn)是一種特征。例如累榜，從 people 數(shù)組中獲取“Ringo”需要恒定的時(shí)間。同樣壹罚，這種表現(xiàn)不應(yīng)被視為理所當(dāng)然。其他數(shù)據(jù)結(jié)構(gòu)猖凛，如鏈表和樹(shù)，沒(méi)有固定時(shí)間訪問(wèn)辨泳。

數(shù)組性能

除了作為隨機(jī)訪問(wèn)集合之外玖院，作為開(kāi)發(fā)人員第岖，我們還對(duì)其他性能領(lǐng)域感興趣难菌，特別是當(dāng)數(shù)據(jù)結(jié)構(gòu)包含的數(shù)據(jù)量需要增長(zhǎng)時(shí)蔑滓，它的表現(xiàn)如何？對(duì)于數(shù)組键袱，這取決于兩個(gè)因素。

插入位置

第一個(gè)因素是我們選擇在數(shù)組中插入新元素的因素蹄咖。將元素添加到數(shù)組的最有效方案是將其附加到數(shù)組的末尾：

people.append("Charles") 
print(people) // prints ["Brian", "Stanley", "Ringo", "Charles"]
復(fù)制代碼

使用 append 方法插入 "Charles" 會(huì)將字符串放在數(shù)組的末尾。這是一個(gè)恒定時(shí)間操作比藻，這意味著無(wú)論數(shù)組有多大，執(zhí)行此操作所需的時(shí)間都保持不變银亲。但是，有時(shí)我們可能需要在特定位置插入元素务蝠，例如在數(shù)組的最中間。

為了幫助說(shuō)明為什么會(huì)出現(xiàn)這種情況馏段，請(qǐng)考慮以下類(lèi)比。你正在排隊(duì)等劇院院喜。新來(lái)的人加入了陣容。將人員添加到陣容中最容易的地方是什么喷舀？最后，當(dāng)然硫麻！

如果新人試圖將自己插入隊(duì)伍的中間，他將不得不說(shuō)服一半的陣容重新洗牌以騰出空間拿愧。

如果他非常粗魯，他會(huì)試圖把自己插在隊(duì)伍的最前面。這是最壞的情況券敌，因?yàn)殛嚾葜械拿總€(gè)人都需要重新洗牌，為前面的新人騰出空間陪白！

這正是數(shù)組的工作原理膳灶。從數(shù)組末尾以外的任何地方插入新元素將強(qiáng)制元素向后移動(dòng)以為新元素騰出空間：

people.insert("Andy", at: 0) 
// ["Andy", "Brian", " Stanley", "Ringo", "Charles"] 
復(fù)制代碼

準(zhǔn)確地說(shuō)，每個(gè)元素必須向后移動(dòng)一個(gè)索引轧钓，這需要 n 步。如果數(shù)組中的元素?cái)?shù)量加倍毕箍，則此插入操作所需的時(shí)間也將加倍。

如果在集合前面插入元素是程序的常見(jiàn)操作而柑，我們可能需要考慮使用不同的數(shù)據(jù)結(jié)構(gòu)來(lái)保存數(shù)據(jù)。

決定插入速度的第二個(gè)因素是陣列的容量媒咳。在底層，Swift 數(shù)組為其元素分配了預(yù)定數(shù)量的空間涩澡。如果我們嘗試將新元素添加到已達(dá)到最大容量的數(shù)組中，則該數(shù)組必須自行重組妙同，以便為更多元素騰出更多空間。這是通過(guò)復(fù)制所有當(dāng)前元素來(lái)完成的 在內(nèi)存中一個(gè)新的更大的容器中的數(shù)組粥帚。然而，這是有代價(jià)的芒涡；必須訪問(wèn)和復(fù)制數(shù)組的每個(gè)元素。這意味著如果進(jìn)行了復(fù)制拖陆，任何插入，即使是在最后依啰，也可能需要 n 步才能完成。但是，標(biāo)準(zhǔn)庫(kù)采用了一種策略叹誉，可以最大限度地減少這種復(fù)制需要發(fā)生的時(shí)間。每次它用完存儲(chǔ)空間并需要復(fù)制時(shí)长豁，它的容量就會(huì)增加一倍。

字典

字典是另一個(gè)保存鍵值對(duì)的通用集合匠襟。例如，這是一個(gè)包含用戶名和分?jǐn)?shù)的字典：

var score: [String: Int] = ["Eric": 9, "Mark": 12, "Wayne": 1]
復(fù)制代碼

字典沒(méi)有任何順序保證酸舍，也不能在特定索引處插入。他們還對(duì) Key 類(lèi)型提出了要求啃勉，即它是 Hashable。幸運(yùn)的是淮阐，幾乎所有的標(biāo)準(zhǔn)類(lèi)型都已經(jīng)是 Hashable 并且在 Swift 的最新版本中，采用 Hashable 協(xié)議現(xiàn)在是微不足道的泣特。我們可以使用以下語(yǔ)法向字典中添加新條目：

scores["Andrew"] = 0
復(fù)制代碼

這將在字典中創(chuàng)建一個(gè)新的鍵值對(duì)：

["Eric": 9, "Mark": 12, "Andrew": 0, "Wayne": 1] 
復(fù)制代碼

"Andrew" 鍵被插入到字典的某個(gè)位置。字典是無(wú)序的群扶，所以你不能保證新條目會(huì)放在哪里。

正如 Collection 協(xié)議所提供的竞阐，可以多次遍歷字典的鍵值。這個(gè)順序雖然沒(méi)有定義骆莹，但每次遍歷時(shí)都是相同的，直到集合發(fā)生變化（突變）幕垦。

缺乏明確的排序劣勢(shì)帶來(lái)了一些可取之處。

與數(shù)組不同先改，字典不需要擔(dān)心元素的移動(dòng)。插入字典總是需要一定的時(shí)間仇奶。查找操作也需要一定的時(shí)間，這比在數(shù)組中查找需要從數(shù)組開(kāi)頭到插入點(diǎn)的特定元素要快得多。

集合

集合是一個(gè)包含唯一值的容器别惦。想象它是一個(gè)包 允許我們將項(xiàng)目插入其中，但拒絕已插入的項(xiàng)目：

var bag: Set<String> = ["Candy", "Juice", "Gummy"] 
bag.insert("Candy") 
print(bag) // prints ["Candy", "Juice", "Gummy"] 
復(fù)制代碼

由于集合強(qiáng)制唯一性掸掸，它們適用于各種有趣的應(yīng)用，例如在值集合中查找重復(fù)元素：

let values: [String] = [ ...] 
var bag: Set<String> = [] 
for value in values { 
  if bag.contains(value) { 
    // bag 已經(jīng)有了它扰付，因此它是重復(fù)的 
  } 
  bag.insert(value) 
} 
復(fù)制代碼

使用集合的次數(shù)幾乎不會(huì)與與數(shù)組和字典一樣多，但它仍然很常見(jiàn)悯周，可以作為重要的數(shù)據(jù)結(jié)構(gòu)保存在我們的工具帶中。不過(guò)，有一個(gè)警告屠橄。與字典類(lèi)似，集合中的值沒(méi)有順序的概念锐墙。當(dāng)我們使用集合來(lái)聚合數(shù)據(jù)時(shí)，請(qǐng)記住這一點(diǎn)溪北。

Swift Collections 包

Swift 標(biāo)準(zhǔn)庫(kù)只實(shí)現(xiàn)了三個(gè)最重要的數(shù)據(jù)結(jié)構(gòu)：Array、Set 和 Dictionary之拨。對(duì)于其他數(shù)據(jù)結(jié)構(gòu)，我們可以查看 Swift Collections 包蚀乔。這個(gè)包允許社區(qū)在它們成為官方標(biāo)準(zhǔn)庫(kù)的一部分之前開(kāi)發(fā)和測(cè)試新的集合類(lèi)型。

在下一節(jié)中吉挣，我們將更深入地了解此包中的一個(gè)數(shù)據(jù)結(jié)構(gòu)。

Deque

之前睬魂，我們了解到在 Array 的前面插入元素會(huì)導(dǎo)致所有元素的混洗。乍一看氯哮，Deque（讀作“deck”）數(shù)據(jù)結(jié)構(gòu)似乎與 Array 具有相同的用途。我們可以將其用作按順序保存值的通用容器。就像數(shù)組一樣垫卤，我們可以調(diào)用 append 將元素添加到 Deque，或調(diào)用 remote(at:) 以刪除某個(gè)索引處的特定元素穴肘。事實(shí)上，接口幾乎是相同的评抚，因?yàn)?Array 和 Deque 都實(shí)現(xiàn)了相同的收集協(xié)議。 那么為什么要在數(shù)組上使用雙端隊(duì)列呢慨代？除非我們考慮時(shí)間復(fù)雜度，否則很難看到權(quán)衡取舍侍匙。 Deque 是一個(gè)雙端隊(duì)列。因此想暗，Deque 針對(duì)集合前后的修改進(jìn)行了優(yōu)化。與 Array 不同说莫，從 Deque 的前面插入或刪除元素是一種快速的 O(1) 操作。太好了 - 那么有什么缺點(diǎn)呢储狭？在編程中，一切都是關(guān)于權(quán)衡的辽狈。對(duì)于 Deque，它是關(guān)于改進(jìn)前端的修改稻艰，以犧牲其他所有方面的性能略有下降。作為程序員尊勿，我們的工作是權(quán)衡選項(xiàng)并選擇最適合工作的工具。如果我們的應(yīng)用程序需要頻繁修改集合的前面元扔，則 Deque 的性能將比 Array 好得多。這可以轉(zhuǎn)化為更好的用戶體驗(yàn)——一種可以在快速和緩慢的應(yīng)用程序之間產(chǎn)生差異的體驗(yàn)澎语。 Swift Collections 包包含額外的數(shù)據(jù)結(jié)構(gòu)验懊，例如 OrderedDictionary 和 OrderedSet。正如前綴所暗示的义图， 這些是 Dictionary和 Set 的變體，它們保留了元素的順序碱工。與 Deque 一樣，這些數(shù)據(jù)結(jié)構(gòu)也有一些性能折衷怕篷。我們可以在 swift.org/blog/swift-… 了解更多關(guān)于它們的信息。

關(guān)鍵點(diǎn)

? 每個(gè)數(shù)據(jù)結(jié)構(gòu)都有優(yōu)點(diǎn)和缺點(diǎn)酗昼。了解它們是編寫(xiě)高性能軟件的關(guān)鍵廊谓。

? 用于Array 的insert(at:) 等函數(shù)具有性能特征麻削，在隨意使用時(shí)會(huì)削弱性能蒸痹。如果我們發(fā)現(xiàn)自己需要經(jīng)常在數(shù)組開(kāi)頭附近使用帶有索引的 insert(at:)碟婆，我們可能需要考慮使用不同的數(shù)據(jù)結(jié)構(gòu)，例如鏈表竖共。

? 字典放棄了保持其元素順序的能力俺祠，以實(shí)現(xiàn)快速插入和搜索公给。

? Set 保證值集合的唯一性蜘渣。Set針對(duì)速度進(jìn)行了優(yōu)化，放棄了保留元素順序的能力蔫缸。

? Swift Collections 包包含在某些場(chǎng)景中表現(xiàn)更好的專(zhuān)用數(shù)據(jù)結(jié)構(gòu)。