Что вообще делает std :: include?

Из стандарта std::includes:

Возвращает: true если [first2, last2) пуст или каждый элемент в диапазоне [first2, last2) содержится в диапазоне [first1, last1). Возвращает false противном случае.

^{Примечание: поскольку это находится под [alg.set.operations], диапазоны должны быть отсортированы}

Принимая это буквально, если мы допустим R1=[first1, last1) и R2=[first2, last2), это оценивает:

∀a∈R2 a∈R1

Однако это не то, что на самом деле оценивается. Для R1={1} и R2={1,1,1}, std::includes(R1, R2) возвращает 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';
}

^{Live на Wandbox}

Это удивительно. Я проверил его как с libstdc++, так и с libc++, но мне кажется маловероятным, что это будет ошибкой в реализации стандартной библиотеки, считая его частью библиотеки алгоритмов. Если это не алгоритм, который должен запускать std::includes, что это такое?

Ответы

Ответ 1

Я отправил это в cpplang slack, и Кейси Картер ответил:

Описание алгоритма в стандарте является дефектным. Цель состоит в том, чтобы определить [если] каждый элемент в игле появляется в порядке в стоге сена.

[Алгоритм, который он фактически выполняет:] "Возвращает true, если пересечение отсортированных последовательностей R1 и R2 равно R2"

Или, если мы гарантируем, что мы уверены в значении подпоследовательности:

Возвращает: истинно тогда и только тогда, когда [first2, last2] является подпоследовательностью [first1, last1)

^{ссылка на сообщение Кейси Картера}

Ответ 2

Я считаю, что вы пытаетесь проверить, если включает a b в вашем примере, не включает в себя a b а b действительно включает. a Если вы поменяете b и a он вернет true, так как a включен в b.

Надеюсь, я не пропущу что-то очевидное.

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

То, что я понял, играя с алгоритмом, заключается в том, что когда вы вводите includes(R2, R1) он проверяет, владеет ли R2 собственностью R1 в качестве подгруппы, если yes возвращает true если не возвращает false. Также, если он не заказал ошибку, то sequence not ordered.

Ответ 3

Как всегда при чтении стандарта, вы должны прочитать неписаные слова.

Сосредоточьтесь на намерении не только на букве. (Формулировка стандарта часто считалась неопределенной, неполной, самореферентной или противоречивой.)

Прочтите введение раздела " 28.7.6. Установите операции над отсортированными структурами [alg.set.operations] ":

В этом подпункте определяются все операции базового набора в отсортированных структурах. Они также работают с мультимножествами, содержащими несколько копий эквивалентных элементов. Семантика заданных операций обобщается на мультимножества стандартным образом, определяя set_union(), чтобы содержать максимальное количество вхождений каждого элемента, set_intersection(), чтобы содержать минимум, и так далее.

Поэтому совершенно ясно, что слова в описании includes:

Возвращает: true, если [first2, last2] пуст или каждый элемент в диапазоне [first2, last2] содержится в диапазоне [first1, last1]. Возвращает false в противном случае.

должны быть проигнорированы. Вам нужно знать априори, какие мультимножества выполняются, что означает "включает" средства для двух мультимножеств, игнорировать описание и перестраивать в голове, что было очевидным намерением.

Множественное включение:

A входит в B, если объединение A B = B.

Это справедливо для множеств или мультимножеств.