Что на самом деле делает std :: includes?
Из стандарт,std::includes:
Returns:
trueif[first2, last2)is empty or if every element in the range[first2, last2)is contained in the range[first1, last1). Returnsfalseotherwise.
Note: as this is under [alg.set.operations], the ranges must be sorted
Если принять это буквально, если мы допустим 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';
}
Это удивительно. Я проверил это как с libstdC++, так и с libC++, но мне кажется маловероятным, что это будет ошибкой в реализации стандартной библиотеки, учитывая, что это часть библиотеки алгоритмов. Если это не тот алгоритм, который должен работать std::includes, то что?
Это больше проверка на R2 ⊆ R1
@Mgetz Я понимаю порядок параметров. Но, судя по буквальной формулировке в стандарте, этот (псевдокод) std::includes({1}, {1, 1, 1}) должен возвращать истину согласно моей интерпретации.
@Mgetz, но каждый элемент {1,1,1} содержится в {1}, поскольку все они едины. Буквальное прочтение стандарта допускает обе интерпретации ИМХО.
@NathanOliver рабочая формулировка - каждый элемент, что означает, что должны быть представлены повторяющиеся элементы, это разница между наборами и списками. Стандарт использует списки, а не наборы.
@Mgetz Здесь не говорится что-то вроде «каждый элемент в R2 должен иметь соответствующий элемент в R1», но «каждый элемент в R2 должен содержаться в R1»
@Justin Я согласен, что здесь есть дефект, стандарт должен быть четким в отношении списков и наборов. Но я думаю, что реализация соответствует требованиям, поскольку сортировка подразумевает списки, которые подразумевают, что положение и повторение имеют значение. TL; DR; Кейси прав и мы потратили на это слишком много времени
@Mgetz Реализация соответствует требованиям, если вы прочитали весь раздел. Смотрите мой ответ.
не уверен, почему в теги был добавлен "мультимножество", этот вопрос не касается std::multiset
@ M.M Затем прочтите описание этого тега.
«Семантика операций над множеством обобщается на мультимножества стандартным способом путем определения set_union (), чтобы содержать максимальное количество вхождений каждого элемента, set_intersection (), чтобы содержать минимум, и так далее». Довольно понятно ИМХО. Все алгоритмы в разделе описаны в терминах заданных операций; для поведения на мультимножествах нужен предыдущий абзац.
Почему люди настаивают, что это не проблема с мультимножеством, когда речь идет о мультимножествах на 100%?
@JHBonarius Включение "R2 ⊆ R1", как определено для мультимножество
Ответы 3
Я полагаю, вы пытаетесь проверить, включает ли ab в вашем примере, 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), он проверяет, владеет ли R2R1 в качестве подгруппы, если да, возвращает true, если нет, возвращает false. Также, если он не заказан, выдает ошибку: sequence not ordered.
Сначала я так думал, но после (внешнего) обсуждения с Джастином стало довольно ясно, что он действительно имел в виду, что «каждый элемент в R2» (то есть: 1) находится в R1. Я не могу сказать, что это неправильно, буквально читая стандарт, но цель алгоритма не в этом.
О, теперь я понял ... моя проблема. Английский не является моим сильным языком, иногда я упускаю главное.
«Каждый элемент из R2» - я понимаю это как «все три единицы», а не просто «1».
@ TuğberkKaanDuman Я думаю, что OP не спрашивает, какой алгоритм на самом деле делает, но если то, что он делает, это то, что стандарт говорит, что он должен делать.
В заголовке написано, что What does std::includes actually do?. Я наблюдал и записал свой опыт. Не всякая документация идеальна, они тоже написаны людьми. Думаю, теперь будет лучше. @Slava
@jrok ""все три единицы"," Но тогда вы не можете различать равные значения. Это действительно сравнение количества одинаковых элементов.
Я разместил это в Slack cpplang и Кейси Картер ответил:
The description of the algorithm in the standard is defective. The intent is to determine [if] every element in the needle appears in order in the haystack.
[The algorithm it actually performs is:] "Returns true if the intersection of sorted sequences R1 and R2 is equal to R2"
Или, если мы уверены, что знаем значение подпоследовательность:
Returns: true if and only if [first2, last2) is a subsequence of [first1, last1)
Как всегда при чтении стандарта, ты должен прочитать неписаные слова.
Сосредоточьтесь на намерении, а не только на письме. (Формулировки стандарта часто оказывались расплывчатыми, неполными, ссылающимися на самих себя или противоречивыми.)
Прочтите введение в раздел «28.7.6 Установить операции над сортированными структурами [alg.set.operations]»:
This subclause defines all the basic set operations on sorted structures. They also work with multisets containing multiple copies of equivalent elements. The semantics of the set operations are generalized to multisets in a standard way by defining set_union() to contain the maximum number of occurrences of every element, set_intersection() to contain the minimum, and so on.
Так что совершенно ясно, что слова в описании includes:
Returns: true if [first2, last2) is empty or if every element in the range [first2, last2) is contained in the range [first1, last1). Returns false otherwise.
должно быть игнорируется. Вам нужно знать априори, что такое операции с мультимножествами, что «включает» означает для двух мультимножеств, игнорировать описание и перестраивать в своей голове то, что было намерением очевидный.
Включение мультинабора:
A входит в B если только A union B = B.
Это верно для наборов или мультимножеств.
@ n.m. кто за это голосует? 90% из них говорят «Игнорируйте стандарт» в саркастической и чрезмерно раздутой манере. Затем он отвечает на вопрос в последних 3 строках. ИМО это следует удалить, так как это сбивает с толку любого, кто понимает это буквально
@ M.M Как вы думаете, чем занимаются авторы компиляторов? Они делают то, что правильно, а НЕ то, что говорит стандарт. Вы, конечно, хотите удалить, это не соответствует вашему мировоззрению (где std нельзя критиковать?).
Похоже, кандидат на отчет о дефектах. Я интерпретирую каждый элемент в диапазоне [first2, last2) содержится в диапазоне [first1, last1) как означающий, что вам понадобится
{1,1,1}, чтобы соответствовать{1,1,1}, но по тому, как это сформулировано, я понимаю, почему вы могли ожидать, что ваш случай сработает.