Why is there no queue in Cocoa?

Question

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

I saw some people suggest using NSMutableArray , but this is extremely inefficient for pops / dequeues, because it requires deleting an object with index 0. This will shift all the elements down (to the now empty record), so the time is O ( n) for each delete operation. Am I missing something or was there simply no reason for queues not being added to Cocoa?

Answer 1

I saw some people suggest using NSMutableArray , but this is extremely inefficient for pops / dequeues, because it requires deleting an object with index 0. This will shift all the elements down (to the now empty record), so the time is O ( n) for each delete operation.

This is not true. NSMutableArray handles insertion into the head very efficiently and can be used for several different data structures, including queues and stacks.

Answer 2

Apple releases CFTypes as an OpenSource - and they are the main data types for object-oriented collections like NSArray, NSDictionary, ... ("Infinite Bridging")

So, if we look at CFArray.c , we just see by looking at the include #include "CFStorage.h" . This should be the type that hurts the data for real.

ok, looking at CFStorage.h , we find it in its comment

CFStorage uses a balanced tree to store values ​​and is suitable for situations where a potentially large number of values ​​(more than a hundred bytes) will be saved and there will be a lot of editing (insert and delete).

Getting the O (log n) element, although caching the last result often reduces this by a constant time.

ergo
The name "NS (Mutable) Array" does not describe how it is implemented, but how it works at a higher level. And the implementation is much more complicated than just a list that would imply an array.

note
We do not know if an apple changes CFTypes when entering a closed source, so not everything can be explained by looking at the sources of CFTypes.

some numbers and charts: http://ridiculousfish.com/blog/posts/array.html

Answer 3

AFAIK NSMutableArray uses a circular buffer inside, so I find it quite normal to use for a queue.

Answer 4

It's easy to write a small wrapper around NSMutableArray and use it as a queue. Apple suggests doing this. I have an implementation that I wrote here to do this

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

Why did Apple decide not to do this. Who knows, this is a question for Foundation Framework engineers.