N3607
2013-03-15
Mike Spertus, Symantec
[email protected]
Attila Pall, Symantec
[email protected]

Making non-modifying sequence operations more robust

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: equal(v1.begin(), v1.end(), v3.begin()); // Gives correct 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 we do not require equal to compare the length of sequences up front if it is passed random access iterators, so programmers comparing sequences of random access iterators in very performance intensive code might still prefer the current overloads, which are of course retained (Of course, very hot code using forward iterators would prefer the new overloads). 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);
[Note: If last2 was not given in the argument list, it denotes first2 + (last1 - first1) below.
—end note]
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);
[Note: If last2 was not given in the argument list, it denotes first2 + (last1 - first1) below.
—end note]
Returns: true if distance(first1, last1) == distance(first2, last2) and 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: At 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.

Returns: false in the forms accepting last2 if distance(first1, last1) = distance(first2, last2). Otherwise, 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: Exactly distance(first1, last1) applications of the corresponding predicate if equal(first1, last1, first2) would return true or equal(first1, last1, first2, pred) would return true or equal(first1, last1, first2, last2) would return true or equal(first1, last1, first2, last2, pred) would return true; otherwise, at worst O(N²), where N has the value distance(first1, last1).