Mantenere un elenco ordinato di elementi, ordinato secondo un attributo esterna a quell'elemento

Question

Ho un "manager" di classe il mantenimento di un elenco di oggetti. Ogni oggetto ha una "posizione" certo, ma questo non è noto a loro, solo il gestore sa su questo. Il gestore deve assegnare ciascun oggetto una posizione e mantenere il suo elenco di oggetti ordinati secondo questo "attributo esterno".

Si noti che la posizione di un oggetto può cambiare in qualsiasi momento. Idealmente dovrei essere in grado di ottenere immediatamente sia elemento alla posizione X o la posizione di Element X in qualsiasi momento.

Si tratta di codice C #. Mi chiedo che cosa sarebbe un modo pulito o idiomatica di fare questo.

ho pensato di fare una classe interna in questo modo:

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

E poi mantenere un elenco di SortedElements. Non lo so, mi sembra goffo a me. Due SortedElements potrebbero avere la stessa posizione per esempio. Mi sento come se ci fosse un evidente, soluzione pulita che mi manca. Potrei anche rendere la posizione di una proprietà degli elementi stessi, ma non ha senso semanticamente, il che significa non c'è alcun motivo per loro di conoscere che, salvo rendere la vita più facile.

Si prega di farmi andare facepalm .

EDIT: Seguendo il consiglio di Eric Lippert di elencare le mie esigenze, e dormire bene la notte, mi sono reso conto che dovrei optare per una LinkedList<Element> e utilizzare l'indice come la posizione. Infatti, le operazioni più comuni qui saranno inserimento all'inizio e rimozione ovunque all'interno del contenitore, che sono costosi su un contenitore basata su array. Grazie per tutte le risposte.

Answer 1

Diamo elencare le vostre esigenze. Presumo che si desidera avere una struttura dati S, che ha le seguenti operazioni:

• ContainsElement: prende un elemento, ti dice se l'elemento è in S
• IsValidPosition: prende una posizione, ti dice se tale posizione è disponibile in S
• getElementAt: prende una posizione valida, restituisce un elemento
• GetPositionOf: prende un elemento che è in S, restituisce una posizione
• InsertElementAt: prende un elemento non in S e una posizione valida. Mette l'elemento in tale posizione; tutti gli elementi dopo che si muovono in posizione "da uno".
• RemoveElementAt: prende una posizione valida, rimuove l'elemento in quella posizione, tutti gli elementi dopo che la posizione movimento "in basso di una"
.

È che una corretta sintesi delle operazioni che si desidera? (Si noti che lo spostamento di un elemento in una nuova posizione è la stessa RemoveElementAt seguita da InsertElementAt.)

Se quelli non sono una sintesi corretta delle operazioni, allora sarebbe utile se si desidera elencare esattamente l'insieme di operazioni che si desidera che il tipo di dato astratto a supporto.

Una volta che abbiamo una chiara lista di requisiti per le operazioni allora la domanda successiva è "quali sono i requisiti di prestazione asintotica?"

Ad esempio, è possibile utilizzare un List<T> come struttura di dati S; supporta tutte quelle operazioni. Tuttavia, se la lista è molto lunga quindi inserire e rimuovere all'inizio della lista è molto costoso, come è il "Contiene" operazione.

Ci sono strutture di dati più esotici è possibile utilizzare che sono altamente efficienti a inserimenti di modellazione e rimozioni; usiamo tali strutture dati per modellare le modifiche allo stato dell'editor in C # IDE. Ovviamente ogni token, dichiarazione di variabile, e così via, è un "elemento" che ha una "posizione" e che la posizione cambia continuamente durante la digitazione intorno; manipolazione di tali modifiche in modo efficiente è molto impegnativo, ma se questo è il tipo di problema di spazio ci si trovi, poi descriverlo in modo più chiaro e possiamo darvi indicazioni su strutture di dati si può fare qualche ricerca su.

Answer 2

Sembra che tu stia prendendo dolori per evitare che descrive la collezione come una semplice sequenza di elementi, quindi darò per scontato un List<T> e utilizzando l'indice come la posizione è fuori questione. Che dire di un Dictionary<int, Element>? Si impone unicità e assumendo questa "posizione" si fa riferimento a è ordinale, mantiene il corretto ordinamento.

Answer 3

Si potrebbe mantenere l'elenco degli elementi interni alla classe "manager" con un elenco generico (List<Element>). È quindi possibile ordinare l'elenco tuttavia si voleva con il metodo Sort() della classe List<T>. Ad esempio:

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

In questo esempio gli elementi sono ordinati per la proprietà "Name", ma è possibile utilizzare qualsiasi cosa in confronto, compreso il vostro "attributo esterno".

Answer 4

Credo che si dovrebbe davvero usare un SortedDictionary .