Thread: Help with <algorithm> functions with 2 ranges

I read the possible implementation of is_permutation from <algorithm> and got a bit confused about the handling of the second range.

Code:

template <class InputIterator1, class InputIterator2>
  bool is_permutation (InputIterator1 first1, InputIterator1 last1,
                       InputIterator2 first2)
{
  std::tie (first1,first2) = std::mismatch (first1,last1,first2);
  if (first1==last1) return true;
  InputIterator2 last2 = first2; std::advance (last2,std::distance(first1,last1));
  for (InputIterator1 it1=first1; it1!=last1; ++it1) {
    if (std::find(first1,it1,*it1)==it1) {
      auto n = std::count (first2,last2,*it1);
      if (n==0 || std::count (it1,last1,*it1)!=n) return false;
    }
  }
  return true;
}

is_permuation only takes in range2.begin() and then advance the begin iter by the length of range 1. So if range 1 is longer than range 2, the advance will calculate the last2 way beyond where range.end() should be.

How come the don't take range2.end() as an argument?

When you use these function in your work, have you noticed any bug caused by this?

is_permuation

Returns true if there exists a permutation of the elements in the range [first1, last1) that makes that range equal to the range [first2,last2), where last2 denotes first2 + (last1 - first1) if it was not given.

EDIT: In other words, it is assumed that the 2nd sequence has the same length as the first.

Originally Posted by antred

is_permuation



EDIT: In other words, it is assumed that the 2nd sequence has the same length as the first.

So it's really not safe to use when the lengths are mismatched?

Originally Posted by nimitzhunter

So it's really not safe to use when the lengths are mismatched?

It's not safe to use if |Range2| < |Range1|. But as I understand it, it makes no sense to use it if |Range2| != |Range1| because there can exist no permutation if that is the case.

How come the don't take range2.end() as an argument?

O_o

Bug. (That is, the missing functions are considered a bug in the standard.) The functions you are asking about have been tagged for a future version of the standard.

When you use these function in your work, have you noticed any bug caused by this?

If you use them incorrectly, the bug will be in your code.

But as I understand it, it makes no sense to use it if |Range2| != |Range1| because there can exist no permutation if that is the case.

That is not the least bit relevant.

If you have two--four iterators--ranges, you would be required to write sentry code to correctly use the interface. The missing interfaces allow you to just ask the question making the code, for the client developer, more clearly self-documenting thanks to being simpler.

The missing interfaces also bring parity with other standard interfaces.

If anyone wants, you can easily wrap a bit of forwarding code behind an optionally compiled block of code so you can start using the missing functions.

[Edit]
The code below uses my semantics because I'm used to those semantics.

The standard semantics for `is_permutation' is more inline with `contains_leading_permutation' or something.

To get standard behavior, you'd need to get the minimum distance and accordingly adjust the range limits.
[/Edit]

Soma

Code:

#include <algorithm>
#include <iomanip>
#include <iostream>
#include <vector>

namespace shim
{
    using namespace std;
    template
    <
        typename FIterator1
      , typename FIterator2
    >
    bool is_permutation
    (
        FIterator1 fOrigin1
      , FIterator1 fTerminus1
      , FIterator2 fOrigin2
      , FIterator2 fTerminus2
    )
    {
        return((distance(fOrigin1, fTerminus1) == distance(fOrigin2, fTerminus2)) ? (is_permutation(fOrigin1, fTerminus1, fOrigin2)) : (false));
    }
    template
    <
        typename FIterator1
      , typename FIterator2
      , typename FPredicate
    >
    bool is_permutation
    (
        FIterator1 fOrigin1
      , FIterator1 fTerminus1
      , FIterator2 fOrigin2
      , FIterator2 fTerminus2
      , FPredicate fPredicate
    )
    {
        return((distance(fOrigin1, fTerminus1) == distance(fOrigin2, fTerminus2)) ? (is_permutation(fOrigin1, fTerminus1, fOrigin2, fPredicate)) : (false));
    }
}

int main()
{
    std::vector<int> s1{1,2,3,4,5};
    std::vector<int> s2{3,5,4,1,2};
    std::vector<int> s3{3,5,4,1};
    std::vector<int> s4{3,5,4,1,6};
    std::cout << std::boolalpha << shim::is_permutation(s1.begin(), s1.end(), s2.begin(), s2.end()) << '\n';
    std::cout << std::boolalpha << shim::is_permutation(s1.begin(), s1.end(), s3.begin(), s3.end()) << '\n';
    std::cout << std::boolalpha << shim::is_permutation(s1.begin(), s1.end(), s4.begin(), s4.end()) << '\n';
    return(0);
}