¿Qué hace realmente std::includes?

Question

¿Qué hace realmente std::includes?

De el estándar, std::includes:

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

^{Nota: como esto está bajo [alg.establecer.operaciones], los rangos deben ser ordenados}

Tomando esto literalmente, si dejamos R1=[first1, last1) y R2=[first2, last2), esto es evaluar: {[17]]}

∀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 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 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, teniendo en cuenta que es parte de la biblioteca de algoritmos. Si este no es el algoritmo que std::includes se supone que debe ejecutarse, ¿qué es?

30

c++language-lawyer c++17 stl-algorithm

Author: Justin, 2018-05-24

Source

3 answers

Creo que está tratando de comprobar si a incluye b en el ejemplo, a no incluyen b pero b incluye a. Si usted intercambia b y a devolverá true, ya que a está incluido en b.

Espero que no me esté perdiendo 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, cuando escribe includes(R2, R1) comprueba si R2 posee R1 como un subgrupo, si sí devuelve true si no devuelve false. También si no está ordenado arroja un error: sequence not ordered.

3

Author: Tuğberk Kaan Duman,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2018-05-24 19:00:01

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

Enfócate 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.establecer.operaciones]" :

Esta subcláusula define todas las operaciones básicas de conjunto en ordenadas estructura. También funcionan con múltiples conjuntos que contengan varias copias de elementos equivalentes. La semántica de las operaciones del conjunto son generalized to multiset in a standard way by defining set_union () to contiene 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: true si [first2, last2) está vacío o si cada elemento el el rango [first2, last2) está contenido en el rango [first1, last1). Devuelve false de lo contrario.

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

Inclusión multiset:

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

Esto es cierto para conjuntos o multisets.

-1

Author: curiousguy,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2018-06-28 03:01:23

score 29 · Accepted Answer

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

La descripción del algoritmo en el estándar es defectuosa. La intención es determinar [si] cada elemento de la aguja aparece en orden en el pajar.

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

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

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

^{enlace al mensaje de Casey Carter}