ce qui est sous-jacente à la structure de données de liste STL, vecteur et de l'ensemble?

ce qui est sous-jacente à la structure de données de liste STL, vecteur et de l'ensemble ?

Ma solution:

  • vecteur : (dynamique alloué) tableau
  • liste: ?
  • ensemble: tas (ou un arbre binaire avec tous les nœuds terminaux situé le plus à gauche possible et de garder min/max élément sur le dessus)

Droit?

  • La mise en œuvre définies, mais en général, std::vector est un tableau alloué dynamiquement. std::list est une liste doublement chaînée (C++11 introduit std::forward_list qui est une seule liste liée), et un set est généralement basé sur arbres rouge-noir, mais rien qui correspond à l'amorti, la complexité et le comportement des exigences des interfaces définies dans la norme sont acceptables implémentations.
InformationsquelleAutor user1002288 | 2011-10-26
  1. 20

    Sur la base des observations, à clarifier, ce sont les choix les plus courants, mais basée sur la complexité et à d'autres facteurs, la sauvegarde de ces implémentations peuvent varier:

    Vecteur = dynamiquement le redimensionnement de la matrice de

    Liste = Liste Doublement Chaînée

    Set = Rouge/Noir Arbre (équilibré Arbre de Recherche Binaire)

    Je pense que vous pourriez éventuellement être mélanger des Tas et des techniciennes se chargent. Un tas est vu comme un arbre, mais c'est en fait construit sur un indexables structure de liste (par exemple de matrice ou vecteur). C++ offre des tas de fonctions via le algorithme d'en-tête dans la STL . Techniciennes se chargent plus d'une clé/valeur en fonction de la structure utilisée pour faciliter la recherche (qui est ce que généralement vous voulez pour un jeu).

    • liste est une liste doublement chaînée
    • C'est généralement vrai, mais notez que ce n'est pas la seule option (ça dépend de l'implémentation).
    • la carte est rouge-noir arbre, le jeu n'est pas parce que les éléments ne sont pas triés. Quelle est la diff entre la liste et liste chaînée ? qu'est-ce que la structure de données de "liste" ? une liste?
    • C'est Dépendant de l'Implémentation, mais la complexité, la Norme exige laisse peu d'options pour la radicalement différentes implémentations.
    • a commander exigences. C++11 est std::unordered_set ne l'est pas. double liaison de la liste est un groupe de nœuds qui ont des références pour le nœud avant et après (ou NULL).
    • Bien que, dans la pratique, vous avez raison, de la bibliothèque standard de mise en œuvre est libre d'utiliser des structures de données qu'il veut, aussi longtemps qu'ils remplissent les garanties et les interfaces spécifiées dans la norme.
    • Bon appel. Je vais préciser.
    • vrai, mais std::list prend en charge itérateurs bidirectionnels et -- doit être à temps constant. Plus les autres contraintes de temps, ce serait un défi de mettre en œuvre la liste de pas à l'aide d'une double liste chaînée.
    • Accordé, il peut varier. Carte, Définir, MultiSet et MultiMap sont vraiment les Types de Données Abstraites (ADTs) qui définissent le comportement. L'implémentation sous-jacente pourrait être mis en œuvre avec toute la structure de données (généralement un BST variante ou une table de hachage (hashtable) en fonction désirée de la complexité et de l'exécutant caprices.
    • En fait j'ai été de ne pas répondre à @Prétorienne et faisait référence à set, qui peut facilement être mis en œuvre dans de nombreuses façons 🙂

    InformationsquelleAutor Brent Writes Code
  2. 5

    La norme donne aucune garantie sur ce que les structures de données sont utilisés, il y a seulement de la complexité des garanties, de sorte que la mise en œuvre peut choisir une structure qui les réalise.

    Cela dit, std::vector est généralement un tableau dynamique, std::list est probablement un liste à double liaison et std::set est le plus souvent une sorte de auto-équilibrage arbre binaire.

    InformationsquelleAutor Fanael