The code is broken
Before asking “can this code be sexier”, you should be asking “does this code work”.
Spoiler: it doesn’t.
Always test your code
You have written a function comp(a, b). You haven’t written any tests for it. You’ve used it in a single case and got the correct answer, but that means very little.
At the bare minimum, you should have a test suite that has two test cases: one for when a and b are equal, and one for when they are not.
For example, for the “equal” test case, you can just generate bunch of random numbers between 0 and some maximum. Here’s what that might look like using the Catch2 test framework:
#define CATCH_CONFIG_MAIN
#include "catch2/catch.hpp"
#include <cstdint> // need for std::size_t, std::uint32_t
#include <limits>
// include the header with comp() declared
TEST_CASE("comparing equal")
{
constexpr auto num_trials = std::size_t{10};
constexpr auto min_val = std::int32_t{0};
constexpr auto max_val = std::numeric_limits<std::int32_t>::max();
auto value = GENERATE(take(num_trials, random(min_val, max_val)));
INFO("value = " << value);
CHECK_FALSE(comp(value, value)); // value cannot be less-than itself
}
This compiles (with warnings, more on that later), and runs, and all tests pass. That’s what happened for me, anyway. You may or may not get all tests passing, because there is a critical bug in your code. We’ll get back to that in the next section, but for now, I’ll just assume all tests passed.
So now for the “unequal” test case, you just list a bunch of pairs of numbers, where the first number should always compare less-than the second:
TEST_CASE("comparing unequal")
{
auto data = GENERATE(table<std::uint32_t, std::uint32_t>({
// single digit numbers
{1, 0},
{9, 0},
{9, 8},
// ... etc.
// multi-digit numbers
{111, 110},
{124, 123},
{130, 120},
{130, 129},
{200, 100},
{200, 109},
{200, 190},
{200, 199},
// ... etc.
// other interesting cases, add as many as you please
{1, 110}, // this works, but...
{112, 1}, // try this one!
{321, 3212}, // okay...
{3214, 321}, // ... also okay...
{3213, 321}, // ... but uh-oh!
}));
INFO("a = " << std::get<0>(data));
INFO("b = " << std::get<1>(data));
CHECK(comp(std::get<0>(data), std::get<1>(data)));
CHECK_FALSE(comp(std::get<1>(data), std::get<0>(data)));
}
Again, compile and run. This time, there are failures.
Why does those cases fail? I’ll explain later, but for now I’ll just say that your algorithm will fail for some cases where one number is <pattern>, and the second number is <pattern>D<something> where the digit D is the same as the first digit of the pattern. For example, 545 and 54 (the former should come first, to get 54554, rather than 54545) would fail, but 565 and 56 work (56556 is less than 56565).
This is why we write tests.
Turn on warnings
If you compile with g++ or clang (and probably any other compiler), and turn warnings on… which you always should… you will get a warning like this:
warning: control reaches end of non-void function [-Wreturn-type]
(I actually get two warnings, and both matter, but the second isn’t as critical, because you’re only going to be dealing with small sizes. I’ll mention it later, though.)
What that warning is telling is you that you have a function—comp()—that returns something—something that is not void—but somehow it is possible to reach the end of the function—the closing }—without returning a value.
We can figure out exactly what is going on later, but for now, let’s hack a nasty little fix to shut the warning up. At the very end of comp(), right before the closing brace, add the following two lines:
std::cerr << "you have a bug!" <<
"\n a = " << ia <<
"\n b = " << ib <<
'\n';
return false;
If the compiler is right, and if it is possible to get to the end of this function without returning a value, this will display an error message, and then just return false. So compile the test code again, and run it and…
… you get the same results as before… but now there are 10 messages in the output:
you have a bug!
a = 1867888929
b = 1867888929
you have a bug!
a = 1276619030
b = 1276619030
you have a bug!
a = 1911218783
b = 1911218783
... [ and so on ]
(The random numbers will be different, of course, but the pattern—the same number appearing for both a and b—will be the same.)
The compiler was right. You have a bug.
Looking at the messages printed, it seems to only happen when a equals b. Before we caught the bug, the function was just returning gibberish whenever a and b were equal… but you didn’t notice, because it didn’t matter to the algorithm (and also because you didn’t test), because when a and b are equal, the function could either return true or false and it makes no difference. It is undefined behaviour, and just happens to “work” on my platform (and probably yours, but who’s to say, because you didn’t test)… but on other platforms, anything could happen.
This is why we turn on warnings, and fix them.
Summary
Although your code appeared to be working, writing some tests and turning on warnings revealed:
- There are cases where it fails.
- Even when it appears to work, there is dangerous undefined behaviour.
You should always write tests to test your code; oftentimes it will blow your mind how it can fail in surprising and unexpected ways.
You should also always turn on all warnings, and then fix them. Some people even recommend turning warnings into errors, so that even a single warning will kill the compile. That’s not bad advice.
Code review
General issues
Overall, the biggest issue with your code is that it is—as you suspected—wildly overcomplicated. It is so ridiculously overcomplicated, that at least two expert level C++ programmers looked at your code and missed critical bugs, and/or failed to understand what was actually going on. (And I’m not even counting myself; I probably missed stuff, too.) That should be a sign.
There are two general rules that would make a HUGE difference:
- Break up complicated functions into simpler ones. There are multiple parts of
comp() that really should be broken out into separate functions. You have 4 loops in comp(); 1 is the max you should aim for… and even that might be too much, because of the second rule.
- Avoid writing loops. If you find yourself writing a loop, stop… think about what you’re actually trying to do… it’s probably some standard algorithm. In that case, use that algorithm.
The second rule is really the most important, because when you stop yourself from writing naked loops and think in terms of algorithms instead:
- Your code becomes easier to understand.
std::mismatch(a.begin(), a.begin() + min_size, b.begin(), b.begin() + min_size) is already complicated, but I can still tell at a glance roughly what’s going on much easier than I can with a manual loop.
- Complications are easier to spot. It is trivial to spot the difference between
std::mismatch(p, p + max_str.size(), max_str.begin(), max_str.end()) and std::mismatch(max_str.begin(), max_str.end(), p, p + max_str.size()). Spotting the difference between those two loops? Not so much.
- Mistakes are easier to spot. That first loop is just
return std::lexicographical_compare(a.begin(), a.end(), b.begin(), b.end());. But because of the complexity of the loop, you didn’t realize you’d failed to account for the situation where the two strings are equal, and you get to the end of the loop without returning anything.
- Especially when dealing with standard algorithms, they’re already tested and optimized. You can almost never beat them without serious sorcery (and even then, often not).
Review
bool comp(const int32_t ia, const int32_t ib)
You use int32_t throughout, but there are two problems with that.
- First, it’s not
int32_t. It’s std::int32_t, and you have to include <cstdint>. The reason it appears to work for you is probably that you’re using a C++ compiler/library that also doubles as a C compiler/library, and they just include int32_t without the std:: to be lazy. But it’s not guaranteed to work everywhere.
- Second,
int32_t is not portable in any case. All the fixed-width types are platform dependent. The moment you use one, you make your code less portable. And in this case, there’s no reason whatsoever for using one.
There’s absolutely no reason to use int32_t and not int. Using the wrong type breaks your code in some places (like returning it from main()). Where it doesn’t, it just makes your code unnecessarily unportable.
const std::string a = std::to_string(ia);
const std::string b = std::to_string(ib);
While these work fine, they’re unnecessarily inefficient. You already know the maximum size string you’ll need, and you know that both ia and ib should be greater than or equal to zero. You could use arrays and numeric_limits<type>::digits10(), and then to_chars() to do all this lightning fast, and with no memory allocation, something like so:
auto a_chars = std::array<char, std::numeric_limits<decltype(ia)>::digits10() + 2>{};
auto b_chars = std::array<char, std::numeric_limits<decltype(ib)>::digits10() + 2>{};
std::to_chars(a_chars.data(), a_chars.data() + a_chars.size(), ia);
std::to_chars(b_chars.data(), b_chars.data() + b_chars.size(), ib);
Or, better yet, move all that into its own function.
int32_t i = 0;
This is bad practice for a number of reasons.
First, you should only declare variables where you’re going to use them; unless you have a damn good reason, you should never declare them up at the top of a function.
And you should especially not reuse a variable for different things throughout a function. i is used as a loop counter in both branches of that if, for two (or more) entirely different loops. That’s bad. You don’t need it at all for either of the first two loops; in the first loop, it should just be a local counter for a for, if anything, and in the second loop, the same, and after you could set it using min_size.
if (a.size() == b.size()) {
while (i < a.size()) {
if (a.at(i) == b.at(i)) {
++i;
continue;
}
else if (a.at(i) > b.at(i))
return true;
else
return false;
}
} else {
Alright, so what exactly is going on here? The manual loop just complicates what is actually a very simple thing. If the two strings are the same size, you go through looking for any mismatched characters, and if you find a mismatched pair, you return true if the character in a is less than the character in b.
What you don’t account for, though, is what happens if all the characters are equal. In that case, you just fall out of the loop and continue on… and eventually get to the end of the function, which returns nothing. That’s your critical bug.
This is what the code above is actually doing, using algorithms to make everything clearer:
if (a.size() == b.size())
{
auto [it_a, it_b] = std::mismatch(a.begin(), a.end(), b.begin()); // don't need b.end(), because the sizes are the same
if (it_a != a.end()) // don't need to check it_b, because the sizes are the same
{
return *it_a < *it_b;
}
else
{
// what happens here?
//
// your current code does nothing, so the program continues on to the
// end of the function, which has no return statement... thus, the bug
}
}
So what is supposed to happen if the two strings are equal? Logically, I’d think, you would return false, because if the two strings are equal, then ia is not less-than ib. So:
if (a.size() == b.size())
{
auto [it_a, it_b] = std::mismatch(a.begin(), a.end(), b.begin());
if (it_a != a.end())
{
return *it_a < *it_b;
}
else
{
return false;
}
}
But searching for the first mismatch and then returning true if the first char is less than the second is just a lexicographical compare:
if (a.size() == b.size())
{
return std::lexicographical_compare(a.begin(), a.end(), b.begin(), b.end());
}
But that’s just what std::string’s operator< does:
if (a.size() == b.size())
{
return a < b;
}
In other words, if the two strings are same size, return true only if a is lexicographically less than b. If you reason about your code at a higher level, rather than getting bogged down with loops, you can spot these simplifications much more easily. In other words, don’t focus on the details, step back and think about the big picture.
int32_t min_size = static_cast<int32_t>(std::min(a.size(), b.size()));
int32_t max_size = static_cast<int32_t>(std::max(a.size(), b.size()));
Forcing int32_t here introduces potential bugs. None are likely to trigger in reality, because the lengths of the two strings should be very, very small, even for 64- or 128-bit integers. However, there’s no sensible reason to tempt fate.
The first potential bug is truncation if the size is greater than what would fit in an int32_t. Again, that will never happen in reality, but again, why play dangerously for no good reason?
The second potential bug is what a decent compiler with warnings turned on will warn you about. Comparing signed and unsigned values is a craps shoot. If you are mixing signedness in a comparison, you can get absurdities like -1 > 1u.
There’s no reason to force-cast any of the above into int32_t… or to force-cast it into anything. Just use auto, and everything works:
auto const min_size = std::min(a.size(), b.size());
auto const max_size = std::min(a.size(), b.size());
Much less typing, too. Or:
auto const [min_size, max_size] = std::minmax(a.size(), b.size());
That works just as well.
while (i < min_size) {
if (a.at(i) == b.at(i)) {
++i;
continue;
}
else if (a.at(i) > b.at(i))
return true;
else
return false;
}
The next naked loop; what exactly is this one doing? Well, it’s going from 0 (which is the value of i at the start of the loop, though it isn’t immediately obvious from the code), to the minimum size of the two strings, and doing a lexicographical comparison. In other words:
if (auto const res = a.compare(0, min_size, b); res != 0)
{
return res < 0;
}
We don’t even need to check which one is smaller here, because we’re using the minimum size.
Now from this point on is where the problems really start. At this point, you’ve dealt with the case where the two strings have equal length (of course, you need to fix the bug when they’re exactly equal). You’ve also dealt with the case where you have a short string and a long string, and the first part of the long string is either greater or less than the short string. So what you have now is the case where you have a short string, and a longer string that starts with the short string. In other words: the short string is <pattern>, and the long string is <pattern><something>.
So what happens next?
Well, what you do is get the first digit of <pattern>, and then compare it with every digit in <something>. But does that make sense?
Consider when <pattern> is 42, and <something> is 41 or 49:
With 41, you compare the first 4 with the 4 in 41… it’s >=, so you return true.
No problem, 42 should compare less than 4241, because 424241 is greater than 424142.
With 49, you compare the first 4 with the 4 in 49… it’s >=, so you return true.
But 42 should compare less than 4249, because 424249 is NOT greater than 424942.
So your algorithm doesn’t work.
As for the rest of the function, I won’t review it in detail (because it needs to be rewritten), but I’ll just say:
- Avoid
std::string.at(). It’s unnecessary. You know for a fact the string is not empty, so a[0] is guaranteed to work.
- You do some trickery with multiple loops to handle the two cases where
a is shorter or longer than b, but that just caused confusion (as you saw). Instead, just do something like:
if (a.size() < b.size())
some_helper_function(a, b);
else
some_helper_function(b, a);
This is clearer, and safer.
Suggestions for fixing
First, write test cases. Especially consider test cases that might be troublesome.
Your function basically has two paths, one for when the two numbers have equal amounts of digits, and one for when they don’t. So you probably need (at least) three test cases:
TEST_CASE("equal values")
{
// ...
}
TEST_CASE("unequal values with the same digit count")
{
// ...
}
TEST_CASE("unequal values with different digit counts")
{
// ...
}
In the latter case, you should check a bunch of of cases, but especially some cases where the short value is repeated one or more times, like:
- 1 and 11
- 1 and 1111111
- 12 and 1212
- 12 and 12121212
- 21 and 2121
- 21 and 21212121
And you should check cases where the short value is repeated, then followed by something that will make it sort before or after, like:
- 45 and 451
- 45 and 454
- 45 and 459
- 45 and 4545451
- 45 and 4545454
- 45 and 4545459
- 54 and 541
- 54 and 545
- 54 and 549
- 54 and 5454541
- 54 and 5454545
- 54 and 5454549
Once you have your test cases set up, you should think about what makes one number sort before or after another… especially when there is a repeated pattern. Like, does 56 come before or after 561, 565 and 569, and why? What about 56 and 5656561, 5656565, and 5656569? I’ll give you one tip: it’s all about lexical comparisons with the short pattern… repeated lexical comparisons with the short pattern, not just one-and-done.
And of course, turn on warnings, and heed them.
return a+b > b+a;onceaandbare assigned! \$\endgroup\$