N3671
Revision of: N3607
2013-04-19
Mike Spertus, Symantec
mike_spertus@symantec.com
Attila Pall, Symantec
Attila_Pall@symantec.com

Making non-modifying sequence operations more robust: Revision 2

Overview

We propose adding overloads for std::equal, std::mismatch, and std::is_permutation to accept two ranges. When using these overloads, the caller does not need to separately check that the two ranges are of the same length.

We illustrate this using std::equal. For example: vector<int> v1 = { 1, 4 9 }; vector<int> v2 = { 1, 4, 9, 16, 25, 36, 49 }; vector<int> v3 = { 1, 2, 3, 4 }; assert(!equal(v1.begin(), v1.end(), v2.begin(), v2.end());

These overloads provide three benefits.

Since one almost always needs to check that the two sequences are of the same length, having a single function that comprehensively checks sequences for equality is clearer and less brittle.
If one neglects to check that the two ranges are the same length, the existing forms of equal will appear to function correctly most of the time, even on sequences of different length. For example, in the following snippets, assume the programmer intended to compare the entire vectors: equal(v1.begin(), v1.end(), v3.begin()); // Gives desired answer by luck but of course occasionally give an incorrect answer equal(v1.begin(), v1.end(), v2.begin()); // Oops! Returns true for unequal sequences or even crash equal(v2.begin(), v2.end(), v1.begin()) // Oops! Undefined behavior would exhibit undefined behavior above), the majority of the time, it will appear to function correctly.

As a result, programs are likely to pass systems testing and QA but intermittently exhibit incorrect errors in deployment. At our company, code that had run apparently correctly for years, started crashing our cloud servers as a result of this error. The impact and cost to fix this problem was obviously far higher than if equal checked for full equality of sequences (including length)
If the sequences do not satisfy the requirements of a random iterator (§24.2.7 [random.access.iterator]), then checking that the sequences are of the same length is much more efficient to do while comparing elements for equality.

Note that if random access iterators are passed to the new overloads of equal equal or is_permutation, they will compare the length of sequences up front to quickly reject unequal length sequences. Even though they don't fully replace the existing overloads, we feel having overloads that properly handle sequences that are not known to be of the same length are well worth having.

While we focused on the case of equal in the text above, the same considerations apply to is_permutation, and mismatch, which are the other non-modifying sequence operators that work on pairs of iterators but do not allow passing the end to the second range, so we include them in our proposal as well.

Wording

In the synopsis of §25.1 [algorithms.general], make the following changes:

template<class InputIterator, class Predicate>
  typename iterator_traits<InputIterator>::difference_type
    count_if(InputIterator first, InputIterator last, Predicate pred);
		
template<class InputIterator1, class InputIterator2>
  pair<InputIterator1, InputIterator2>
    mismatch(InputIterator1 first1, InputIterator1 last1,
             InputIterator2 first2);
						 
template
 <class InputIterator1, class InputIterator2, class BinaryPredicate>
  pair<InputIterator1, InputIterator2>
    mismatch(InputIterator1 first1, InputIterator1 last1,
             InputIterator2 first2, BinaryPredicate pred);

template<class InputIterator1, class InputIterator2>
  pair<InputIterator1, InputIterator2>
    mismatch(InputIterator1 first1, InputIterator1 last1,
             InputIterator2 first2, InputIterator2 last2);
						 
template
 <class InputIterator1, class InputIterator2, class BinaryPredicate>
  pair<InputIterator1, InputIterator2>
    mismatch(InputIterator1 first1, InputIterator1 last1,
             InputIterator2 first2, InputIterator2 last2,
             BinaryPredicate pred);

template<class InputIterator1, class InputIterator2>
  bool equal(InputIterator1 first1, InputIterator1 last1,
             InputIterator2 first2);

template
 <class InputIterator1, class InputIterator2, class BinaryPredicate>
  bool equal(InputIterator1 first1, InputIterator1 last1,
             InputIterator2 first2, BinaryPredicate pred);

template<class InputIterator1, class InputIterator2>
  bool equal(InputIterator1 first1, InputIterator1 last1,
             InputIterator2 first2, InputIterator2 last2);

template
 <class InputIterator1, class InputIterator2, class BinaryPredicate>
  bool equal(InputIterator1 first1, InputIterator1 last1,
             InputIterator2 first2, InputIterator2 last2,
             BinaryPredicate pred);

template<class ForwardIterator1, class ForwardIterator2>
  bool is_permutation(ForwardIterator1 first1, ForwardIterator1 last1,
                      ForwardIterator2 first2);
											
template<class ForwardIterator1, class ForwardIterator2,
                    class BinaryPredicate>
  bool is_permutation(ForwardIterator1 first1, ForwardIterator1 last1,
                      ForwardIterator2 first2, BinaryPredicate pred);

template<class ForwardIterator1, class ForwardIterator2>
  bool is_permutation(ForwardIterator1 first1, ForwardIterator1 last1,
                      ForwardIterator2 first2, ForwardIterator2 last2);

template<class ForwardIterator1, class ForwardIterator2,
                    class BinaryPredicate>
  bool is_permutation(ForwardIterator1 first1, ForwardIterator1 last1,
                      ForwardIterator2 first2, ForwardIterator2 last2,
                      BinaryPredicate pred);

template<class ForwardIterator1, class ForwardIterator2>
  ForwardIterator1 search(
    ForwardIterator1 first1, ForwardIterator1 last1,
    ForwardIterator2 first2, ForwardIterator2 last2);

Modify §25.2.10 [mismatch] as follows

template<class InputIterator1, class InputIterator2>
  pair<InputIterator1, InputIterator2>
    mismatch(InputIterator1 first1, InputIterator1 last1,
             InputIterator2 first2);
						 
template
 <class InputIterator1, class InputIterator2, class BinaryPredicate>
  pair<InputIterator1, InputIterator2>
    mismatch(InputIterator1 first1, InputIterator1 last1,
             InputIterator2 first2, BinaryPredicate pred);

template<class InputIterator1, class InputIterator2>
  pair<InputIterator1, InputIterator2>
    mismatch(InputIterator1 first1, InputIterator1 last1,
             InputIterator2 first2, InputIterator2 last2);
						 
template
 <class InputIterator1, class InputIterator2, class BinaryPredicate>
  pair<InputIterator1, InputIterator2>
    mismatch(InputIterator1 first1, InputIterator1 last1,
             InputIterator2 first2, InputIterator2 last2,
             BinaryPredicate pred);
Remarks: If last2 was not given in the argument list, it denotes first2 + (last1 - first1) below.

Returns: A pair of iterators i and j such that j == first2 + (i - first1) and i is the first iterator in the range [first1,last1) for which the following corresponding conditions hold:
j is in the range [first2, last2).
!(*i == *(first2 + (i - first1)))
pred(*i, *(first2 + (i - first1))) == false
Returns the pair last1 first1 + min(last1 - first1, last2 - first2) and first2 + (last1 - first1) first2 + min(last1 - first1, last2 - first2) if such an iterator i is not found.

Modify §25.2.10 [alg.equal] as follows:

template<class InputIterator1, class InputIterator2>
  bool equal(InputIterator1 first1, InputIterator1 last1,
             InputIterator2 first2);

template
 <class InputIterator1, class InputIterator2, class BinaryPredicate>
  bool equal(InputIterator1 first1, InputIterator1 last1,
             InputIterator2 first2, BinaryPredicate pred);

template<class InputIterator1, class InputIterator2>
  bool equal(InputIterator1 first1, InputIterator1 last1,
             InputIterator2 first2, InputIterator2 last2);

template<class InputIterator1, class InputIterator2,
           class BinaryPredicate>
  bool equal(InputIterator1 first1, InputIterator1 last1,
             InputIterator2 first2, InputIterator2 last2,
             BinaryPredicate pred);
Remarks: If last2 was not given in the argument list, it denotes first2 + (last1 - first1) below.

Returns: If last1 - first1 != last2 - first2, return false. Otherwise return true if for every iterator i in the range [first1,last1) the following corresponding conditions hold: *i == *(first2 + (i - first1)), pred(*i, *(first2 + (i - first1))) != false. Otherwise, returns false.

Complexity: No applications of the corresponding predicate if InputIterator1 and InputIterator2 meet the requirements of random access iterators and last1 - first1 != last2 - first2. Otherwise, Aat most last1 - first1 min(last1 - first1, last2 - first2) applications of the corresponding predicate.

Modify §25.2.12 [alg.is_permutation] as follows:

template<class ForwardIterator1, class ForwardIterator2>
  bool is_permutation(ForwardIterator1 first1, ForwardIterator1 last1,
                      ForwardIterator2 first2);
template<class ForwardIterator1, class ForwardIterator2,
                 class BinaryPredicate>
  bool is_permutation(ForwardIterator1 first1, ForwardIterator1 last1,
                      ForwardIterator2 first2, BinaryPredicate pred);
template<class ForwardIterator1, class ForwardIterator2>
  bool is_permutation(ForwardIterator1 first1, ForwardIterator1 last1,
                      ForwardIterator2 first2, ForwardIterator2 last2);
template<class ForwardIterator1, class ForwardIterator2,
                 class BinaryPredicate>
  bool is_permutation(ForwardIterator1 first1, ForwardIterator1 last1,
                      ForwardIterator2 first2, ForwardIterator2 last2,
                      BinaryPredicate pred);
Requires: ForwardIterator1 and ForwardIterator2 shall have the same value type. The comparison function shall be an equivalence relation.

Remarks: If last2 was not given in the argument list, it denotes first2 + (last1 - first1) below.

Returns: If last1 - first1 != last2 - first2, return false. Otherwise return true if there exists a permutation of the elements in the range [first2,first2 + (last1 - first1)), beginning with ForwardIterator2 begin, such that equal(first1, last1, begin) returns true or equal(first1, last1, begin, pred) returns true; otherwise, returns false.

Complexity: No applications of the corresponding predicate if ForwardIterator1 and ForwardIterator2 meet the requirements of random access iterators and last1 - first1 != last2 - first2. Otherwise, eExactly last1 - first1 applications of the corresponding predicate if equal(first1, last1, first2, last2) would return true if pred was not given in the argument list or equal(first1, last1, first2, last2, pred) would return true if pred was given in the argument list; otherwise, at worst O(N²), where N has the value last1 - first1.