c++ - ¿Qué hace realmente std:: includes?

language-lawyer c++17

Question

Del estándar, std::includes :

Devuelve: true si [first2, last2) está vacío o si cada elemento en el rango [first2, last2) está contenido en el rango [first1, last1) . De lo contrario devuelve false .

^{Nota: como se encuentra en [alg.set.operations] , los rangos deben ordenarse}

Tomando esto literalmente, si permitimos que R1=[first1, last1) y R2=[first2, last2) , esto está evaluando:

∀a∈R2 a∈R1

Sin embargo, esto no es lo que realmente se está evaluando. Para R1={1} y R2={1,1,1} , std::includes(R1, R2) devuelve falso:

#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 vivo en Wandbox}

Esto es sorprendente. Lo verifiqué con libstdc ++ y libc ++, pero me parece poco probable que esto sea un error en la implementación de la biblioteca estándar, considerando que es parte de la biblioteca de algoritmos. Si este no es el algoritmo que se supone que std::includes debe ejecutar, ¿qué es?

Answer 1

Como siempre al leer el estándar, debe leer las palabras no escritas .

Céntrate en la intención no solo en la letra. (La redacción de la norma a menudo se encontró que era vaga, incompleta, autorreferencial o contradictoria).

Lea la introducción de la sección " 28.7.6 Establecer operaciones en estructuras ordenadas [alg.set.operations] ":

Esta subcláusula define todas las operaciones de conjunto básico en estructuras ordenadas. También funcionan con conjuntos múltiples que contienen copias múltiples de elementos equivalentes. La semántica de las operaciones de set se generalizan a multisets de manera estándar al definir set_union () para que contenga el número máximo de ocurrencias de cada elemento, set_intersection () para contener el mínimo, y así sucesivamente .

Así que está perfectamente claro que las palabras en la descripción de includes :

Devuelve: verdadero si [first2, last2) está vacío o si cada elemento en el rango [first2, last2) está contenido en el rango [first1, last1). De lo contrario devuelve falso.

debe ser ignorado Debe saber a priori qué son las operaciones multiset, lo que "incluye" significa para dos multisets, ignorar la descripción y reconstruir en su cabeza cuál era la intención obvia .

Inclusión multiset:

A se incluye en B sif A unión B = B.

Esto es cierto para conjuntos o multisets.

Answer 2

Creo que estás tratando de verificar si a incluye b en tu ejemplo, a no incluye b pero b sí incluye a . Si intercambia b y a se devolverá verdadero, ya que a se incluye en b .

Espero no perderme algo obvio.

#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'';
}

Lo que he entendido al jugar con el algoritmo es que, cuando escribe includes(R2, R1) , comprueba si R2 posee R1 como subgrupo, si sí devuelve true si no devuelve false . Además, si no está ordenado arroja un error: sequence not ordered .

Answer 3

Publiqué esto en el cpplang slack, y Casey Carter respondió :

La descripción del algoritmo en el estándar es defectuosa. La intención es determinar [si] todos los elementos de la aguja aparecen en orden en el pajar.

[El algoritmo que realmente realiza es:] "Devuelve verdadero si la intersección de las secuencias ordenadas R1 y R2 es igual a R2"

O, si nos aseguramos de que estamos seguros del significado de la subsequence :

Devuelve: verdadero si y solo si [first2, last2) es una subsecuencia de [first1, last1)

^{enlace al mensaje de Casey Carter}