Harro,
Does anybody know of a data structure that has:
* fast lookup and insertion of elements (ideally amortised O(1),
but O(log n) is OK too),
* enables you to iterate over the elements in the data structure in
the same order that you inserted them in, and
* doesn't let you insert duplicate elements?
Two other ways to think about these requirements are that I want (1)
a set that also keeps ordering of insertion order, or (2) an array/
vector that doesn't let you insert duplicates, and has faster element
lookup than O(n).
The use-case for this is where you conceptually want a set, but you
need to keep the ordering for a user interface. e.g. Say you're
writing some blogging software that enables the user to have
Technorati-like tags for each blog entry... you don't want the same
tag twice, but you also want to keep the ordering of the tags for
display in the user interface.
I could write one, but I thought that surely someone else out there
has, and can probably do a better job than me. I'm sure there's also
a more technical term for this than "ordered set". Pointers to a C/C+
+ library that implements this would be even better -- preferably C+
+, but C's fine.
(I did look at boost::multiindex, but couldn't quite munge it to do
what I wanted.)
Cheers :)
--
% Andre Pang : trust.in.love.to.save <http://www.algorithm.com.au/>
_______________________________________________
coders mailing list
coders@slug.org.au
http://lists.slug.org.au/listinfo/coders
