Est la liste <T> vraiment un tableau secret en C #?

Question

J'ai été regarder .NET bibliothèques à l'aide de ILSpy et avons rencontré List<T> définition de la classe en System.Collections.Generic d'espace de noms. Je vois que la classe utilise des méthodes comme celle-ci:

// System.Collections.Generic.List<T>
/// <summary>Removes all elements from the <see cref="T:System.Collections.Generic.List`1" />.</summary>
public void Clear()
{
    if (this._size > 0)
    {
        Array.Clear(this._items, 0, this._size);
        this._size = 0;
    }
    this._version++;
}

Ainsi, l' Clear() méthode de List<T> classe utilise réellement Array.Clear méthode. J'ai vu de nombreux autres List<T> méthodes que l'utilisation de la Matrice de choses dans le corps.

Est-ce à dire qu' List<T> est en fait une infiltration de Tableau ou de la Liste utilise seulement une partie des méthodes de Tableau?

Je sais que les listes sont de type sécurisé et ne nécessitent pas de boxing/unboxing mais cela a confondu un peu de moi.

Answer 1

La classe de liste n'est pas elle-même un tableau. En d'autres termes, il ne dérive pas d'un tableau. Au lieu de cela, il encapsule un tableau qui est utilisé par l'implémentation pour contenir les éléments membres de la liste.

Étant donné que List<T> offre un accès aléatoire à ses éléments, et que ces éléments sont indexés 0..Count-1 , l'utilisation d'un tableau pour stocker les éléments est la mise en œuvre évidente.

Answer 2

Cela a tendance à surprendre les programmeurs en C++ qui savent std::list. Une liste liée, couverts de .NET ainsi avec la classe LinkedList. Et a les mêmes perf caractéristiques, O(1) pour les insertions et les suppressions.

Vous devriez cependant, en général l'éviter. Les listes chaînées ne fonctionnent pas bien sur les processeurs modernes. Qui dépend largement de la caches cpu pour obtenir des performances acceptables avec la mémoire c'est de nombreuses fois plus lent que l'exécution de base. Un tableau simple est de loin la structure de données qui prend le plus de profit du cache. L'accès à un élément donne de très forte chances que les éléments suivants sont présents dans le cache bien. Ce n'est pas le cas pour une liste liée, les éléments ont tendance à être dispersés dans l'espace d'adressage, faire un cache miss probable. Ils peuvent être très coûteux, 200 cycles avec le cpu ne rien faire, mais en attente sur la mémoire du sous-système de fourniture de données.

Mais gardez la perf caractéristiques à l'esprit, l'ajout ou la suppression d'un élément qui n'est pas à la fin de la Liste des coûts de O(n), tout comme un tableau. Et une grande Liste peut générer beaucoup de déchets dans le tableau doit être élargie, la définition de la Capacité de propriété peuvent beaucoup aider à éviter cela. Plus à ce sujet dans cette réponse. Et sinon exactement les mêmes préoccupations pour le std::vector<>.

Answer 3

Oui, List<T> utilise un tableau en interne pour stocker les éléments, bien que dans la plupart des cas, le tableau est en fait plus grande que le nombre d'éléments dans la collection, il a un supplément de "remplissage" à la fin de sorte que vous pouvez ajouter de nouveaux éléments sans avoir à réallouer la mémoire à chaque fois. Il garde la trace de la taille réelle de la collection avec un champ distinct (vous pouvez voir this._size dans votre code généré). Lorsque vous ajoutez plus d'éléments que l'ensemble a de la place pour, il va attribuer automatiquement un nouveau plus grand tableau -- deux fois plus grande, je pense -- et une copie sur tous les éléments existants.

Si vous êtes préoccupé par un List<T> utilise plus de mémoire que nécessaire, vous pouvez définir la taille du tableau explicitement le constructeur de remplacer accepte capacity paramètre, si vous connaissez la taille à l'avance, ou appelez l' TrimExcess() méthode pour s'assurer que la matrice est (presque) à la taille de la collection.

Answer 4

Random access memory est un tableau, donc dans ce sens toutes les structures de données de listes liées à des tas et au-delà, qui reposent sur le hasard-l'accès à la mémoire pour leur performance, les comportements, sont construits sur le tableau qui est de la mémoire système. C'est plus une question de combien de niveaux d'abstraction sont entre les deux.

Bien sûr, dans un cadre moderne de la mémoire virtuelle de la machine, l'accès aléatoire de la mémoire système est lui-même une abstraction construite sur un complexe virtuel-modèle de mémoire multi-niveaux en pipeline caches, non mis en cache RAM et de disque.