4

I recently found out that there is no queue built into Cocoa (Touch, in this case). Why not? A queue is one of the most fundamental data structures in computer programming.

I've seen some people suggesting the use of NSMutableArray, but this is extremely inefficient for pops/dequeues, because it requires removing the object at index 0. That will shift all of the elements down (towards the now empty entry), thus taking O(n) time for each remove operation. Am I missing something or was there just no reason that queues were not added to Cocoa?

4

4 回答 4

12

我见过一些人建议使用NSMutableArray，但这对于弹出/出队来说效率极低，因为它需要删除索引 0 处的对象。这会将所有元素向下移动（朝向现在为空的条目），从而占用 O (n) 每次移除操作的时间。

这是不正确的。NSMutableArray非常有效地处理头部插入，并且可以用于许多不同的数据结构，包括队列和堆栈。

于 2012-05-31T13:13:51.227 回答
8

Apple 将 CFTypes 作为 OpenSource 发布——它们是面向对象集合的核心数据类型，如 NSArray、NSDictionary、……（“免费桥接”）

因此，如果我们查看CFArray.c，我们只需查看 include 即可#include "CFStorage.h"。这必须是真正让数据感到痛苦的类型。

好的，看看CFStorage.h，我们在它的评论中找到了这个

CFStorage 使用平衡树来存储值，并且最适用于可能存储大量值（超过 100 字节的值）并进行大量编辑（插入和删除）的情况。

获取一个项目是 O(log n)，尽管缓存最后一个结果通常会将其减少到一个恒定的时间。

ergo
名称“NS(Mutable)Array”并没有描述它是如何实现的，而是它在更高级别上是如何工作的。并且实现比数组所暗示的列表要复杂得多。

注意
我们不知道，如果苹果在进入封闭源代码时改变了 CFTypes，所以并不是所有的事情都可以通过查看 CFTypes 源代码来解释。

一些数字和图表：http ://ridiculousfish.com/blog/posts/array.html

于 2012-05-31T14:06:15.590 回答
4

AFAIK NSMutableArray 在内部使用循环缓冲区，所以我认为它可以用于队列。

于 2012-05-31T13:14:29.103 回答
0

围绕 NSMutableArray 编写一个小包装器并将其用作队列并不难。苹果建议这样做。我有一个我在这里写的实现来做到这一点

https://github.com/Machx/Zangetsu/blob/master/Source/CWQueue.m

至于为什么苹果决定不这样做。谁知道呢，这是 Foundation Framework 工程师的问题。

于 2012-05-31T16:54:57.930 回答