2012-05-31 64 views
4

最近我發現,沒有內置可可隊列(觸摸,在這種情況下)。爲什麼不?隊列是計算機編程中最基本的數據結構之一。爲什麼Cocoa中沒有隊列?

我見過一些人建議使用NSMutableArray,但這對於彈出/退出非常低效,因爲它需要移除索引0處的對象。這會將所有元素向下移動(朝向現在爲空的條目),因此每次移除操作需要O(n)個時間。我是否錯過了某些東西,或者有沒有理由說隊列沒有添加到可可?

+7

「不要再猜蘋果,因爲蘋果已經第二次猜到了你,當然,這是一個好方法。」 http://ridiculousfish.com/blog/posts/array.html – vikingosegundo

+0

@vikingosegundo偉大的閱讀 - 感謝分享。 – Till

+0

@Till看到我的回覆,我張貼了一些信息,通過查看CFArray和CFStorage的源文件找到。 – vikingosegundo

回答

12

我見過一些人建議使用NSMutableArray,但這是彈出/出隊極其低效的,因爲它需要在索引0去除對象將轉移所有元素向下(朝現空條目),因此每個刪除操作需要O(n)個時間。

這是不正確的。 NSMutableArray可非常有效地處理頭部插入,並可用於許多不同的數據結構,包括隊列和堆棧。

4

AFAIK的NSMutableArray中使用循環緩衝區內,所以我認爲這是相當正常使用的隊列。

8

蘋果發佈的CFTypes作爲開源 - 和他們的核心數據類型的面向對象的集合作爲的NSArray,NSDictionary的,......(「免費電話橋接」)

因此,如果我們看看CFArray.c我們只需查看包含#include "CFStorage.h"即可看到。這必須是真實存儲數據的類型。

ok了,在看看CFStorage.h,我們發現這在它的評論

CFStorage使用平衡樹來存儲的值,並且是最 適合那種潛在的大量的值 情況(更一百個字節的價值)將被保存,都會有很多 編輯(插入和刪除)的。

獲取一個項目是O(log n)的,雖然高速緩存的最後結果往往降低此 到一個恆定的時間。

ERGO
命名爲「NS(可變)陣列」沒有介紹,它是如何實現的,但它是如何工作在更高的層次。而且實現要複雜得多,而不僅僅是一個列表,數組意味着。


我們不知道,如果進入封閉源代碼的時候,所以不是所有的事情可能會通過查看CFTypes來源可以解釋蘋果正在改變CFTypes。

一些數字和圖表:http://ridiculousfish.com/blog/posts/array.html

+1

很好解釋。當然,沒有理由說NeXT/Apple(或者Nosrettap!)不能在底層結構中添加另一個高級接口「NS [Mutable] Queue」。 –

0

不難寫圍繞NSMutableArray的小包裝和使用,作爲一個隊列。蘋果建議這樣做。我有我寫這裏的實施要做到這一點

至於爲什麼蘋果決定不這樣做。誰知道,這是基金會框架工程師的問題。

相關問題