Re: Where is NSList?
Re: Where is NSList?
- Subject: Re: Where is NSList?
- From: Tim Conkling <email@hidden>
- Date: Wed, 28 Jul 2004 02:09:11 -0400
It's clear from the responses I received in this thread (and from my
original post that I have re-read) that I was terribly unclear in
describing what it is I'm looking for. Basically, all I was asking was
whether Apple had created a linked list object for Cocoa (hence the
title of my original post); I was surprised that I had not seen such a
class in the Cocoa documentation and was thinking I may have missed
something. I am quite capable of creating my own such class, but, being
lazy, I would of course prefer to use one that has already been written
and tested by somebody else.
I'm quite aware of how the STL works in regards to iterators and the
like. I seem to have greatly miscommunicated exactly what it is I'm
looking for. I've written several programs in the past where I had many
objects that I needed to have held in several containers
simultaneously. When any one of these objects was deleted, it also had
to be removed from all of its containers. If these objects knew nothing
of their position in the containers, a search would be necessary for
each of these deletions to take place. As an optimization, I had each
object retain an iterator for each container it was contained in, so
that these deletions could be performed more quickly. STL lists, sets,
and maps all guarantee that iterators are not invalidated upon
insertion and removal, which is key to the implementation of the
optimization described above. I'm now writing a Cocoa application, and
wanted to do something similar, hence my original question.
I thought that Cocoa might have similar functionality; as a Cocoa
newbie, I've been trying to do things the Cocoa way and to use Apple's
classes whenever possible. From the multitude of messages I've received
on the topic, it's now quite clear to me that Cocoa does not contain
the sort of solution to my one-object-in-many-containers problem that I
was looking for. This is perfectly okay; I'll solve it in another way
(or I'll use Objective-C++, as recommended).
Thanks for everyone's input,
Tim
On Jul 27, 2004, at 6:52 PM, Steve Checkoway wrote:
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.
_______________________________________________
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.