```html <p>c# Ajout d'une méthode Remove(int index) à la classe Queue .NET</p> ```

Question

Je voudrais utiliser la classe de file d'attente générique telle que décrite dans le framework .NET (3.5) mais j'aurai besoin d'une méthode Remove(int index) pour supprimer des éléments de la file d'attente. Est-ce que je peux obtenir cette fonctionnalité avec une méthode d'extension? Quelqu'un pourrait-il me guider dans la bonne direction?

Answer 1

Quelqu'un développera probablement une meilleure solution, mais d'après ce que je vois, vous devrez retourner un nouvel objet Queue dans votre méthode de suppression. Vous voudrez vérifier si l'index est hors limites et il se peut que j'aie mal compris l'ordre des éléments ajoutés, mais voici un exemple rapide et dirty qui pourrait facilement être transformé en une extension.

public class MyQueue : Queue {
    public MyQueue() 
        : base() {
        // Constructeur par défaut
    }

    public MyQueue(Int32 capacity)
        : base(capacity) {
        // Constructeur par défaut
    }

    /// 
    /// Supprime l'élément à l'index spécifié et retourne une nouvelle Queue
    /// 
    public MyQueue RemoveAt(Int32 index) {
        MyQueue retVal = new MyQueue(Count - 1);

        for (Int32 i = 0; i < this.Count - 1; i++) {
            if (i != index) {
                retVal.Enqueue(this.ElementAt(i));
            }
        }

        return retVal;
    }
}

Answer 2

Je ne pense pas que nous devrions utiliser List pour émuler une file d'attente, car pour une file d'attente, les opérations d'ajout et de suppression doivent être très performantes, ce qui ne serait pas le cas en utilisant un List. Pour la méthode RemoveAt, cependant, il est acceptable que la performance ne soit pas optimale, car ce n'est pas le but principal d'une Queue.

Ma façon d'implémenter RemoveAt est en O(n) mais la file d'attente conserve toujours un ajout en O(1) (parfois le tableau interne doit être réalloué ce qui rend les opérations en O(n)) et toujours un retrait en O(1).

Voici mon implémentation d'une méthode d'extension RemoveAt(int) pour une Queue:

public static void RemoveAt(this Queue queue, int index)
{
    Contract.Requires(queue != null);
    Contract.Requires(index >= 0);
    Contract.Requires(index < queue.Count);

    var i = 0;

    // Déplacer tous les éléments avant celui à supprimer vers l'arrière
    for (; i < index; ++i)
    {
        queue.MoveHeadToTail();
    }

    // Supprimer l'élément à l'index
    queue.Dequeue();

    // Déplacer tous les éléments suivants vers la fin de la file d'attente.
    var queueCount = queue.Count;
    for (; i < queueCount; ++i)
    {
        queue.MoveHeadToTail();
    }
}

Où MoveHeadToTail est défini comme suit:

private static void MoveHeadToTail(this Queue queue)
{
    Contract.Requires(queue != null);

    var dequed = queue.Dequeue();
    queue.Enqueue(dequed);
}

Cette implémentation modifie également la Queue réelle au lieu de renvoyer une nouvelle Queue (ce qui, je pense, est plus conforme à d'autres implémentations de RemoveAt).

Answer 3

En fait, cela va à l'encontre de tout le but de la file d'attente et la classe que vous finirez par créer violera totalement la sémantique FIFO.

Answer 4

Si la file d'attente est utilisée pour conserver l'ordre des éléments dans la collection, et si vous n'aurez pas d'éléments en double, alors un SortedSet pourrait être ce que vous cherchez. Le SortedSet agit un peu comme une List, mais reste ordonné. Idéal pour des choses comme les sélections déroulantes.

Answer 5

La solution de David Anderson est probablement la meilleure mais a un peu d'overhead. Utilisez-vous des objets personnalisés dans la file d'attente ? Si c'est le cas, ajoutez un booléen comme "cancel".

Vérifiez avec vos travailleurs qui traitent la file d'attente si ce booléen est défini, puis passez-le.