The SETT Programming Contest: The fastest set<T> implementation

[SETT Programming Contest]

The SETT Programming Contest: The fastest set<Timplementa tion

Write the fastest set<Timplementa tion using only standard C++/C.
Ideally it should have the same interface like std::set.
At least the following methods must be implemented:
insert(), find(), begin(), end(), erase(), size(), operator<(),
and at least the forward iterator.

Here, speed and correctness are the 2 most important factors.
Functionally it should behave similar to std::set,
have practically no limitation on the number of items,
and be significantly faster, either always or under specified
conditions (for example for random items etc.).

The class should be placed in an own namespace.
Supply also a benchmark routine which compares your
implementation with that of std::set, and briefly document
and comment these results.

Hint: Since items in a set are always in an ordered sequence
(as determined by operator<()) you need to use some tree
routines (AVL, red-black, splay, etc.) or use your own tree
method in the heart of your implementation.

See also this paper:
Ben Pfaff, "Performanc e Analysis of BST in System Software", Stanford University
http://www.stanford.edu/~blp/papers/libavl.pdf

Publish your finished project somewhere on the Web
(for example at your own homepage or at http://sourceforge.net/ )
and announce it in comp.lang.c++ .

There is no deadline on this contest. The fastest method
will be the winner of the SETT Programming Contest,
until someone comes up with a faster method.

Good Luck!

[Anders Dalvander]

On Jun 3, 3:55 pm, "SETT Programming Contest"
<[e-mail] ramming.contest .org.invalidwro te:

Write the fastest set<Timplementa tion using only standard C++/C.
Ideally it should have the same interface like std::set.
At least the following methods must be implemented:
insert(), find(), begin(), end(), erase(), size(), operator<(),
and at least the forward iterator.

Is that you Razii? What are you trying to prove?

Regards,
Anders

[Stephen Howe]

I don't see any specifications on iterator invalidation in the

original post.

I think the intention is it follows the same as std::set.
And that means an iterator to a element within the container is always valid
for as long as the element exists.
So any rebalancing does not affect the iterator.
That iterator validity is true for all nodal containers in C++ : std::list,
std::map etc.

Stephen Howe

[Chris Thomasson]

"Anders Dalvander" <go****@dalvand er.comwrote in message
news:84******** *************** ***********@c58 g2000hsc.google groups.com...

On Jun 3, 3:55 pm, "SETT Programming Contest"
<[e-mail] ramming.contest .org.invalidwro te:

>Write the fastest set<Timplementa tion using only standard C++/C.
Ideally it should have the same interface like std::set.
At least the following methods must be implemented:
insert(), find(), begin(), end(), erase(), size(), operator<(),
and at least the forward iterator.

Is that you Razii?

:^)

What are you trying to prove?