A set that maintains insert order and allows accessing elements by its index

Question

I basically need a data structure that works just like a Set, but that not only maintains insert order as let's me get them later by a get(index) method.

What is the data structure best suited to achieve this? I wouldn't have a problem in having to implement one, if needed. In the worse case I could just use both an ArrayList and a HashSet, but I'm wondering whether there is a specialized data structure up to the task.

Performance is paramount (otherwise I could just do a O(n) search over a regular list!) and I'm not that worried about spatial complexity.

A *set* doesn't have an *order*. You may or may not be aware of this, but I think it's worth emphasizing. — Damien_The_Unbeliever, Feb 24 '12 at 18:47
How about two data structures: a dictionary to map indexes to items, and a hashmap for the items. — harold, Feb 24 '12 at 18:47
I'll probably end up using it in Java, but as I said, if needed I'm ok with implementing it by hand. — devoured elysium, Feb 24 '12 at 18:48
[MSDN SortedSet](http://msdn.microsoft.com/en-us/library/dd412070.aspx) — Austin Salonen, Feb 24 '12 at 18:48
@harold: that would one solution, as well as having both a list and a set, yes. — devoured elysium, Feb 24 '12 at 18:49
@devouredelysium a List and a Set wouldn't have an efficient `remove`, do you need that? — Daniel Lubarov, Feb 24 '12 at 18:55
If I get elements by index, I'd have an efficient remove(). It'd be an amortized O(1). I could get the element off the list in ~O(1) and with the element I could now delete it from the set. Or am I missing something? — devoured elysium, Feb 24 '12 at 19:00
Guava has [considered this](http://code.google.com/p/guava-libraries/issues/detail?id=13), but we couldn't find anyone who really needed it. Would you mind poking there with some more details on your use case? — Louis Wasserman, Feb 24 '12 at 19:02
Oh, it's for a Traveling Salesman Problem brute-force implementation, so it's not really a standard scenario, I admit. — devoured elysium, Feb 24 '12 at 19:05
Related: http://stackoverflow.com/questions/769731/why-doesnt-java-util-set-have-getint-index — Michael Myers, Feb 24 '12 at 23:02

score 4 · Answer 1 · answered Feb 24 '12 at 18:46

4

How about OrderedDictionary ?

Represents a collection of key/value pairs that are accessible by the key or index.

http://msdn.microsoft.com/en-us/library/system.collections.specialized.ordereddictionary.aspx

answered Feb 24 '12 at 18:46

asawyer

17,642
8
59
87

Ahhh. I wasn't aware of that. Is that the general-purpose name of the algorithm? – devoured elysium Feb 24 '12 at 18:47
@devouredelysium The particular one I linked is a c# collection type. – asawyer Feb 24 '12 at 18:49
I know. But I'm as worried about finding an existent implementation as to know the name of the algorithm that is used behind (this is for an Algorithms and Data Structures graduate course). – devoured elysium Feb 24 '12 at 18:51
@devouredelysium I'm not really sure then. Could try a few google searches around and see, and/or poke around it's guts with reflector and see how it's implemented. – asawyer Feb 24 '12 at 18:53

score 1 · Answer 2 · answered Feb 24 '12 at 18:54

1

Are you open to using existing code? Apache Commons has a ListOrderedSet class that seems to fit all your requirements. Worst come to worse you could study the source code and implement in C#.

answered Feb 24 '12 at 18:54

Perception

79,279
19
185
195

nongeneric!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! But thanks, seems to be just what I'm looking for. I'll take a look at its source, too. – devoured elysium Feb 24 '12 at 18:58

Daniel Lubarov · Accepted Answer · 2012-02-25T00:53:07.967

1

Something like this? Edit: As Jiddo noted, this structure can't remove elements efficiently. ArrayList + Set is simpler if an efficient remove is not required, so this structure isn't actually good for much.

import java.util.*;

public class ArraySet<T> {
    private final Map<Integer, T> indexToElem;
    private final Map<T, Integer> elemToIndex;

    public ArraySet() {
        indexToElem = new HashMap<Integer, T>();
        elemToIndex = new HashMap<T, Integer>();
    }

    public T get(int index) {
        if (index < 0 || index >= size())
            throw new IndexOutOfBoundsException();
        return indexToElem.get(index);
    }

    public void add(T elem) {
        if (!contains(elem)) {
            int index = indexToElem.size();
            indexToElem.put(index, elem);
            elemToIndex.put(elem, index);
        }
    }

    // Doesn't work; see comment.
    /*public void remove(T elem) {
        int index = elemToIndex.get(elem);
        indexToElem.remove(index);
        elemToIndex.remove(elem);
    }*/

    public boolean contains(T elem) {
        return elemToIndex.containsKey(elem);
    }

    public int size() {
        return indexToElem.size();
    }
}

edited Feb 25 '12 at 00:53

answered Feb 24 '12 at 19:01

Daniel Lubarov

7,796
1
37
56

Nice. But is that better than a set+arraylist mix, for instance? – devoured elysium Feb 24 '12 at 19:04
1

I don't understand how you would efficiently remove from the ArrayList, wouldn't shifting the other elements take linear expected time? – Daniel Lubarov Feb 24 '12 at 19:08
Argh, forgot about that small detail. – devoured elysium Feb 24 '12 at 19:13
1

Note that using the suggested implementation the remove operation on any element except the last would effectively break the set. It would not be possible to retrieve the last element, the index of the next added element will collide with the last element and the accessible indices would no longer be coherent. If remove is not required then it will work fine tho. – Jiddo Feb 24 '12 at 19:55
@Jiddo good point, I overlooked that. This answer should probably be unaccepted. A balanced tree, where each node stores its descendant count, seems like the better approach. That should be able to do everything in logarithmic time. – Daniel Lubarov Feb 25 '12 at 00:48

A set that maintains insert order and allows accessing elements by its index

3 Answers3