Recently, the question was about this algorithm. By standard, it accepts sorted sequences, but I always gave the correct result for unsorted sets. For example:

std::vector<int> a{1, 2, 5, 3, 11, 23, 12, 6}; std::vector<int> b{5, 3, 11}; if (std::includes(a.begin(), a.end(), b.begin(), b.end())) cout << b.back(); // вывод 11

And, just in case, the reference to the standard: https://ru.cppreference.com/w/cpp/algorithm/includes I think it’s just that the algorithm works faster for sorted sets and does not sort the unsorted ones (or doesn’t sorting be necessary?). I have not figured it out yet, I would like to receive help from you (what is your answer? ...) Simply, it is purely logical, the sorting is not needed at all ...

  • sorting required. Just in this case, lucky that the significant part (up to 23 was sorted) (contained a segment of 5-3-11 in that order and then 5 were numbers less) - pavel
  • The question is related to this question - cpp questions
  • @cpp questions, I have already mentioned what is connected in the question. Do not hesitate to repeat - AR Hovsepyan
  • @ARHovsepyan so that the system understands what is connected, you need to give a link to it. Then on the right in "Related" will appear. Add a link to the question and I will delete if you do not want - cpp questions

2 answers 2

Your sequence is too good ... Try on

 std::vector<int> a{1, 2, 5, 3, 23, 11, 12, 6};

Take a look at the approximate implementation of the algorithm at the link you specified, and everything should become clear why this is so.

According to the laws of logic, falsehood and truth can flow out of false assumptions, so the correct result still does not mean that it will always be :( But at least one false one shows that the initial assumptions are false.

  • I'm already confused, then I'll take a look (smoke break) - AR Hovsepyan

but I always gave the correct result for unsorted sets

You are making something up. The behavior of the std::includes algorithm on unordered sequences is undefined, i.e. it does not work at all on unordered sequences. Your "I always gave the correct result" - it's just an accident (which, moreover, is hard to believe).

Simple, purely logical, sorting is not needed here at all.

By no means. The standard function std::includes and the rest of the functions of this group ( std::set_difference , std::set_union , etc.) were used to implement set-theoretic operations through a textbook algorithm for synchronous passage through two sorted sequences. Without sequence ordering, these algorithms are meaningless.

  • one
    [this is just an accident] I myself knew a person who at the time of MS DOS created system diskettes with the copy command, not with the sys command. And everything worked for him. And he was piously sure that this was the way to do it. And the solution was simple - he took the floppy disks on which the system once was, deleted all the files and copied io.sys, msdos.sys and command.com, which fell to the right place at the beginning of the volume. boot sector was registered, so everything started to work. That kind of happiness happens with people. - pepsicoca1
  • @ pepsicoca1, my case is connected with the fact that I write programs purely for the sake of curiosity, and the algorithm itself is not often used. But I do not consider such a coincidence luck, but quite the opposite. If I were to get the wrong result, then there would be no mistaken opinion ... - AR Hovsepyan
  • @AnT, what do you think, what interest should I pursue to invent? Happened, used, did not begin to understand, and the erroneous opinion turned into conviction. Thanks for the help and prompted. - AR Hovsepyan