My IsIsogram() implementation

Unreal Courses Talk
,
#1 
bool FBullCowGame::MyIsIsogram(FString String) const
{
    // TIP: we do not need to check for 0/1 letter words, since the code below works anyway
    // less code = less things to worry about :)
    TMap <char, bool> SeenLetters;

    for (auto Letter : String)
    {
        char LowercaseLetter = tolower(Letter);
        if (SeenLetters[LowercaseLetter]) { // if seeen letters contains current letter
            return false; // its not an isogram
        }

        // otherwise add current letter to seen letters
        // TIP: we do not need else here, since return exits the function as well as the for loop
        SeenLetters[LowercaseLetter] = true;
    }

    return true; // no letters seen twice
}
1 Like
#2

Nice work. Thanks for sharing. The code looks beautiful and very legible.

#3

Observation: If you only need to support ascii characters, you can use an array of bools, like:

bool SeenLetters[256]; // technically, ascii is restricted to 128 characters, but let's splurge a bit.

And if you wanted to get fancier, you could use bits of integers instead of bool, like:

uint32_t SeenLetters[8];

I just looked at TMap’s implementation and it seems to have a per element overhead of 8 bytes and an alignment requirement of 4 bytes, so each char in the map would take up 12 bytes. There’s another part of the implementation that adds overhead but I found it slightly harder to understand. In any cause, there’s a helpful function that returns how much has been allocated, called GetAllocatedSize().

1 Like
#4

Just noting that this is tagged for section 2 and is not using UE4 so TMap is just #define TMap std::map

#5

I would be VERY cautious of writing code like that because it totally obfuscates what’s going on.

#6

Ah, I didn’t actually watch the first section.

And most std::map implementations have an overhead of 3 pointers, which would be 16 bytes total on 32 bit architectures and 32 bytes on 64 bit.

#7

I wouldn’t really recommend doing it manually, in production code. There are libraries like Boost.DynamicBitset that provide optimal bitset operations like this. Though in this case, you could go with std::bitset, which isn’t dynamic.

Just because the naive implementation seems to make the code harder to read, doesn’t mean you can’t have the best of both worlds.

For example:

#include <assert.h>
#include <bitset>
#include <string>

bool MyIsIsogram(std::string String)
{
    // TIP: we do not need to check for 0/1 letter words, since the code below works anyway
    // less code = less things to worry about :)
    std::bitset<256> SeenLetters;
    static_assert(sizeof(std::bitset<256>) == 32, "");

    for (auto Letter : String)
    {
        char LowercaseLetter = tolower(Letter);
        if (SeenLetters[LowercaseLetter]) { // if seeen letters contains current letter
            return false; // its not an isogram
        }

        // otherwise add current letter to seen letters
        // TIP: we do not need else here, since return exits the function as well as the for loop
        SeenLetters[LowercaseLetter] = true;
    }

    return true; // no letters seen twice
}
int main() {
  assert(MyIsIsogram("hi"));
  assert(!MyIsIsogram("hh"));
}

That’s just as readable and yet, requires no allocations and has significantly higher performance.

Note, UE4 also has a TBitSet.

Anyways, from the perspective of teaching people C++, I’d suggest that teaching manual bit manipulation is a must, eventually and from the perspective of shipping code, using a node based map for this is a suboptimal solution, when either standard or defacto solutions exist for doing bit operations that solve the problem.

#8

Ah yes. If it’s properly wrapped then that’s great.

Privacy & Terms