Extension

Implicit string views

I want to demonstrate how to solve a problem that comes up all the time when trying to write string algorithms... and also came up here, but I didn’t notice it in the original review.

Here is the problem: You want to write a function that can work with strings—or more specifically, views of strings, because you only want to inspect the string data, not take it or change it. For plain old char strings, this is trivial:

auto f(std::string_view sv) { ... }

This will automatically work for anything string-like... provided the character type is char:

f("NUL terminated char arrays work");
f("std::strings work"s);
f("std::string_views work (obv)"sv);
f(my_custom_string_type{"works so long as it is implicitly convertible to std::string_view (which anything 'string-like' should be)"});

Great!

Okay, but now you want to support all character types, not just char. So you naturally do this:

template<typename Char>
auto f(std::basic_string_view<Char> sv) { ... }

Only now... everything breaks. Not only do non char strings (still) not work (except for specializations of basic_string_view)... even the char strings that worked before no longer work:

f("nope");
f("nope"s);
f("well, obviously this works"sv);
f(my_custom_string_type{"nope"});

Your compiler will probably tell you that it could not find a matching function. The only candidate requires a std::basic_string_view<Char> (and then it would deduce Char), and even though everything you threw at it will implicitly convert to a std::basic_string_view<Char>, they are not, in fact, actuallystd::basic_string_view<Char>.

So how to solve this problem?

As always, the solution is just another level of indirection:

template<typename Char>
auto f(std::basic_string_view<Char> sv) { ... }
template<typename S>
auto f(S&& s) { return f(std::basic_string_view<???>{std::forward<S>(s)}); }

Putting aside the question of what the ??? for a moment, this works. Anything string-like, with any character type, will either be converted to a string view... or will be a string view... so there will be no problem finding a match.

But this is hacky, to say the least. So let’s tighten things up a bit.

The first issue is what the ??? should be. How do you get the character type from... literally anything?

Well... you don’t. You just let std::basic_string_view do the work. There are three possible cases here:

1. The type is something that std::basic_string_view<Char> can be constructed from directly... which is specifically just Char const*. In that case, Char is obvious.
2. The type is something that std::basic_string_view<Char> has a converting constructor for... specifically as a contiguous character range. In that case, std::basic_string_view<Char> has a deduction guide that deduces Char.
3. The type is something that has a conversion operator to std::basic_string_view<Char>... that is, anything string-like that isn’t already a contiguous range. In that case, the type itself will tell you what Char is via its conversion operator.

In any case, we can let class template argument deduction (CTAD) do the work:

template<typename Char>
auto f(std::basic_string_view<Char> sv) { ... }
template<typename S>
auto f(S&& s) { return f(std::basic_string_view{std::forward<S>(s)}); }

But this is still not so great, because the second overload claims it takes literally everything. We clearly need to constrain it a bit.

What we need is a "string-like" concept:

template<typename T>
concept string_like = ???;
template<typename Char>
auto f(std::basic_string_view<Char> sv) { ... }
template<string_like S>
auto f(S&& s) { return f(std::basic_string_view{std::forward<S>(s)}); }

Okay, but how do we define "string-like"?

Well, anything that is implicitly convertible to a basic_string_view must be string-like. So:

template<typename T>
concept string_like = std::convertible_to<T, std::basic_string_view<???>>;
template<typename Char>
auto f(std::basic_string_view<Char> sv) { ... }
template<string_like S>
auto f(S&& s) { return f(std::basic_string_view{std::forward<S>(s)}); }

But again we have the problem... what do we put in the ????

This is a problem we already solved! We don’t put anything there. We just let CTAD do its thing:

template<typename T>
concept string_like = std::convertible_to<T, decltype(std::basic_string_view{std::declval<T>()})>;
template<typename Char>
auto f(std::basic_string_view<Char> sv) { ... }
template<string_like S>
auto f(S&& s) { return f(std::basic_string_view{std::forward<S>(s)}); }

The concept works in three steps:

1. Use CTAD to deduce a string view type for the given type.
2. Use decltype to get the type that was deduced.
3. Make sure T is implicitly convertible to that kind of string view.

(We ultimately do an explicit conversion in the function itself, but we require that the type is implicitly convertible. That is on purpose. Anything that is only explicitly convertible to a string view may not be all that string-like. But anything that implicitly converts to a string view must be string-like.)

string_like or something like it is definitely something that should be in your toolkit—or at least you should keep the technique in mind for when you need it.

In the specific case here, it would look like this:

template<typename T>
concept string_like = std::convertible_to<T, decltype(std::basic_string_view{std::declval<T>()})>;
template<typename Char>
constexpr auto are_isomorphic(std::basic_string_view<Char> s1, std::basic_string_view<Char> s2) { ... }
template<string_like S1, string_like S2>
constexpr auto are_isomorphic(S1&& s1, S2&& s2)
{
 return are_isomorphic(std::basic_string_view{std::forward<S1>(s1)}, std::basic_string_view{std::forward<S2>(s2)});
}

