C++ Girl
  1. C++ Girl
  3. Ensemble C ++: compter les éléments inférieurs à une valeur
Intereting Posts
Impossible de lire des entiers binarys simples à partir d’un fichier? (C ++) c ++ lecture dans un fichier texte dans le vecteur puis écriture dans un vecteur ou un tableau selon le premier mot du vecteur interne Effectuer static_assert sur tous les autres types d’un modèle Le compilateur peut-il optimiser la base vide si la classe contient un membre du type classe de base en tant que premier élément, suivi des autres membres? C ++: appel d’une fonction virtuelle pure à partir d’une fonction membre de la même classe Pourquoi sizeof (Derived4) est de 8 octets? Je pense que cela devrait être 5 octets Passer des arguments comme référence const vs référence normale Déclassement C ++ en classe dérivée basé sur une variable Puis-je utiliser std :: vector comme paramètre de modèle ou faut-il que ce soit std :: vector ? mpirun n’a pas pu trouver le fichier exécutable spécifié Placement de la définition des membres statiques de classe dans un fichier cpp – limitation technique? Définir des interfaces pour des fonctions qui n’acceptent que des fonctions C ++ – Lorsque la recompilation est requirejse Comment écrire un fichier d’en-tête C pouvant être utilisé dans des programmes C ++? Modification d’une structure de données en itérant sur celle-ci

Ensemble C ++: compter les éléments inférieurs à une valeur

En supposant que j’ai un set s STL set s et un int x , comment puis-je compter le nombre d’éléments dans s qui sont inférieurs à x ?

Je cherche une solution O(log n) (ou similaire; tout ce qui est raisonnablement meilleur que O(n) );

Je connais déjà std::distance(s.begin(), s.lower_bound(x)) , mais c’est O(n) , je crois, car les set ne sont pas à access aléatoire.

Ce dont vous avez besoin est un “arbre de statistiques de commande”. Il s’agit essentiellement d’un arbre augmenté (recherche binary) qui prend en charge l’opération supplémentaire rank(x) qui vous donne le nombre d’éléments avec une clé inférieure ou égale à l’élément x . Chapitre 14 à Cormen, Leiserson, Rivest, Stein; “Introduction aux algorithmes” devrait vous donner le contexte algorithmique.

Il existe également une mise en œuvre sur le Web .

Je ne pense pas que ce soit possible. Votre ensemble STL est une structure arborescente, la vérification de la présence d’un élément est donc tout simplement O (log n). Les nœuds de votre arborescence ne stockent la taille de leurs sous-twigs dans aucun champ (autant que je sache), de sorte que le nombre d’opérations nécessaires pour compter les nœuds ayant une propriété qui ne découle pas directement des règles utilisées pour la construction de l’arborescence ne peut pas être réduit. que le nombre de ces nœuds. Etant donné que vous ne savez pas à l’avance combien de nœuds ont des valeurs inférieures à x, la performance dans le cas le plus défavorable se produit lorsque tous les nœuds sont inférieurs à x, ce qui correspond à la complexité dans le cas le plus défavorable de O (n). Même si la valeur x était dans l’arborescence, vous avez besoin d’opérations O (log n) pour trouver ce nœud, mais vous devez ensuite visiter toutes ses descendantes gauches afin de les compter. La complexité dépend donc du nombre de nœuds correspondants qui est O ( n) dans le pire des cas. Peut-être qu’avec des données supplémentaires dans les nœuds de l’arborescence, on pourrait faire mieux que cela.

Suite à mon commentaire: en utilisant des arbres de recherche binarys rouge-noir (au lieu d’ensembles), si chaque nœud stocke le nombre de nœuds enracinés dans ce nœud (mis à jour chaque fois que vous insérez / supprimez un nœud), vous pouvez accéder à ” nombre de nœuds plus / moins que X “statistiques assez rapidement.