Re: red black trees
Re: red black trees
- Subject: Re: red black trees
- From: Óscar Morales Vivó <email@hidden>
- Date: Thu, 19 Feb 2004 12:34:20 +0100
There is an use for C++, and that seems to be it ;oP
And having implemented a few computational geometry algorithms in C++
that then got their results displayed via Cocoa I guess I earned my
right to have an opinion :D
More seriously, most STL implementations of std::set and std::map (and
variants thereof) are based on red-black trees, so they should be safe
to use while keeping the desired algorithm complexity.
If performance is an issue, the most sensible thing to do would be to
encapsulate the algorithm in pure C++ and do the black box calling from
your Cocoa program. It also ends you up with a portable library with no
additional effort, which down the road ends up being a useful thing
more often than not.
Hope that helps:
Sscar Morales Vivs.
On 19 Feb 2004, at 11:29, Marco Scheurer wrote:
On Feb 19, 2004, at 8:41 AM, Allan Odgaard wrote:
On 19. Feb 2004, at 5:22, Brian Reardon wrote:
So what is driving your desire to have a tree vs an ordered array?
I am trying to implement Preparata and Shamos's convex hull point
set search algorithm (Computational Geometry, Springer-Verlag, 1985,
section 4.1.3, pages 157-166)
Arg... implementing algorithms in ObjC is certainly not something I
would recommend, not really for the performance overhead, but mainly
for the syntactic overhead -- i.e. lack of operator overloading,
implicit type conversions, compact type declarations, stack allocated
temporaries etc. etc.
Argh! I would have said exactly the opposite, ie one always want to
avoid the syntactic mess of C++. The EDCommon framework from Mulle
Kybernetik has a red black tree implementation in a class named
EDSortedArray.
http://www.mulle-kybernetik.com/software/EDFrameworks/Documentation/
EDCommon/Classes/EDSortedArray.html
I haven't used it, so I cannot comment on this class in particular,
but Mulle Kybernetik's stuff is usually very well done.
Marco Scheurer
Sen:te, Lausanne, Switzerland http://www.sente.ch
_______________________________________________
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.