Because there are multiple strings involved here, you may also want to confirm that they both have the same character type.

For that, you would need a type trait, like so:

template<string_like S>
using string_char_t = typename decltype(std::basic_string_view{std::declval<S>()})::value_type;

Which you would use to constrain the generic template:

template<string_like S1, string_like S2>
requires std::same_as<string_char_t<S1>, string_char_t<S2>>
constexpr auto are_isomorphic(S1&& s1, S2&& s2)
{
 return are_isomorphic(std::basic_string_view{std::forward<S1>(s1)}, std::basic_string_view{std::forward<S2>(s2)});
}

And now you’re off to the races .

Avoiding linear search

As suggested by @PeterCordes in the comments, if the character size is small enough, you could avoid linear searches for matches by using indexing instead. There is one little wrinkle, which is why this was worth extending the review for, but it’s otherwise pretty straightforward. The following is not at all hand-optimized, but any decent optimizing compiler should have an easy time with it.

template<typename Char>
// Specialize if the bit size of the type is 8 (or less, I suppose).
//
// This is perfectly safe because any type that is legit for use as a
// character in a basic_string_view *must* have a numeric_limits
// specialization.
requires ((std::numeric_limits<Char>::digits + std::numeric_limits<Char>::is_signed) >= 8uz)
constexpr auto are_isomorphic(
 std::basic_string_view<Char> s,
 std::basic_string_view<Char> z) -> bool
{
 // Get the easy check out of the way first.
 if (s.length() != z.length())
 return false;
 constexpr auto size = std::numeric_limits<std::make_unsigned_t<Char>>::max();
 auto mapping = std::array<Char, size>{};
 auto seen = std::bitset<size>{};
 return std::ranges::all_of(std::views::zip(s, z),
 [&mapping, &seen](auto&& t)
 {
 auto const [cs, cz] = t;
 auto const i = static_cast<std::make_unsigned_t<Char>>(cs);
 // If we've already seen the character, and it is *not* mapped to
 // its partner, then we're done.
 //
 // Otherwise, record the mapping.
 if (seen.test(i) and mapping[i] != cz)
 {
 return false;
 }
 else
 {
 mapping[i] = cz;
 seen.set(i);
 }
 // This is the only tricky part!
 //
 // If the target character is "zero", then we can't just search
 // for it in the mapping... because "zero" will be the value set
 // for every character we have not yet seen.
 //
 // When the target character is *not* zero, we just do the easy
 // thing.
 //
 // When the target character *is* zero, we need to loop through
 // all seen mappings, and check them. Unfortunate, but without a
 // sentinel value, it's probably the best we can do. And we can
 // how that "zero" values are vanishingly rare in strings (though
 // undeniably not so in generic data).
 if (cz != Char{})
 {
 if (auto const p = std::ranges::find(mapping, cz); p != std::ranges::end(mapping))
 {
 auto const found_index = std::ranges::distance(std::ranges::begin(mapping), p);
 
 // In theory we should test that the mapping we just found
 // is actually a seen mapping.
 //
 // However, because we have special-cased "zero", the only
 // way there can be a match is if this *is* a seen
 // mapping.
 //
 // If we did not zero-fill the mapping at the beginning,
 // it would have garbage data in it, and so then we would
 // have to do the check. But we did zero-fill the mapping,
 // and cz is not "zero" in this branch, so... we're cool.
 //
 // So there is only one thing left to check:
 if (i != found_index)
 return false;
 }
 }
 else
 {
 // So cz is "zero". That means we can't just search for it in
 // the mapping, because the mapping holds "zero" for every
 // unseen pair.
 //
 // So instead we loop through the seen bitset, and for every
 // mapping that has been seen - other than the one we found or
 // created earlier - we check to see if the mapped value is
 // cz. If it is, then the strings can't be isomorphic.
 for (auto n = 0uz; n != seen.size(); ++n)
 {
 if (i != n and seen.test(n))
 {
 if (index[n] == cz)
 return false;
 }
 }
 }
 }
 );
}

Can this be parallelized or, dare we hope, vectorized?

Maybe!

What you could do is split long strings up into chunks, and for each chunk, generate the array<Char, size> mapping and bitset<size> seen table, then merge them all.

Merging the seen tables is trivial; it’s just merged = seen1 | seen2.

Merging the mapping is a bit trickier. What you want to do is when the mapped element does not match, check that the seen flag is only set in one of the two seen tables—that is, for every position n where mapping1[n] != mapping2[n], seen1.test(n) ^ seen2.test(n) must be true. When the element does match... no biggie; either it was the same mapped pair, or both were never seen (and thus both still "zero"), or one was seen and it happened to be "zero" (which happens to match the unseen case)... all three cases are fine. I’m not really a SIMD guy, but the operations I just described—producing a mask where the mappings don’t match, and then getting their indices and doing the XOR tests with those indices—sure seem doable.

