Ведение отсортированного списка элементов, отсортированных по атрибуту, внешнему по отношению к этому элементу

Question

У меня есть класс "manager", поддерживающий список объектов.Каждый объект имеет определенную «позицию», но им это неизвестно, об этом знает только менеджер.Менеджер должен назначить каждому объекту позицию и поддерживать свой список объектов, отсортированных в соответствии с этим «внешним атрибутом».

Обратите внимание, что позиция объекта может измениться в любое время.В идеале я должен иметь возможность немедленно получить элемент в позиции X или в позиции элемента X в любое время.

Это код C #.Мне интересно, что было бы чистым или идиоматическим способом сделать это.

Я думал о создании внутреннего класса, подобного этому:

class SortedElement {
    public Element Elem { get; set; }
    public int Position { get; set; }
}

И затем поддержу список SortedElements.Я не знаю, это кажется мне неуклюжим.Например, два отсортированных элемента могут иметь одинаковую позицию.Я чувствую, что есть очевидное, чистое решение, которое мне не хватает.Я также мог бы сделать Положение свойством самих Элементов, но это не имеет смысла семантически, то есть у них нет причин знать об этом, кроме как облегчить мою жизнь.

Пожалуйста, заставьте меня уйти facepalm .

РЕДАКТИРОВАТЬ: Следуя совету Эрика Липперта о перечислении моих требований и хорошего сна, я понял, что должен выбрать LinkedList<Element> и использовать индекс в качестве позиции.В самом деле, наиболее распространенными операциями здесь будут вставка в начале и удаление в любом месте контейнера, которые дороги для контейнера на основе массива.Спасибо за все ответы.

Answer 1

Давайте перечислим ваши требования. Я предполагаю, что вы хотите иметь структуру данных S, которая имеет следующие операции:

• ContainsElement: принимает элемент, сообщает, находится ли элемент в S
• IsValidPosition: занимает позицию, сообщает, доступна ли эта позиция в S
• GetElementAt: занимает действительную позицию, возвращает элемент
• GetPositionOf: берет элемент, который находится в S, возвращает позицию
• InsertElementAt: принимает элемент не в S и действительную позицию. Помещает элемент в эту позицию; все элементы после этой позиции перемещаются "вверх на один".
• RemoveElementAt: занимает действительную позицию, удаляет элемент в этой позиции, все элементы после этой позиции перемещаются «на одну единицу».

Это правильная сводка операций, которые вы хотите? (Обратите внимание, что перемещение элемента в новую позицию аналогично RemoveElementAt, за которым следует InsertElementAt.)

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

Когда у нас есть четкий список требований к операциям, возникает следующий вопрос: «Каковы требования к асимптотическим характеристикам?»

Например, вы можете использовать List<T> в качестве структуры данных S; он поддерживает все эти операции. Однако, если список очень длинный, то вставка и удаление в начале списка очень дороги, как и операция «Содержит».

Есть более экзотические структуры данных, которые вы можете использовать, которые очень эффективны при моделировании вставок и удалений; мы используем такие структуры данных для моделирования изменений состояния редактора в C # IDE. Очевидно, что каждый токен, объявление переменной и т. Д. Является «элементом», который имеет «позицию», и эта позиция все время меняется по мере ввода вокруг нее; Эффективная обработка этих изменений довольно сложна, но если вы находитесь в такой проблемной области, опишите ее более четко, и мы можем дать вам указатели на структуры данных, с которыми вы можете провести некоторые исследования.

Answer 2

Похоже, вы стараетесь не описывать коллекцию как простую последовательность элементов, поэтому я приму List<T> и использование индекса в качестве позиции не может быть и речи. А как насчет Dictionary<int, Element>? Он обеспечивает уникальность и, предполагая, что эта «позиция», на которую вы ссылаетесь, является порядковой, поддерживает правильную сортировку.

Answer 3

Я думаю, что вы действительно должны использовать SortedDictionary .

Answer 4

Вы можете вести список элементов внутри класса "manager", используя общий список (List<Element>). Затем вы можете отсортировать список по своему усмотрению, используя метод Sort() класса List<T>. Например:

myList.Sort((elem1, elem2) => elem1.Name.CompareTo(elem2.Name));

В этом примере элементы сортируются по свойству «Имя», но вы можете использовать в сравнении все, что угодно, включая ваш «внешний атрибут».