2

std::includes is documented as

Returns true if every element from the sorted range [first2, last2) is found within the sorted range [first1, last1). Also returns true if [first2, last2) is empty.

The emphasis is mine.

Is there an equivalent C++ algorithm that reproduces this functionality on an unsorted range from a container, or do I have to go back to implementing this myself via loops?

dlanod
  • 8,664
  • 8
  • 54
  • 96
  • 1
    sort the range first? – Bryan Chen Sep 08 '15 at 23:38
  • One of the ranges is sorted on another property other than what I want to use `includes` on, so I'd need to create a second container just in order to sort it, either temporarily or have to maintain alignment of the contents of the two. – dlanod Sep 08 '15 at 23:41
  • 2
    I guess you can write `std::all_of(first2, last2, [&](const auto& e) { return std::find(first1, last1, e) != last1; })`, but it's O(MN). – T.C. Sep 08 '15 at 23:46

1 Answers1

5

If you sort the range first, the sort will run in O(n log n) time and the search will run in O(m+n) time. If you try to do this naïvely on an unsorted range, it will run in O(m·n) time. You’re usually better off just sorting.

You can, however, search an unsorted range for a substring efficiently. That’s the closest thing I can think of to what you’re asking for.

Davislor
  • 14,674
  • 2
  • 34
  • 49
  • 1
    Which one is better rather depends on the relative size of `m` and `n`, no? – T.C. Sep 08 '15 at 23:47
  • 2
    Sure, but if you’re searching for a single element, you can just use `std::find`, and if *m* is small, you can `std::find` each one and break as soon as one isn’t found. So that’s how you can do it on an unsorted range in O(*mn*) time with STL if that’s better than O(*n* log *n*). (It might not be as efficient in real-world use due to locality of reference.) – Davislor Sep 09 '15 at 00:29
  • 1
    But I added a weasel word. – Davislor Sep 09 '15 at 00:34