Listes, dictionnaires, queues et piles : des collections C# pour tous les usages !

Aujourd’hui, nous abordons les collections. Des alternatives bien pratiques aux Array, avec de multiples avantages. On peut y insérer où en retirer plus facilement des éléments, il n’est pas nécessaire de connaître le nombre d’éléments final de la liste dès l’initialisation, et elles ont de nombreuses fonctions dédiées (tri, interrogation…). Bref, vous allez le voir, les collections sont extrêmement pratiques !

Avant toute chose, pour utiliser les collections ci-dessous, assurez-vous d’utiliser le namespace dédié :

using System.Collections.Generic;

Dans cet article, nous nous concentrons sur les fondamentaux. Notez que l’utilisation de LINQ augmente encore plus les possibilités sur les listes : LINQ, le langage de requêtes intégré de C# .NET.

List : la liste, alternative bien pratique aux tableaux

Une liste peut recevoir des éléments au fur et à mesure. Imaginez une liste de course ou une Todolist où on peut ajouter des éléments au fur et à mesure et les cocher/barrer dans un ordre différent.

Tous les éléments doivent être de même type : un type primaire int, string, … ou un objet Transform, Customer…

On l’initialise avec new List<T>(), où T est le type.

// Initialiser une liste et la remplir :
List<int> primeNumbers = new List<int>() { 2, 3, 5, 7, 11 };
// Initialiser une liste vide
List<Character> party = new List<Character>();

Ajouter des éléments avec Add(). Attention, ce n’est pas une liste d’éléments uniques, vous pouvez ajouter plusieurs fois le même objet.

// Ajout d'entiers dans notre liste primeNumbers
primeNumbers.Add(13);
primeNumbers.Add(17);

// Ajout d'instances de Character dans notre liste party
party.Add(new Character { Name = "Dumen", Strength = 7, Stamina = 9, Dexterity = 3, Role = Role.Paladin });
party.Add(new Character { Name = "Alena", Strength = 3, Stamina = 6, Dexterity = 8, Role = Role.Wizard });
party.Add(new Character { Name = "Wenfir", Strength = 9, Stamina = 7, Dexterity = 5, Role = Role.Barbarian });

Retirer des éléments : soit un élément précis Remove(element), ou soit un élément à un index précis (RemoveAt(2)) Comme les éléments ne sont pas unique, c’est la première instance trouvée dans la liste qui est effacée. Pour effacer toutes les instances d’un élément, c’est RemoveAll(element).

// Test sur un personnage : on l'enlève de l'équipe s'il n'a plus de HP.
if(currentCharacter.HealthPoints <= 0)
{
    Console.WriteLine($"{currentCharacter.Name} is dead!");
    party.Remove(currentCharacter);
}
// On enlève le premier élément d'une liste :
primeNumbers.RemoveAt(1);

Comme pour les tableau, la syntaxe liste[i] permet d’obtenir ce qui est rangé à l’index i de la liste. Il est possible de vérifier aussi si la liste contient un objet spécifique avec liste.Contains(xxx) :

Itérer sur la liste est très utile. C’est possible avec une boucle « foreach ». Si on a besoin de l’index, on pourra utiliser une boucle « for » classique. Attention : pour les listes on utilise Count et non Length pour avoir le nombre d’éléments.

// Itérations avec la boucle foreach :
foreach (int i in primeNumbers)
{
    Console.WriteLine($"{i} is a prime number.");
}
// Itérations avec une boucle for :
for(int i = 0; i < party.Count; i++)
{
     Console.WriteLine($"Slot {i} : {party[i].Name}");
}

Ce sont les principales méthodes pour manipuler une liste, mais il y en a d’autres (pour certaines, directement héritées des Array()) :

1. Clear() permet de réinitialiser la liste
2. Sort() permet de trier la liste
3. Reverse() inverse les éléments de la liste
4. IndexOf() donne l’index d’un élément spécifique dans la liste
5. AddRange() permet d’ajouter une liste à la fin d’une autre liste
6. Insert(int index, T item) permet d’ajouter l’élément item à la position index. De même, InsertRange() permet d’ajouter une collection à la position index.

