Набор, который поддерживает порядок вставки и позволяет получить доступ к элементам по их индексу - PullRequest
Новая
       1

Набор, который поддерживает порядок вставки и позволяет получить доступ к элементам по их индексу

4 голосов
/ 24 февраля 2012

Мне, в основном, нужна структура данных, которая работает точно так же, как Set, но которая не только поддерживает порядок вставки, так как я получу их позже методом get(index).

Какая структура данных лучше всего подходит для этого?У меня не будет проблем с необходимостью его реализации, если это необходимо.В худшем случае я мог бы просто использовать ArrayList и HashSet, но мне интересно, есть ли специальная структура данных для этой задачи.

Производительность имеет первостепенное значение (в противном случае я мог бы просто сделать O(n) поиск по обычному списку!) и я не так беспокоюсь о пространственной сложности.

Ответы [ 3 ]

4 голосов
/ 24 февраля 2012

Как насчет OrderedDictionary?

Представляет коллекцию пар ключ / значение, которые доступны ключ или индекс.

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

1 голос
/ 24 февраля 2012

Как то так? Редактировать : Как отметил Джиддо, эта структура не может эффективно удалять элементы. ArrayList + Set проще, если эффективное удаление не требуется, поэтому эта структура на самом деле не годится для многих. 

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();
    }
}
1 голос
/ 24 февраля 2012

Вы открыты для использования существующего кода?В Apache Commons есть класс ListOrderedSet , который соответствует всем вашим требованиям.Хуже того, вы можете изучить исходный код и реализовать его на C #.

...