But all through this section we have not asked the Goldblum question . Sure, this can be done... but...

...

... should it?

In my opinion? No.

Let’s be real. This function, while useful and possibly used in some utility or another, it hardly a massively important, linchpin operation. It probably won’t be called thousands or millions of times a second. And it probably won’t be called on strings that are tens of thousands or millions of characters long.

Even in the situation where everything is stacked in such away as to give the best possible advantage to the algorithm that avoids the linear search as opposed to the indexing, you’re literally just talking about avoiding the cost of iterating two bytes at a time over 512 bytes (so 256 iterations) that are always right there, hot in the closest cache. And that is the absolute worst case. In the average case, you’d only be iterating two bytes at a time over 256 bytes (128 iterations), and in the expected realistic case, your strings will usually not be 100+ characters long... so the actual amount of iterating will be much, much smaller. I’m actually skeptical that any cost difference would even be measurable above noise. (And remember that even the indexed solution might need to loop too! Granted, it is far less likely, because NUL does not usually appear in strings, but there is actually a theoretically possible worst case with string data that is just a million NUL characters long. The indexed solution would have to do 256 loop iterations for every character, while the linear search would only ever do one.)

Yes, sure, an algorithm should be as efficient as reasonably possible... but the key word there is "reasonably".

I get the allure of being nerd sniped by a deep, low-level optimization problem that could even get you into managing individual registers and flags and farting around with vector operations. But I am not a scientist or mathematician; I am an engineer. And as an engineer, I can’t allow myself to be blinded by the shininess of the problem, because there are important things that are being forgotten by the kinds of people who want to drop everything and dive into problems like this.

Probably the biggest one, is this: nothing is free. Every tiny little bit of extra complication or complexity you add to a problem brings with it an order of magnitude increase in the cost of making your solution real. And by real I mean: actually coded... AND FULLY TESTED... so that it can actually be used in real-world systems.

If you write a single solution to the problem—either like the original code, or any of the versions offered in the reviews—then you need a battery of tests to verify it. So long as you have only a single solution, that same battery of tests should suffice... meaning that you can freely refactor and experiment with tweaks to try and improve the efficiency, without increasing the maintenance burden. You would have working code, that is verifiably tested, and can be improved.

But the moment you add a second solution—one that special-cases for some factor—you not only double the maintenance burden—because now you need a second battery of tests to exercise the new solution—you actually more than double it—because you also need tests to confirm that the second solution is being selected when you think it is, and is not being selected when you don’t want it to be.

And that is the thing that too many people fail to consider: any additional complexity you add to the solution... even if it may increase the efficiency of the actual code... always requires more testing... and that testing very often costs far, far more than any tiny gains you get from twiddling bits in individual registers, however satisfying that may be. I am perpetually horrified by how few people think of testing at all, or at best give it only a cursory thought. As far as I am concerned, any code that is not properly tested is garbage. I don’t care how sexy or efficient it is; if it has not been verified by a battery of tests, it is absolutely useless. I cannot put it in any project I am responsible for. Only a truly incompetent engineer ships untested code. (And yes, I am straight up calling out the 90+% of coders out there who never test their code... many of whom don’t even know how!)

Of course, if you don’t care about producing code for real-world systems... if you’re actually just in it for the intellectual thrill... then by all means, twiddle bits as much as you please. But if you care about being a real, profession programmer, who produces code that gets used in real-world systems, then you might need to tamp down that nerd lust to fart around with a problem until you’ve squeezed every interesting bit out of it, and instead of sexiness or shininess or coolness, make robustness and proven reliability the thing you focus on.

And yes yes yes of course, there are cases where it is worthwhile, and maybe even necessary, to squeeze every last bit of performance out of some bit of code, and where special-casing is not only useful, but possibly even required to get that performance in the key use cases. That is not generally the case, but yes, there are some functions that are so important, and called so often, that they should be hyper-optimized. But, again, if you want to make real-world code, you need to be able to identify when that is the case... and when it is not.

This case? Sure seems like it’s a "not".

My advice is that your time as a programmer is far better spent on writing (and learning how to write) proper tests for functions like this, than on dicking around with hyper-optimizing it by special-casing. That skill—properly testing and validating code—is worth a billion times more than whatever you might gain counting bytes and cycles. You could literally spend years hyper-fixating on making this function as fast as possible in every possible case... all time which will otherwise be effectively wasted. Meanwhile, every minute you spend doing testing and other validation of whatever code you have now will pay off in piles, because not only will the skills themselves be immediately valuable and transferable... you will also have made this function usable in real-world projects that require verified code (even if you never actually use it).

Don’t get nerd sniped by esoteric crap. Focus on reliability and testing. It is and always will be far more important, and useful, to make code that works... provably works... than to make code that is a few nanoseconds faster.