Sont le vecteur d'un cas particulier de listes liées?

Quand on parle de la STL, j'ai plusieurs camarades de classe m'indiquant que "les vecteurs sont liés listes".

J'en ai une autre en arguant que si vous appelez la méthode effacer() avec un itérateur, il rompt le vecteur, puisque c'est une liste liée.

Ils ont aussi tendance à ne pas comprendre pourquoi je suis toujours en argumentant que le vecteur sont contigus, comme n'importe quel autre tableau, et ne semblent pas comprendre ce que l'accès aléatoire moyen. Vecteur strictement contigus comme des tableaux, ou tout simplement à la plupart des contigus ? (pour l'exemple on va allouer plusieurs segments contigus si l'ensemble du tableau ne correspondent pas).

InformationsquelleAutor jokoon | 2011-01-15
  1. 27

    Je suis désolé de dire que vos camarades de classe sont complètement faux. Si vos camarades de classe peut honnêtement dire que "les vecteurs sont liés listes", alors vous devez respectueusement leur dire qu'ils doivent ramasser une bonne C++ livre (ou de tout ordinateur décent livre scientifique) et de le lire. Ou peut-être même les articles de Wikipédia pour vecteurs et listes. (Voir aussi les articles pour les tableaux dynamiques et les listes liées.)

    Vecteurs (comme dans std::vector) ne sont pas les listes chaînées. (Notez que std::vector ne dérivent pas de std::list). Alors que les deux peuvent stocker une collection de données, comment un vecteur de fait, c'est complètement différent de la façon dont une liste liée t-il. Par conséquent, ils ont des caractéristiques de performance différentes dans des situations différentes.

    Par exemple, les insertions sont une constante de temps de fonctionnement sur les listes liées, alors qu'il est linéaire en temps de l'opération sur les vecteurs si elle est insérée dans un endroit autre que la fin. (Toutefois, il est amorti constante de temps si vous insérer, à la fin d'un vecteur.)

    La std::vector classe en C++ sont nécessaire être contiguës par la norme C++:

    23.2.4/1 modèle de Classe vector

    Un vector est un genre de séquence qui prend en charge des itérateurs à accès aléatoire. En outre, il prend en charge (amorti) constante de temps d'insérer et effacer des opérations, à la fin, insérer et effacer dans le moyen de prendre le temps linéaire. La gestion du stockage est géré automatiquement, même si elles peuvent être à en améliorer l'efficacité. Les éléments d'une vector sont stockés de manière contiguë, ce qui signifie que si v est un vector<T, Allocator> où T est un type autre que bool, puis il obéit à l'identité &v[n] == &v[0] + n pour tous 0 <= n < v.size().

    De la comparer à std::list:

    23.2.2/1 modèle de Classe list

    Un list est un genre de séquence qui prend en charge itérateurs bidirectionnels et permet à temps constant insérer et effacer des opérations n'importe où à l'intérieur de la séquence, de la gestion du stockage gérés automatiquement. À la différence des vecteurs (23.2.4) et deques (23.2.1), accès aléatoire rapide aux éléments de la liste n'est pas pris en charge, mais de nombreux algorithmes seulement besoin d'un accès séquentiel de toute façon.

    Clairement, le C++ standard stipule qu'un vecteur et une liste de deux récipients différents que de faire les choses différemment.

    Vous ne pouvez pas "casser" un vecteur de (au moins pas intentionnellement) en appelant simplement erase() avec une pièce d'itérateur. Que ferait std::vectors plutôt inutile puisque le but de son existence est de gérer la mémoire pour vous!

    • silico: en ce qui concerne la "pause", appelant erase invalidera les itérateurs d'éléments au-delà de la effacées point (et "fin").
    • M.: Droit, l'appel de erase() va invalider des itérateurs, mais il ne va pas se casser ou d'endommager le vecteur lui-même. Je m'adressais à la réclamation que erase() va "casser le vecteur, puisque c'est une liste chaînée," ce qui est absurde.
    • silico: oui, je comprends ce que tu veux dire, mais je pense que l'OP (et ses amis) utilisés "pause", parce qu'ils ne comprennent pas ce que l'invalidation signifiait, depuis l'effacement d'un élément à partir d'une liste n'a pas d'effet d'invalider les autres itérateur.
    • ils pensent également que chaque élément du vecteur a un côté et d'un élément pointeur
    • Seulement doublement lié liste des éléments suivant et précédent pointeurs. Les éléments du vecteur sont contigus, et, par conséquent, ne nécessite pas d'autre, ni précédente pointeurs. Encore une fois, si vos camarades de classe peut sérieusement dire que, vous devez leur dire (respect!) pour ramasser C++ livre.
    • Je voulais juste être sûr pour moi le premier, je ne m'en soucie pas vraiment ce qu'ils pensent, parce que je n'aime pas vraiment la façon dont ils me le dire, tous de rire et de la merde. Je vais juste le lien de cette question/réponse la prochaine fois ils m'emmerdent avec ça.

    InformationsquelleAutor In silico
  2. 8

    vector tiendra tous de son stockage dans un seul endroit. Un vector n'est pas même à distance comme une liste chaînée. En effet, si je devais choisir deux structures de données qui ont été les plus dissemblables les uns les autres, il serait vector et list. "Au plus contiguë" est de savoir comment un deque fonctionne.

    Vecteur:

    1. Garantie de stockage contigu de tous les éléments de copier ou de déplacer des éléments.
    2. O(1) temps d'accès.
    3. O(n) pour insérer ou retirer.
    4. Itérateurs invalidé lors de l'insertion ou de la suppression de tout élément.

    Liste:

    1. Pas de stockage contigu à tout jamais de copie ou déplace des éléments.
    2. O(n) le temps d'accès - plus de toutes les sales cache vous allez obtenir.
    3. O(1) d'insérer ou de retirer.
    4. Itérateurs valable aussi longtemps que cet élément n'est pas supprimé.

    Comme vous pouvez le voir, ils se comportent différemment dans chaque structure de données de cas d'utilisation.

    InformationsquelleAutor Puppy
  3. 2

    Par définition, vectors sont des blocs de mémoire contigus comme C des tableaux. Voir: http://en.wikipedia.org/wiki/Vector_(C%2B%2B)

    Vecteurs permettent d'accès aléatoire; c'est,
    un élément d'un vecteur peut être
    référencé dans la même manière que
    les éléments d'un tableau (par les indices de tableau).
    Les listes liées ensembles, sur les autres
    à la main, ne prennent pas en charge l'accès aléatoire ou
    l'arithmétique des pointeurs.

    InformationsquelleAutor Daniel A. White
  4. 0

    Vecteurs ne sont pas liées liste, ils fournissent l'accès aléatoire et sont contigus, comme des tableaux. Afin d'atteindre cet objectif, ils ré-allouer de la mémoire sous le capot.

    Liste est conçu pour permettre une insertion rapide et de suppressions, tout n'est pas d'invalider toutes les références ou les itérateurs à l'exception de
    ceux de l'élément supprimé.

    InformationsquelleAutor Neera