Re: Where is NSList?
Re: Where is NSList?
- Subject: Re: Where is NSList?
- From: Steve Checkoway <email@hidden>
- Date: Tue, 27 Jul 2004 15:52:43 -0700
On Jul 27, 2004, at 3:35 PM, Tim Conkling wrote:
I'm looking for a container that returns some information that
uniquely identifies each object added to it. This information is
called an iterator in the STL, but it's not used exclusively for
iterating over a container of objects, and I'm not actually looking to
iterate over a list of objects here. These iterators allow for
bidirectional reference between the list and the objects in the list
-- i.e., the list knows which objects it contains; and each object, if
it chooses to retain the iterator returned to it by the list it is
added to, knows exactly where it is contained in the list.
When you add something to an stl list (via insert, push_back, etc.) the
object knows nothing of it's position in the list or that it is even in
a list. Also, nothing is returned by those methods. You can explicitly
get an iterator (using your favorite methods provided by list) but
there is no sense of retaining these.
This is very useful, because it allows for operations like deletion
(which take linear time in a container like an NSArray) to be done in
constant time (in a list container), if you have retained the iterator
for the object to be deleted. Importantly, these iterators remain
valid when the container is modified.
It sounds like you simply want a doubly linked list. I'm quite sure
that someone has written one in Cocoa or you could very simply write
your own. If you really need/want the functionality of stl's list, then
you might as well just use objective-c++. Of course, unless most of
your work involves deleting and inserting elements into the middle of
the list, you'd be better off using an array as repeated heap
allocation for each element is fairly slow even if it is constant time.
An array is good for quick access via index, but object lookup is
slow. If I have an object that I know is contained in an NSArray, and
I want to delete it from that array, there is no quick method of doing
so -- the operation is necessarily performed in linear time, AFAIK.
Object lookup in a list is just as slow (actually slower since you
can't just increment a pointer by the size of the object) since you
still have to scan the whole list. I assume that your data isn't sorted
since then a binary search would be faster on the array. As for
deletion, the entire list must still be scanned if you don't know the
location of the object. If you store a pointer (or iterator) for each
object, there's no reason for the data structure in the first place.
Again, I'm new to Cocoa, so I may be missing something, but I have
already looked at the documentation for NSArray and NSEnumerator, and
they don't seem to provide the functionality I'm looking for. But I
certainly apologize if I'm missing something obvious.
Again, if you simply must have a linked list, write your own or use one
that I'm positive that someone else has written. Or, just use
objective-c++.
- Steve
_______________________________________________
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.