Que fait std :: includes?

Question

À partir de la norme, std::includes:

Retourne: true si [first2, last2) est vide ou si chaque élément de la gamme [first2, last2) est contenue dans l'intervalle [first1, last1). Les retours false sinon.

^{Remarque: comme c'est en vertu de [alg.ensemble.opérations], les plages doivent être triés}

La prise de ce littéralement, si nous les laissons R1=[first1, last1) et R2=[first2, last2), ce qui est de l'évaluation:

∀a∈R2 a∈R1

Cependant, ce n'est pas ce qui est réellement évalué. Pour R1={1} et R2={1,1,1}, std::includes(R1, R2) retourne false:

#include <algorithm>
#include <iomanip>
#include <iostream>
#include <vector>

int main() {
    std::vector<int> a({1});
    std::vector<int> b({1,1,1});

    // Outputs 'false'
    std::cout << std::boolalpha
        << std::includes(a.begin(), a.end(), b.begin(), b.end()) << '\n';
}

^{En direct sur Wandbox}

Ce qui est surprenant. J'ai vérifié avec les deux libstdc++ et de la libc++, mais il me semble improbable que ce serait un bug dans la bibliothèque standard de mise en œuvre, considérant que cela fait partie des algorithmes de la bibliothèque. Si ce n'est pas l'algorithme qui std::includes est censé fonctionner, c'est quoi?

Answer 1

J'ai posté ceci dans le cpplang mou, et Casey Carter a répondu:

La description de l'algorithme dans la norme est défectueux. L'objectif est de déterminer [si] chaque élément de l'aiguille apparaît dans l'ordre dans la botte de foin.

[L'algorithme effectue en réalité est:] "Renvoie true si l'intersection des séquences triées R1 et R2 est égal à R2"

Ou, si nous assurer que nous sommes certains de la signification de la sous-suite:

Retourne: true si et seulement si [premier2, last2) est une sous-suite de [first1, last1)

^{lien vers Casey Carter du message}

Answer 2

Je crois que vous êtes en essayant de vérifier si a inclut b dans votre exemple, a n'inclut pas l' b mais b ne comprennent a. Si vous permutez b et a il renverra true, depuis a est inclus dans b.

J'espère que je ne suis pas rater quelque chose d'évident.

#include <algorithm>
#include <iostream>
#include <vector>

int main() {
    std::vector<int> a({1});
    std::vector<int> b({1,1,1});

    // Outputs 'true'
    std::cout << std::boolalpha
        << std::includes(b.begin(), b.end(), a.begin(), a.end()) << '\n';
}

Ce que j'ai compris, en jouant autour avec l'algorithme est, lorsque vous tapez includes(R2, R1) il vérifie si R2 détient R1 comme un sous-groupe, si oui retourne true si pas de retours false. Aussi, si ce n'est pas commandé renvoie une erreur: sequence not ordered.

Answer 3

Comme toujours lors de la lecture de la norme, vous devez lire le non écrite des mots.

Se concentrer sur l'intention non seulement de la lettre. (Le libellé de la norme est souvent imprécise, incomplète, auto-référentielle, ou contradictoires.)

Lire l'introduction de l'article "28.7.6 Ensemble des opérations sur triés structures [alg.ensemble.opérations]" :

Ce paragraphe définit tous les réglages de base opérations sur triés les structures. Ils ont également travailler avec des multisets contenant de multiples copies des éléments équivalents. La sémantique de l'ensemble des opérations sont généralisée à multisets, de manière standard, en définissant set_union() pour contenir le nombre maximum d'occurrences de chaque élément, set_intersection() pour contenir le minimum, et ainsi de suite.

Il est donc parfaitement clair que les mots dans la description de l' includes:

Retourne: true si [premier2, last2) est vide ou si chaque élément de la gamme [premier2, last2) est contenue dans l'intervalle [first1, last1). Renvoie false dans le cas contraire.

doit être ignoré. Vous avez besoin de savoir a priori ce que multiset opérations sont, ce qui "comprend" désigne, pour deux multisets, ignorer la description et de reconstruction dans votre tête ce qui était l' évidente intention.

Multiset inclusion:

A est inclus dans B ssi A union B = B.

Cela est vrai pour des ensembles ou des multisets.