‘Cause sometimes, you really need a deque
The default collections in Foundation are great and just what you need 99% of the time. However, none of the collections actually guarantee the underlying structure of the class you’re using. Anyone with a computer science background knows that an array should always yield constant time ( O(1) ) access to an object given the index, however the CFArray documentation clearly states:
The access time for a value in the array is guaranteed to be at worst O(log N) for any implementation, current and future, but will often be O(1)
Since its based on CFArray, we can assume this is true for NSArray as well.
Again, 99% of the time this isn’t a problem in the average iOS app, however for a project I’m working on now, I needed a data structure that provided ordering but I knew I would be doing a lot of adding and removing of objects on either end. A deque is what I needed, but Cocoa doesn’t supply me any deques. Simply using an NSArray would incur a performance hit when prepending onto the front.
Enter CHDataStructures, a suite of classes providing for more exact implementations of data structures for when that the structure really matters:
- Trees: AVL, Anderson, RedBlack
- Linked lists – singly linked, doubly linked
- Stacks, Queues, Deques
- Sorted sets and sorted dictionaries
- Circular Buffers
These certainly aren’t for every day, but they’re good to have around when you need them. The project homepage can be found here, though none of the SVN links worked for me. Fortunately google found a bitbucket repo containing the code.
Also, here’s the RidiculousFish post containing more information than you ever wanted to know about the Foundation collection classes.