1
$\begingroup$

Does there exist any data structure that efficiently (linearithmic-or-similar in-order traversal, sublinear time insertion/search/removal) implements an ordered set (i.e. a set that allows for enumerating the items in insertion order)?

If so, what data structure is it/how does it do this?

$\endgroup$
  • 1
    $\begingroup$ Doesn't a simple linked list meet your criteria (except for sublinear traversal, which doesn't make sense)? $\endgroup$ – svick Jul 15 '12 at 22:17
  • 1
    $\begingroup$ It's easy if you don't insist on linear-time traversal: use a set as normal, and associate some metadata with each entry to encode insertion order. Insert, remove, and search work just like for a set; when you want to iterate, just do a straight sort on the metadata first. Do you need linear traversal? $\endgroup$ – Patrick87 Jul 15 '12 at 22:41
  • 3
    $\begingroup$ What precisely does "search" mean in this context? Find the rank of a given item? Find the item with a given rank? Decide whether a given item is in the set at all? Or something else? $\endgroup$ – JeffE Jul 15 '12 at 22:48
  • 1
    $\begingroup$ Another nice thing about such a structure as I describe above is that it can support, with no additional overhead, sorting based on the elements' natural ordering. Also, you might be able to use an auxiliary DS - a BST would work nicely - to start sorting as you're inserting elements; you'd go from const-time add/remove to log time, and you'd double the storage, but that would support everything, including linear traversal. $\endgroup$ – Patrick87 Jul 15 '12 at 22:48
  • 1
    $\begingroup$ I just learned a new word: "linearithmic". $\endgroup$ – Raphael Jul 18 '12 at 9:58
4
$\begingroup$

Another pretty simple solution is a balanced binary search tree with threading (an overlaid linked list passing through all the nodes of the tree in order of their original insertion). Then insertion/search/removal are all O(log n), and iteration is O(n). You just update insert/remove to either append to the linked list or remove the node from it.

$\endgroup$
0
$\begingroup$

Okay, I guess this is just a case of me being silly... thanks to the people who commented above who made me realize this.

I can just use a hashtable, and keep a counter along with the item.

To traverse in order of insertion? Just dump it into an array and sort it with respect to the counter.
Traversal is O(n) anyway, so O(n log n) sorting won't really make a difference.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.