Pour avoir plein d’autres exemples bien illustrés, je vous conseille l’article de Dot Net Perls sur les listes (en anglais).

Dictionary : le Dictionnaire, définir pour mieux retrouver

Le Dictionnaire est une liste de paires clés et valeurs, qui peuvent être de différents types. Chaque clé du dictionnaire est unique, mais on peut retrouver plusieurs fois la même valeur associée à différente clés.

Initialisation avec new Dictionary<TKey,TValue>() :

// Dictionnaire associant à chaque niveau (Key, int) le temps minimum que le joueur a mis pour le compléter (Value, float) :
Dictionary<int, float> LevelsTime = new Dictionary<int, float>();

Pour ajouter un élément, c’est aussi avec Add(Key, Value). Le dictionnaire dispose aussi de TryAdd(Key, Value) qui permet d’ajouter une valeur seulement si celle-ci n’est pas présente. Selon l’utilisation du dictionnaire, il peut être utile de vérifier si la clé existe, voire de vérifier sa valeur (avec dictionaryName[Key]).

Voir l’exemple ci-dessous : si je n’ai pas enregistré le temps d’un joueur pour un niveau, j’ajoute directement le temps dans le dictionnaire. Si j’ai déjà un temps enregistré, je ne modifie la valeur du dictionnaire que si le temps enregistré est meilleur (donc plus petit) que le temps enregistré précédemment.

if (!LevelsTime.ContainsKey(currentLevel))
{
    LevelsTime.Add(currentLevel, currentTime);
}
else if(LevelsTime[currentLevel] > currentTime)
{
    LevelsTime[currentLevel] = currentTime;
}

La méthode recommandée pour récupérer une valeur dans le dictionnaire, c’est TryGetValue(T Key, out T Value) : cette fonction retourne un booléen (indiquant si oui ou non le dictionnaire a une valeur pour cette clé) et exporte la valeur dans une variable (via le mot-clé out), ce qui permet de prévoir directement un comportement au cas où il n’y a pas de valeur pour la clé.

if (LevelsTime.TryGetValue(selectedLevel, out float timeForSelectedLevel))
{
    Console.WriteLine($"Level {selectedLevel} was finished in {timeForSelectedLevel} seconds.");
}
else
{
    Console.WriteLine($"Level {selectedLevel} has not been completed yet.");
}

Bref, pour des paires « Clé unique / Valeur non nécessairement unique », pensez au Dictionary.

Queue : premier arrivé, premier servi

La Queue est une collection d’objets, qui fonctionne selon la méthode du premier arrivé, premier sorti. J’évoque « premier servi » pour nous faciliter la représentation : une queue c’est une file d’attente, par exemple à votre franchise de cafés et lattés favorite.

Queue<Customer> WaitList = new Queue<Customer>();

Ici, pas de Add() et de Remove(), on ajoute toujours à la fin de la file, et on récupère spécifiquement le premier élément de la file, en le supprimant au passage.

1. WaitList.Enqueue(element) : ajoute element à la fin de WaitList
2. var customer = WaitList.Dequeue() : supprime le plus ancien élément de WaitList, et on le récupère dans customer
3. var customer = WaitList.Peek() : la version « non destructive » de Dequeue() : cette méthode retourne le plus ancien élément de WaitList
4. Nous disposons de versions « Try » pour ces deux dernières fonctions : WaitList.TryDequeue(out T customer) et WaitList.TryPeek(out T element) retournent true si WaitList contient au moins un élément, et le copie dans le paramètre element (en le supprimant pour TryDequeue).
5. WaitList.Contains(customer) (résultat = booléen) permet de vérifier si customer est présent dans la liste
6. WaitList.Clear() vide complètement la file d’attente

Dans la conception de jeu vidéo, une liste de type Queue peut être très utile si on veut instancier une quantité limitée d’objets. On les ajoute dans la queue au fur et à mesure qu’on les instancie, et on pourra à tout moment récupérer la plus vieille instance, pour la détruire en priorité, voire réinitialiser cette instance pour s’en resservir.

