Re: Where is NSList?
Re: Where is NSList?
- Subject: Re: Where is NSList?
- From: Nicko van Someren <email@hidden>
- Date: Wed, 28 Jul 2004 14:45:00 +0100
On 28 Jul 2004, at 13:45, Tim Conkling wrote:
Pandaa put it well. It's not about the semantics. It's about the
implementation. Neither NSArray nor NSMutableDictionary provide the
time complexities that I am looking for, though they _do_ provide all
the _functionality_ I'm looking for.
...
I was simply surprised to find a list-like object lacking from
CoreFoundation and Cocoa
I suspect that there are a couple of reasons why there is no
linked-list class in Cocoa.
Firstly, in my 25 years of programming I have found that I far more
frequently care about the cost of looking up an object in a collection
than I do about the cost of removal of that object and although the
cost of insertion is occasionally an issue the majority of the time the
insertions I want to do are at the end of the connection, which makes
it very cheap for arrays too. I would hazard that for most uses that
people have most of the time the arrays, sets and dictionaries have
better performance.
The second reason is more subtle and has to do with the difference in
the way people do things in Objective C verse C++. In C++ you have
templates. If you want to make a handy package of code to allow other
people to build liked lists of their own objects then you can write
this as a template and then the end user's objects can acquire forward
and backward pointers and methods for list manipulation. If I already
have some class of Widget I can make a list of Widgets using a list
template and my existing Widget class. In Objective-C there is no
strait forward way to build generic code to extend other classes if you
need to extend the data as well as the messages (categories don't allow
you to add instance variables). Building a doubly-linked list requires
the object to gain forward and backward pointers and the only way to do
this in Objective-C is to subclass the things you want to list. The
problem is that the type system in Objective C is much more dynamic
than in C++ and people are therefore far more inclined to write code
that neither knows nor cares about the type of object that gets passed
in. An initial reaction might be to build a linked list of some sort
of node class and have each object in the list hang off a pointer in
the node, but this does not really do what you need since it's hard to
work out which node refers to a particular object. So, all in all
building code in Objective C to make generic lists of all subclasses of
NSObject is a bit of a pain.
As it happens, since the advent of Key-Value coding it is now actually
much easier to write generic code to handle linked lists of objects
just as long as you are willing to have a list that only hold objects
that you've created yourself. As long as you can arrange for all the
objects that you'll ever add into the linked list to have a couple of
extra instance variables with pre-defined names you can implement the
operations on the list items as a category added to NSObject and use
-valueForKey: and -setValue:forKey: to access the variables (you can't
access them directly since they are not in instances of NSObject).
Cheers,
Nicko
_______________________________________________
cocoa-dev mailing list | email@hidden
Help/Unsubscribe/Archives:
http://www.lists.apple.com/mailman/listinfo/cocoa-dev
Do not post admin requests to the list. They will be ignored.