Check if a string is palindrome or two strings are the opposite of each other

Question

I made a function which checks if a word is the opposite of each other (ex: word and drow) and then realized that with minor changes it could also be used to detect if a word is palindrome. They both return bools, false means they aren't opposite/it isn't palindrome, true means they are/it is. First function:

bool opposite(std::string& first, std::string& second) {
 size_t size = first.size();
 if (size != second.size()) {
 return false;
 }
 for (size_t left = 0, right = size - 1; first[left] == second[right]; ++left, --right) {
 if (left == size) {
 return true;
 }
 }
 return false;
}

Second function:

bool palindrome(std::string& word) {
 for (int left = 0, right = word.size() - 1; word[left] == word[right]; ++left, --right) {
 if (right < 0) {
 return true;
 }
 }
 return false;
}

In the second function I decided to use int because size_t is unsigned, I could use left == first.size() in the if statement, but that would mean calling size() twice which I think would slow me down. The other option would be storing the value returned by first.size() in a size_t (let's call it size), using it to initialize right and changing the condition to left == size, but that would mean keeping an extra size_t variable around.

I already tested them, they work, but the question is, are there improvements I can make to speed them up?

Answer 1

Of course there are possible improvements. First, if you can already use C++17 std::string_view, use that for greater flexibility, specifically decoupling from how the strings are stored.

Next, minimize the number of variables involved. Take special notice that string::data() and string::size() are often a bit more involved than a simple field-access due to SSO.

I also changed the argument-names to a and b because there isn't really any difference between them which would justify a specific order.

constexpr bool opposite(std::string_view a, std::string_view b) noexcept {
 auto size = a.size();
 if(size != b.size())
 return false;
 for(auto pa = end(a), pb = begin(b); size; --size)
 if(*--pa != *pb++)
 return false;
 return true;
}

Or using standard <algorithm>s and reverse-iterators:

 return std::equal(begin(a), end(a), rbegin(b), rend(b)); // C++14
 return a.size() == b.size() && std::equal(begin(a), end(a), rbegin(b));

Apply the same to palindrome(), but also take note that if you tested the first half against the last half, there's no need to thereafter test the remainders each against each other. That would just duplicate the work. Incidentally, that eliminates the int-variable, which might have been too small.

constexpr bool palindrome(std::string_view s) noexcept {
 for(auto left = begin(s), right = end(s); left < right;)
 if(*left++ != *--right)
 return false;
 return true;
}

• Mercury Dime: Should it return true for an empty string?
• Deduplicator: @MercuryDime Of course. It might be a degenerate case, but it is a palindrome.

Answer 2

I would try to utilize a reverse iterator, which was designed pretty much for the cases like this:

#include <algorithm>
bool opposite (std::string& first, std::string& second) {
 return std::equal(first.begin(), first.end(), second.rbegin());
}

• Deduplicator: You really have to compare the lengths separately as a pre-condition, or use the 4-iterator-version. See en.cppreference.com/w/cpp/algorithm/equal
• vnp: @Deduplicator The spec explicitly says that Two ranges are considered equal if they have the same number of elements etc
• Deduplicator: Yes, but the second range is formed from the length of the first range and a begin-iterator. Now if the second range does not actually contain enough elements for that...

Answer 3

for (size_t left = 0, right = size - 1; first[left] == second[right]; ++left, --right) {
 if (left == size) {
 return true;
 }
}

Completely incorrect.

IIRC, accessing sizeth character of first is UB. Even more, at this moment right is (size_t)-1, so you may guess.

For instance, when size is 0, right is initialized to -1. Were it a real character address, it would reside far beyond the reasonable RAM boundaries.