Что на самом деле делает std :: includes?

Question

С стандарт, 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 on Wandbox}

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

Answer 1

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

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

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

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

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

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

Answer 2

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

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

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

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

Так что совершенно очевидно, что слова в описании includes:

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

должно быть игнорировано .Вам нужно знать a priori , что такое мультимножественные операции, что означает «включает» два мультимножества, игнорировать описание и перестраивать в своей голове то, что было очевидным намерением.

Включение мультимножества:

A включено в B если Объединение B = B.

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

Answer 3

Я полагаю, вы пытаетесь проверить, включает ли 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 подгруппой, если да, возвращает true, если не возвращает false.Также, если это не заказано, выдает ошибку: sequence not ordered.