Comment insérer efficacement une plage d’entiers consécutifs dans un std :: set?

En C ++, j’ai un std :: set que je voudrais insérer une plage d’entiers consécutifs. Comment puis-je le faire efficacement, espérons-le en temps O (n), où n est la longueur de la plage?

Je pense que j’utiliserais la version inputIterator de std :: insert, mais je ne sais pas trop comment construire l’iterator d’entrée.

std::set mySet; // Insert [34 - 75): mySet.insert(inputIteratorTo34, inputIteratorTo75); 

Comment puis-je créer l’iterator d’entrée et sera-ce O (n) sur la taille de la plage?

Le moyen efficace d’insérer des éléments déjà commandés dans un ensemble consiste à indiquer à la bibliothèque où se trouvera le prochain élément. Pour cela vous voulez utiliser la version de insert qui prend un iterator:

 std::set::iterator it = mySet.end(); for (int x : input) { it = mySet.insert(it, x); } 

D’autre part, vous pouvez envisager d’autres conteneurs. Autant que possible, utilisez std::vector . Si le nombre d’insertions est faible comparé aux recherches, ou si toutes les insertions ont lieu à l’avance, vous pouvez alors créer un vecteur, le sortinger et utiliser lower_bound pour les recherches. Dans ce cas, l’entrée étant déjà sortingée, vous pouvez ignorer le sorting.

Si des insertions (ou des suppressions) se produisent partout, vous pouvez envisager d’utiliser std::unordered_set qui a un coût moyen d’insertion (par élément) et de recherche de O(1) .

Dans le cas particulier du suivi de petits nombres dans un ensemble, qui sont tous petits (34 à 75 sont de petits nombres), vous pouvez également utiliser des bits ou même un tableau simple de valeurs booléennes dans lequel vous définissez les éléments sur true lors de leur insertion. L’un ou l’autre aura l’insertion O(n) (tous les éléments) et la recherche O(1) (chaque recherche), ce qui est meilleur que l’ensemble.

Un moyen de Boost pourrait être:

  std::set numbers( boost::counting_iterator(0), boost::counting_iterator(10)); 

Un excellent lien pour d’autres réponses, spécialement la réponse de @ Mani

std :: set est un type d’arborescence de recherche binary, ce qui signifie qu’une insertion coûte en moyenne 0 (lgn),

c ++ 98: Si N éléments sont insérés, Nlog (taille + N) en général, mais linéaire en taille + N si les éléments sont déjà sortingés selon le même critère de classement utilisé par le conteneur.

c ++ 11: Si N éléments sont insérés, Nlog (taille + N). Les implémentations peuvent optimiser si la plage est déjà sortingée.

Je pense que l’implémentation C ++ 98 va tracer le nœud d’insertion actuel et vérifier si la valeur suivante à insérer est supérieure à celle actuelle, auquel cas il n’est pas nécessaire de recommencer à partir de la racine.

dans c ++ 11, il s’agit d’une optimisation facultative. Vous pouvez donc implémenter une structure de skiplist et utiliser cette plage-insert feture dans votre outil, ou vous pouvez optimiser le programme en fonction de vos scénarios.

Prenant l’allusion fournie par aksham, je vois que la réponse est la suivante:

 #include  std::set mySet; // Insert [34 - 75): mySet.insert(boost::counting_iterator(34), boost::counting_iterator(75)); 

La raison pour laquelle vous souhaitez spécifiquement insérer des iterators pour spécifier une plage n’est pas claire.

Cependant, je pense que vous pouvez utiliser une simple boucle for pour insérer avec la complexité O (n) souhaitée.

Citant la page de cppreference sur std :: set, la complexité est la suivante:

Si N éléments sont insérés, Nlog (taille + N) en général, mais linéaire en taille + N si les éléments sont déjà sortingés selon le même critère de classement utilisé par le conteneur.

Donc, en utilisant une boucle for:

 std::set mySet; for(int i = 34; i < 75; ++i) mySet.insert(i);