Queue<Projectile> SpawnedProjectiles = new Queue<Projectile>();
int maximumProjectiles = 30;


// Plus loin, dans le game loop ou une coroutine...
if (SpawnedProjectiles.Count < maximumProjectiles)
{
    SpawnedProjectiles.Enqueue(new Projectile(spawnCoordinates));
}
else
{
    var oldestProjectile = SpawnedProjectiles.Dequeue();
    oldestProjectile.ReinitializeAt(spawnCoordinates);    // Fonction maison pour réinitialiser un objet Projectile
    SpawnedProjectiles.Enqueue(oldestProjectile);
}

Stack (pile) : dernier arrivé, premier sorti

La collection de classe Stack est une pile, où le dernier élément ajouté est le premier à être sorti. Ça serait perçu comme injuste dans une file d’attente classique, alors imaginez plutôt une pile de feuilles qui s’entasse bien droit. Vous ne pouvez alors que prendre la feuille qui est sur le haut de la pile.

Stack<string> Names = new Stack<string>();

Les commandes d’ajout et de récupération sont différentes d’une liste ou d’une queue, c’est plus lisible et le comportement est simple à prédire.

Pour cet exemple, imaginons que nous avons une pile de linge, Laundry :

1. Laundry.Push(element) : ajoute element sur le dessus de la stack Laundry
2. var clothing = Laundry.Pop() : enlève l’élèment du dessus de la stack Laundry et le récupère dans clothing.
3. var clothing = Laundry.Peek() : version non destructive de Pop, juste pour voir.
4. Laundry.TryPop(out T element) et Laundry.TryPeek(out T element) : les fonctions « Try » respectives de Pop et Peek.
5. Enfin, nous avons les habituels Laundry.Contains(element) et Laundry.Clear(), respectivement vérifier la présence de élément et pour vider toute la pile.

Voici un exemple pour ce tas de linge :

Stack<string> Laundry = new Stack<string>();

Laundry.Push("red shirt");
Laundry.Push("green socks");
Laundry.Push("white socks");
Laundry.Push("blue socks");
// red shirt est au fond de la pile, blue socks est au-dessus !

Console.WriteLine("I took " + Laundry.Pop() + " from the laundry basket.");
Console.WriteLine("I see " + Laundry.Peek() + " on the top on the laundry pile.");
// blue sock est récupéré et sorti de la pile Laundry.
// C'est donc white socks qu'on peut voir en haut du panier (on a consulté le haut de la pile sans effacer ce qui y est présent)

Dans un contexte de développement de jeu vidéo, je n’ai pas eu l’occasion d’utiliser de collection de type Stack(). Mais on peut imaginer une pile de butin, par exemple, ou des personnages qui rentrent dans un véhicule qui ne dispose que d’une seule entrée (et le dernier rentré est donc le premier sorti).

À savoir sur les collections

Il est bon de savoir que ces différentes collections existent et elles peuvent toutes trouver leurs usages.

Concrètement, vous vous servirez probablement le plus souvent d’une liste List() classique, et parfois d’un dictionnaire. Il est assez simple de récupérer le premier ou le dernier élément d’une liste et d’imiter le comportement qu’on a avec une Queue ou un Stack. Ces collections-là vous seront utile dans des cas particuliers.

Notez que pour des données où la quantité finale est connue et sur laquelle vous n’aurez pas à faire de tri ou d’insertion, un Array() peut être plus adapté, notamment quand il y a beaucoup de données, pour économiser l’opération d’indexation des éléments de la collection.

Enfin, il existe depuis C#.NET 4 des collections spécifiques pour le multithreading. Si votre application fonctionne sur différent threads en même temps, il faut utiliser l’espace de nom System.Collections.Concurrent et utiliser les collections correspondantes : ConcurrentBag, ConcurrentDictionnary, ConcurrentQueue, ConcurrentStack et BlockingCollection.