la complexité de set::insert

J'ai lu que l'opération d'insertion dans un ensemble ne prend que log(n) fois. Comment est-ce possible?

À insérer, nous avons d'abord trouver l'emplacement dans le tableau trié où le nouvel élément doit s'asseoir. À l'aide de la recherche binaire il faut log(n). Puis à l'insérer dans l'emplacement de tous les éléments de réussir, il doit être déplacé d'une position vers la droite. Il prend un autre temps.

Mon doute est basé sur mes connaissances est mis en œuvre comme un tableau et les éléments qui sont stockés dans l'ordre de tri. S'il vous plaît corrigez-moi si ma compréhension est erronée.

Vous êtes en supposant que std::set est mis en œuvre comme un tableau trié. Pourquoi?
Prises de cppreference: Ensembles sont généralement mises en œuvre comme des arbres rouge-noir.
Maintenant que je suis arrivé à savoir que les jeux sont mis en œuvre à l'aide de rouge-l'arbre noir. Merci chris
Eh bien, il devrait être connue à tout le monde de se soucier des structures de données que les jeux sont généralement mises en œuvre à l'aide de arbres ou de tables de hachage, pas à l'aide de tableaux, en raison de la performance... Diable, en Java, vous devez décider si vous voulez un HashSet ou un TreeSet (qui est un SortedSet), et je doute qu'il y est un ArraySet disponibles. (Notez que inmodifiable ensembles efficace sera mis en œuvre comme un tableau trié, à l'aide de binarySearch - donc en fait comme une triés arbre stockées dans un tableau)
En fait, d'une télévision ensemble est, dans de nombreux cas, plus performant qu'un arbre ensemble, en raison de la localité de cache.

OriginalL'auteur bibbsey | 2012-10-08

  1. 19

    std::set est couramment mis en œuvre comme un rouge-noir binaires un arbre de recherche. Insertion sur cette structure de données est un des pires cas de O(log(n)) de la complexité, comme l'arbre est maintenu en équilibre.

    Pas tout à fait: la modification peut entraîner un rééquilibrage qui est une fois de plus un O(log n) opérations.
    Avec un rouge-noir de l'arbre, de l'insertion doit avoir un pire cas en O(log(n)), même en tenant compte de rééquilibrage.
    Oui, bien sûr, je n'ai pas de concours de. Mais vous avez dit que la modification de l'arbre est en O(1). Que c'est faux.
    Modifié ma réponse.

    OriginalL'auteur cdhowie

  2. 0

    HashSet, LinkedHashSet, et EnumSet add(), remove() et() les opérations coût constant O(1) temps c'est parce que de l'intérieur HashMap mise en œuvre.

    Pour la structure de l'arbre TreeMap et ConcurrentSkipListMap le put(), get(), remove(), containsKey() opérations en temps est O(log(n)).

    de sorte que le TreeSet a O(log (n)) le temps de la complexité .

    Cela semble être, en se référant à la Java des collections de la bibliothèque, plutôt que le C++ conteneurs de la bibliothèque

    OriginalL'auteur khawar