# Beware CTAD on reverse_iterator

Consider the following example of an “STL-style algorithm,” taken from a lab exercise in one of my training courses:

template<class It>
bool is_palindrome(It first, It last) {
while (first != last) {
--last;
if (first == last) break;
if (*first != *last) {
return false;
}
++first;
}
return true;
}


A palindrome is equal to itself when read forwards or backwards, so, I said blithely, we could rewrite it like this:

template<class It>
bool is_palindrome(It first, It last) {
return std::equal(
first, last,
std::reverse_iterator(last),
std::reverse_iterator(first)
);
}


But look out — this code has a bug that causes undefined behavior! Do you see it?

Here’s a test case that triggers the undefined behavior (Godbolt):

std::string s = "foo";
assert(!is_palindrome(s.begin(), s.end()));
assert(is_palindrome(s.begin()+1, s.end()));
assert(!is_palindrome(s.rbegin(), s.rend()));
assert(is_palindrome(s.rbegin(), s.rend()-1));  // Fails! Oof!


The bug is that I left the five characters make_ out of std::make_reverse_iterator. (Or, alternatively, I left the four characters <It> out of std::reverse_iterator<It>.) When I wrote std::reverse_iterator(last) without angle brackets, I was accidentally triggering C++17 class template argument deduction (CTAD). CTAD tries to deduce the template arguments to std::reverse_iterator; and in the latter two cases above, it sees that last is already a reverse_iterator (specifically reverse_iterator<string::iterator>). So CTAD thinks it doesn’t need to do anything.

Thus, in the latter two cases above, std::reverse_iterator(last) is treated as just another way of writing last, and so we’re actually executing std::equal(first, last, last, first) — which immediately runs off the end of the string and has undefined behavior.

My recommended fix is never to use CTAD (certainly never in generic code). I continue to wish that any mainstream compiler would add an opt-in -Wctad diagnostic; see Contra CTAD” (2018-12-09) and “Measuring adoption of C++17 and CTAD in real codebases” (2019-01-16). (I submitted such a diagnostic to Clang back in November 2018, but it never made progress.)

The specific case of reverse_iterator has come up for others in the past:

Separately, it’s mildly interesting that this is an algorithm whose performance can be improved (at least in debug mode) by not using the C++14 four-argument version of std::equal.

template<class It>
bool is_palindrome(It first, It last) {
return std::equal(
first, last,
std::reverse_iterator<It>(last)
// do NOT pass the end of the second range
);
}


The four-iterator version can be O(1) in the case that all the iterators are random-access and (last1 - first1) != (last2 - first2): different-length ranges can never be “equal.” But in this case we know our ranges are definitely the same length, and so we can save a bit of time by skipping that comparison.

Posted 2022-08-02