A C++ program to check if a string is a pangram

Question

I'm new to C++ and decided to implement a simple program that checks if a string is a pangram (i.e. the string contains all the English alphabet letters). It's my first program in C++ and I have some background with interpreted programming languages like Python and R.

I want to know what are the common beginners mistakes I'm making in this implementation, whether I'm following good practices, what I should avoid etc.

The Code

#include<iostream>
#include<string>
#include<vector>
#include <algorithm>

bool isPangram(std::string str) {
    std::transform(str.begin(), str.end(), str.begin(), ::toupper); // Transforming a string to upper case
    std::vector<bool> hash_table(26, false); // a hash_table that maps the  index of a letter from the alphabet
                                             // and a boolean saying if the string contains this element                                             
    int index;
    for(auto c: str){
        if(isalpha(c))
            // Checks if the element in the string is in the alphabet
            index = c - 'A';
            hash_table[index] = true; 
            std::cout << index << std::endl;

    };

    if(std::any_of(hash_table.begin(), hash_table.end(), [](bool v) { return !v; })) {
        // if any of the items in the array evaluates to false
        // means that the string don't contain all the elements 
        // in the alphabet,hence, it's not a pangram

        return false;
    }
    return true;    
};

int main() {
    std::string str = "We promptly judged antique ivory buckles for the next prize"; 
    if (isPangram(str)){ 
         std::cout << "Yes" << std::endl; 
     }
     else {
         std::cout << "No" << std::endl; 
     };
     return 0;
}
```

Answer 1

Here are a number of things that may help you improve your program.

Make sure you have all required #includes

The code uses toupper but doesn't #include <cctype>.

Eliminate spurious semicolons

The code has a number of spurious semicolons immediately after closing braces. They don't bother the compiler but they will bother any other programmer who looks at your code.

Check your if statements for proper braces

It appears from the indentation in the if statement in the isPangram routine is not what you intended to write. The only thing that is currently associated with the if statement is index = c - 'A'; -- all of the lines after that are executed in every case.

Initialize variables before use

The index variable, as mentioned above, may or may not actually get initialized to anything as it's currently written. That leads to undefined behavior of your program, which is not a good thing. Best practice is to initialize variables when they are declared.

Return boolean values directly

The isPangram ends with this strange construct:

if(std::any_of(hash_table.begin(), hash_table.end(), [](bool v) { return !v; })) {
    return false;
}
return true;

Here's a much more direct way to do that:

return std::all_of(hash_table.begin(), hash_table.end(), [](bool v){return v;});

Similarly, within main, I'd write this:

std::cout << (isPangram(str) ? "Yes" : "No" ) << '\n';

Consider a more efficient approach

Consider that the the transform must necessarily visit every letter. We then make another pass through with the main loop. It is possible to do everything in a single pass.

Don't use std::endl unless you really need to flush the stream

The difference between std::endl and '\n' is that std::endl actually flushes the stream. This can be a costly operation in terms of processing time, so it's best to get in the habit of only using it when flushing the stream is actually required. It's not for this code.

Eliminate return 0 at the end of main

When a C++ program reaches the end of main the compiler will automatically generate code to return 0, so it is not necessary to explicitly write that. Some people prefer to do so for style reasons, but it's important to know that it's not required by the standard.

Consider using std::spanstd::accumulate

If your compiler is C++20 capable, this would be a good use of std::accumulate (not std::span as I originally wrote). This version is faster than anything so far.

// helper function for isPangram_accum
constexpr uint_fast32_t charToMask(const unsigned char c){ 
    // can't use non-const toupper in constexpr function
    unsigned index{(c | 0x20u) - 'a'};
    return index < 26 ? ~(1u << index) : ~0;
}

bool isPangram_accum(const std::string& str) {
    uint_fast32_t present{(1u << 26) - 1};
    constexpr auto letterMask = [](uint_fast32_t collection, char ch) {
      if (collection)
        collection &= charToMask(ch);
      return collection;
    };
    return std::accumulate(str.begin(), str.end(), present, letterMask) == 0;
}

Answer 2

• The sequence

    if (condition) {
        return false;
    }
    return true;
  

  is a long way to say

    return !condition;
  

• std::all_of seems more natural than std::any_of, which implies double negation.

• std::toupper is declared in <cctype>. Make sure to explicitly #include it.

• In programming, hash_table has very special meaning. I strongly recommend to rename it to present or something like that.

Answer 3

There's a problem hidden here:

std::transform(str.begin(), str.end(), str.begin(), ::toupper);

The problem is quite subtle (more subtle the missing include of <cctype> or misspelling of std::toupper). It's that std::toupper() accepts a positive int, and plain char may be signed or unsigned.

Promoting signed char to int may result in a negative value, but we need a positive value, usually achieved by converting to unsigned char and allowing that to promote to a (positive) int.

For a safe version, we have to write

std::transform(str.begin(), str.end(), str.begin(),
               [](unsigned char c) { return std::toupper(c); });

Similarly, we need to replace

for(auto c: str){
    if(isalpha(c))

with

for (unsigned char c: str) {
    if (std::isalpha(c))

---

Another portability bug lurks here:

    if(isalpha(c))
        // Checks if the element in the string is in the alphabet
        index = c - 'A';

There's no guarantee that the host character set contains all upper-case letters in any particular sequence. Of particular note, on EBCDIC systems, 'Z'-'A' is significantly more than 25 (it's 37 if I remember correctly), and we'll write outside the bounds of hash_table.

For portable code, we need to change how we store the values - perhaps use a bitset of length UCHAR_MAX, or perhaps a std::set. Then test whether there are any std::isalpha() characters not present.

Answer 4

Note that your entire strategy of assuming 26 alphabetic upper-case characters, and that they're between 'A' and 'Z', breaks if there are any high-8-bit accented characters in a non-UTF-8 8-bit character set. So the locale-aware toupper and isalpha are just slower for probably no benefit.

Several comments have discussed using a "better" data structure for your set of seen letters, because std::vector<bool> is unfortunately required to be specialized as a bit-vector. (Good data structure for some things, especially large bitsets, bad choice of name to expose it in ISO C++, as Howard Hinnant argues). For this use-case of only 26 elements, it's slower than necessary.

The two good choices here for efficiency (and clean concise code) are:

• std::bitset<26> - very cheap to init and check (and convenient with bitset.all()), relatively cheap to update on most ISAs. (Better than std::vector<bool> because the template can specialize itself for the known size being <= one unsigned long or whatever chunk size the library uses. So the compiler will have an easier time being sure it can just keep one integer in a register and OR bits into it.)

  std::bitset is so cheap to check, literally just an integer compare for a small bitset (smaller than the bitness of the machine you're compiling for, which is usually at least 32 these days), you could even consider an early-out check every iteration if you expect very long strings where all 26 letters appear far before the end of the string. (Maybe unroll by 4 so you check every 4 chars).

  With an ASCII-only replacement for isalpha and toupper, some compilers (e.g. clang and ICC) can even auto-vectorize the bit shift / OR, effectively checking 2 to 4 characters in parallel for only somewhat more than the cost of one. (Or even 8 characters in parallel if you replace std::bitset with uint32_t to avoid the silly compiler widening to 64-bit integer elements. Or even 16 with AVX-512)

• std::array<bool,26> - Unlike vector<char>, no dynamic allocation required (it doesn't indirect to separately allocated storage: the object is the array, which is totally fine for a small fixed size like 26). Less cheap than bitset to init and check (especially if the compiler doesn't do a smart job), but even cheaper to update for each char of the string, especially on CPUs like modern x86 where a byte store is extremely cheap, not even an internal word-RMW when committing to L1d cache, although non-x86 CPUs will often do more store coalescing in their store buffer making byte stores still fairly cheap, and likely not a bottleneck unless you seriously optimize the isalpha and toupper checks. (It will hit in cache every time because the array is tiny).

  In theory a smart compiler could check for all 26 byte elements of being set fairly efficiently, with two partially-overlapping SIMD 16-byte loads and a SIMD AND (then on x86 for example, pcmpeqb against 0 / pmovmskb to check for any elements that matched a zero). But in practice GCC is dumb and fully unrolls 1 byte at a time compare/branching.

The clean portable way, not optimizing for ASCII-only

Still only using narrow char, though, not wchar_t and not using UTF-8 aware stuff. non-UTF8 charsets other than ASCII are increasingly rare these days.

Probably a good idea to just use toupper(c) - 'A' and manually check if that's unsigned <= 25, instead of using isalpha: on a POSIX system for example, if LOCALE or LC_ALL aren't "C" (the POSIX locale, pure ASCII), isalpha can also return true for allow accented characters whose upper-case codepoint is also outside the 'A'..'Z' range. For example in a locale like ISO-8859-1 or probably also Windows-1252, somewhere from 0x80 to 0xff.

bool isPangram(const std::string &str)        // note: const-ref arg
{
    static_assert('Z'-'A' == 25, "we assume a charset where letters are contiguous");
    std::bitset<26> present(false);
    //std::array<bool, 26> present = {0};

    for(unsigned char c: str){          // note: unsigned char instead of auto to work around legacy C unsigned-char value range in int arg requirements
        if(isalpha(c)) {      // FIXME: isalpha can return true for high-8-bit c
            auto index = toupper(c) - 'A';
            present[index] = true; 
            // std::cout << index << '\n';
        }
    }

    return present.all();   // nice semantic meaning of "all present"
    //return std::all_of(present.begin(), present.end(), [](bool v){return v;});
};

(Compiles and runs, with complete #include<> list and an improved main, on the Godbolt compiler explorer. Along with some experiments for pure-ASCII, and a manually-vectorized function with SSE2 intrinsics to check a std::array<bool,26> for being all non-zero. Clang's bitmap update is clever for x86-64: With EAX holding the toupper return value: dec al / bts r15, rax. 'A' is ASCII 65, and the bts instruction (bit test-and-set, like dst |= 1<<src) with a reg destination masks the bit-index by &63, like %64, so c-'A' is equivalent to c-1 as a shift count in x86 asm. I don't know why clang thinks using a partial register, AL, is a good idea. Other compilers do worse.)

This also shows other improvements mentioned in other answers:

• const std::string & by-reference arg, which we don't modify. Instead we do toupper inside the loop, and only for alphabetic characters. If you're used to Python, "applying" something to a whole list can be faster than looping manually, but that's because of Python interpreter overhead, where you want to get into a compiled C loop in the Python interpreter. C++ always compiles to native machine code, so you can mostly loop as fast as any std:: template function can. (In theory template functions could use tricks like manual SIMD vectorization, but in practice that's unlikely. However, C library functions like memcmp or strchr are often hand-written in asm, so that's one case where you have fast building blocks that you can't replicate with portable C++, only with intrinsics like x86 _mm_cmpeq_epi8 to do 16 byte-compares in parallel.)

• unsigned char because toupper and isalpha expect their arg in an int (because those functions date back to early C before function prototypes even existed). But they expect the character code to have the value-range of unsigned char. Perhaps a good way to remember this is to imagine that they're implemented by using the int arg as an index into a table of character attributes for the current locale (which is actually true on many libc implementations), so a negative int from sign-extending a signed char would be a problem. That won't happen if your characters are purely ASCII; those are always positive-valued chars, but in general don't assume that. On many ABIs (including the mainstream x86 ones), char is signed. (Fun fact: ARM C/C++ implementations use unsigned char, so your code wouldn't have this problem there.)

• {} after the inner if() so the if also controls using the index. I also moved the declaration of index into that scope because there's no need for it outside.

• static_assert to check that 'Z'-'A' == 25. Non-ASCII / non-UTF-8 character sets are possible in portable C++, but actually making your code slower because of the possibility isn't something you always want to do. But if possible, you can avoid silent failure there.

ASCII-only

Neither of isalpha and toupper will inline, with gcc / glibc / libstdc++. That's normal; non-ASCII locales may have accented characters. But just for fun since we're not handling modern UTF-8 anyway, lets see how fast we can go for ASCII. And because the whole strategy of 26 slots revolves around plain ASCII, not accented upper-case characters.

It only takes a couple operations to check it for being alphabetic, by turning it into an index into the alphabet and checking if that's in the 0..25 range (see this SO answer: set the lower-case bit, then one sub / unsigned compare as a range check). In our case, we actually want that index, so this is perfect. Turns out the check can even auto-vectorize decently, especially with AVX2, allowing compilers to check multiple characters at once. (You can still see asm for the scalar version in a clean-up loop after the vectorized version.)

(Instead of benchmarking, I actually just wanted to look at the asm; turns out clang has some neat tricks up its sleeve and without AVX2 for variable-shift with a per-element shift count, it adds a value into the exponent of a float 1.0 and does float->int conversion to get a per-element 1<<idx, I think. Other compilers just give up and use scalar. Clang also seems to be doing an integer multiply as part of the vectorization, and I don't know what that's about. Haven't fully reverse engineered how it vectorized, and IDK whether it's a real speedup :P)

// I also tried  unsigned int  for most of these; compilers widen sooner for that
// clang isn't usefully getting more work done before widening, but GCC might be

// returns idx, valid.  if valid, idx is in [0..25]
inline  std::pair<unsigned char,bool> ascii_letteridx(unsigned int c)
{
    // strictly ASCII, *not* other 8-bit charsets.
    // the original didn't work for UTF-8 multi-byte accented characters anyway, but non-UTF8 8-bit charsets still exist
    unsigned char lcase = c|0x20;
    unsigned char alpha_idx = lcase - 'a';   // 0..25 for alphabetic.  Will wrap for characters below 'a', or above 25 for > 'z'
    return {alpha_idx,  alpha_idx <= unsigned('z'-'a')};
}


// auto-vectorizes with clang.  And with AVX2, also GCC and ICC.
//  The if() version does very nicely with AVX-512, but compilers do worse with  bool << n
bool isPangram_ascii_compilerfriendly(const std::string &str)
{
    //std::bitset<26> present(false);
    uint32_t bitmap = 0;   // avoid 64-bit so clang auto-vectorizes without widening past 32-bit.

    for(unsigned char c: str){
        auto idx = ascii_letteridx(c);
        //if (idx.second)   // clang / ICC auto-vec even with the if
        {
            //present[idx.first] = true;
            // shift / OR of a 0 as a no-op for non-alphabetic is better than putting a CMOV on the critical path
            //  and enables GCC to auto-vectorize, at least with AVX2 for variable-shift
            bitmap |= uint32_t(idx.second) << idx.first;  // 1UL <<  would be 64-bit and make auto-vectorization worse.
        }
    }

    std::bitset<26> present = bitmap;
    return present.all();  // bitmap == (1UL << 26) - 1;
};

These comments are not a recommendation for how to write code, just leftover notes after looking at how it compiles with gcc, clang, and ICC, for various x86 targets (e.g. -march=sandybridge, -march=haswell (includes AVX2), -march=skylake-avx512)

Answer 5

This is good use of the standard library, and the code is quite good for a beginner.

The main thing that sticks out to me (aside from the points mentioned in the other answers) is that you are passing the input string to your function by value, which creates an unnecessary copy of the string for a function that should just need to read the string and return a boolean. Normally, such a function would accept its argument as a const reference, but the call to std::transform prevents this (at least, the const part of it). The call to std::transform isn't really needed anyway (and results in another, unnecessary loop through each letter), since you can call toupper in your for loop.

I would also suggest using a std::unordered_set<std::string::value_type> instead of a std::vector<bool>. This will allow you to call std::unordered_set::insert() in your for loop, which only adds the letter if it isn't already in the std::unordered_set. Then, instead of calling std::any_of at the end (a loop through possibly all 26 elements of the std::vector<bool>) you can call the constant-time std::unordered_set::size() to determine if the set contains all 26 letters.

Here's how it would look:

bool isPangram(const std::string& str) {
    std::unordered_set<std::string::value_type> hash_table;

    for (auto c : str) {
        if (isalpha(c)) {
            hash_table.insert(::toupper(c));
        };
    };

    return hash_table.size() == 26;
};

Finally, if you do use your original code it would be best to use the proper type for index: not int, but the size_type of the container your are indexing (i.e. std::vector<bool>::size_type for your original container).

Answer 6

Another comment says "Initialize variables before use". I would turn that around and say something like:

Avoid declaring a variable without initialization

The problem occurs in:

int index; // Could change to index=0;
for(auto c: str){
    if(isalpha(c))
        // Checks if the element in the string is in the alphabet
        index = c - 'A';
        hash_table[index] = true; 
        std::cout << index << std::endl;

};

But the solution isn't to initialize index with 0 (or -1), but to move the declaration until you can initialize it as follows:

for(auto c: str){
    if(isalpha(c))
        // Checks if the element in the string is in the alphabet
        const int index = c - 'A';
        hash_table[index] = true; 
        std::cout << index << std::endl;

};

The reason for moving the declaration is that index will have a smaller scope so it is easier to keep track of (for programmers) - and by making it const you don't have to check if it is changed anywhere.