Verify string format with given pattern

Question

I'm implementing an auxiliary global function which has to check whether a given string has correct format (i.e., it begins with a letter and only contains letters, numbers or the "_" character).

This function, named ok_tret, will be used in the methods of a couple classes and will help ensure that the attributes are initialized with correct words and the rest of the methods are getting correct words as parameters.

The classes will be used in situations in which incorrect inputs are not frequent. They'll only happen when the user misspells the word, or by ignorance. So my guess is there will be two errors per read at worst.

My first ok_tret proposal returns a bool that tells us whether the given word is correct. This means we'll have to do the cin in the class method and then pass the word to the function. If there's error, then we'll have various function calls, until eventually the functions returns true.

const char *err4 = "ERROR. Init again.";

// Check correctness, return corresponding bool.
bool ok_tret(const string& nom) {
    if (not ((nom[0] >= 'a' and nom[0] <= 'z') or
        (nom[0] >= 'A' and nom[0] <= 'Z'))) {
        cout << err4 << endl;
        return false;
    } 
    for (unsigned int i = 1; i < nom.length(); ++i) {
        if (not ((nom[i] >= '0' and nom[i] <= '9') or 
            (nom[i] >= 'A' and nom[i] <= 'Z') or 
            (nom[i] >= 'a' and nom[i] <= 'z') or nom[i] == '_')) {
                cout << err4 << endl;
                return false;
        }
    }
    return true;
}

The next proposal also does the cin, so in order to get a correct word there's no need for various function calls.

// Check correctness and cin until nom contains a correct word. Iterative.
void ok_tret(string& nom) {
    bool P = true;
    while (P) {
        if ((nom[0] >= 'a' and nom[0] <= 'z') or 
            (nom[0] >= 'A' and nom[0] <= 'Z')) {
            for (unsigned int i = 1; P and i < nom.length(); ++i)
                if (not ((nom[i] >= '0' and nom[i] <= '9') or 
                    (nom[i] >= 'A' and nom[i] <= 'Z') or 
                    (nom[i] >= 'a' and nom[i] <= 'z') or nom[i] == '_')) 
                    P = false;
        } else P = false; 
        P = !P; 
        if (P) {
            cout << err4 << endl;
            cin >> nom;
        }
    }
}

Finally a recursive solution, obviously there will be multiple function calls:

// Check correctness and cin until nom contains a correct word. Recursive.
void ok_tret(string& nom) {
    if (not ((nom[0] >= 'a' and nom[0] <= 'z') or 
        (nom[0] >= 'A' and nom[0] <= 'Z'))) {
            cout << err4 << endl;
            cin >> nom;
            ok_tret(nom);
            return;
    }
    for (unsigned int i = 1; i < nom.length(); ++i) {
        if (not ((nom[i] >= '0' and nom[i] <= '9') or 
            (nom[i] >= 'A' and nom[i] <= 'Z') or 
            (nom[i] >= 'a' and nom[i] <= 'z') or nom[i] == '_')) {
                cout << err4 << endl;
                cin >> nom;
                ok_tret(nom);
                return;
        }
    }
}

I wanted to know:

1. Which proposal looks more natural?
2. Given the context in which the code will be used, there's no meaningful runtime difference between proposals. But... come on, which one would you choose and why?
3. If number of errors could be arbitrary (0 to a billion), which one would you choose and why?

Answer 1

I'd instead use the std::isalpha() to check for the alphabets, and for the rest; use isalnum() plus an or condition for the _ character.

Another check, I'd put is whether the input's length is indeed \$ \gt 0 \$. The code then becomes:

// Check correctness, return corresponding bool.
bool ok_tret(const string& nom) {
    if (nom.length() < 1) {
        // handle null strings
        return false;
    }
    if (not (bool) std::isalpha(nom[0])) {
        cout << err4 << endl;
        return false;
    } 
    for (unsigned int i = 1; i < nom.length(); ++i) {
        if (not ((bool) std::isalnum(nom[i]) or nom[i] == '_')) {
                cout << err4 << endl;
                return false;
        }
    }
    return true;
}

Answer 2

Regular Expression Solution

Firstly, this can be accomplished with regular expressions rather easily:

bool ok_tret(const std::string& nom){

    static const std::regex re{"^[a-zA-Z][a-zA-Z0-9_]+$"};

    return std::regex_match(nom, re);
}

The advantage is obvious: compactness. We are making a single call to a function, ok_tret is basically acting as a wrapper function.

The problem with this some might say is readability: not everyone understands regular expressions, but that can be said of other language features like template metaprogramming and moreover there are many tools online to build your own regular expressions.

Performance Considerations

I tested both the regular expression function and your function, for a million strings, of length 100 characters, randomly distributed. Your function was 6% the total time for mine.

With -O3, it was 2.5% of the total time for the regular expression. So the more specific approach seems to be more easily optimised by the compiler.

This is to be expected since a specialised solution will run faster; regular expressions are coded to deal with virtually any matching conditions. However, I suspect this function won't be called as in my test conditions and the performance difference won't come into play.

---

Some obvious complaints with your code are not to use a const char*, go with,

constexpr char* err4{"ERROR. Init again."};

where you are using two modern C++ features: constant expressions and uniform initialisation.

Answer 3

Your first version is the closest to being in good programming style.

I don't like #3 because recursion's practical usefulness is limited. It leads to hard-to-understand code. I believe it is only taught to the degree it is in programming classes to force students to think. In nearly every case, the code can-- and should-- be rewritten to use iteration. It will be clearer, shorter, less error-prone, easier to read, and use less memory.

I don't like #2 because it is a tenet of programming that one ought to separate user interaction from the logic of the program. This is if you need to change how the program gets its data, you only have to change it in one place, without going through multiple functions. The processing functions should just process the input they're given as parameters (or member variables, for classes). It is actually cleaner this way. Don't worry about multiple functions; functions' actual cost is close to 0 with a decent compiler.

Anyway, a few comments:

const char *err4 = "ERROR. Init again.";

Why isn't this a std::string? You're using C++, so make use of its features.

void ok_tret(string& nom)

Is this a language other than English? I can't find any meaning of "tret" in wiktionary that makes sense here, which means it's probably an abbreviation or initialism. You really ought to write out the whole word; you don't get a bonus for making your function names cryptically short.

Also, why are you using string instead of std::string? It's bad practice to have using namespace std;.

if (not ((nom[0] >= 'a' and nom[0] <= 'z') or
    (nom[0] >= 'A' and nom[0] <= 'Z'))) {

Use std::isalpha() instead. (you'll need to #include <cctype>)

for (unsigned int i = 1; i < nom.length(); ++i) {

Use an iterator. You should also become aware of about the new c++ range-based for syntax, available since 2011, though it's a little questionable to use here. It'd be something like for(const char& c : nom.substr(1))

            if (not ((nom[i] >= '0' and nom[i] <= '9') or 
                (nom[i] >= 'A' and nom[i] <= 'Z') or 
                (nom[i] >= 'a' and nom[i] <= 'z') or nom[i] == '_')) 

Using std::isalnum() you can replace most of this, also in cctype.

Answer 4

An addendum to JNS's std::regex answer: we can compare two implementations for speed. The first is a corrected version of the OP code (testing the string length and using <cctype> functions to work with character encodings that have non-contiguous alphabets), and the second is a simplified regexp function:

#include <cctype>
#include <regex>
#include <string>

bool v1(const std::string& nom)
{
    if (nom.size() == 0 || !std::isalpha(nom[0]))
        return false;
    for (auto c: nom)
        if (c != '_' && !std::isalnum(c))
            return false;
    return true;
}

bool v2(const std::string& nom)
{
    static const std::regex re{"[a-zA-Z][a-zA-Z0-9_]*"};
    return std::regex_match(nom, re);
}

We can test both implementations for correctness, and compare their runtimes.

Here, we create one million strings of length 0-100 chars, alternating valid and invalid.

#include <algorithm>
#include <chrono>
#include <iostream>
#include <iterator>
#include <random>
#include <vector>

static std::random_device rd;
static std::mt19937 gen{rd()};

template<typename T>
auto& pick_one(T&& s)
{
    auto dist = std::uniform_int_distribution<>{0, (int)s.size() - 1};
    return s[dist(gen)];
}

std::string example(bool valid)
{
    static const std::string letters = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
    static const std::string idchars = letters + "0123456789_";
    static const std::string others = "!@#$%^&*(){}?<>:+/,.;=-\\|'";

    static std::uniform_int_distribution<> length_dist{0, 100};
    std::string::size_type length = length_dist(gen);
    if (!length && valid) ++length;
    if (!length) return {};

    auto id = std::string(length, pick_one(letters));
    std::generate(id.begin()+1, id.end(), [] { return pick_one(idchars); });

    if (!valid)
        pick_one(id) = pick_one(others);

    return id;
}

int verify(const std::vector<std::string>& ids, bool (*f)(const std::string&))
{
    auto errs = 0;
    bool v = true;
    for (auto const s: ids)
        errs += (v=!v) != f(s);
    return errs;
}

int main()
{
    std::vector<std::string> test_set;
    auto n = 1000000u;
    bool v = true;
    test_set.reserve(n);
    std::generate_n(std::back_inserter(test_set), n, [&v]{ return example(v=!v); });

    // Run through once each to reduce biases due to cache memory and branch prediction
    auto errs = verify(test_set, v1)
        + verify(test_set, v2);

    using Duration = std::chrono::duration<double, std::chrono::milliseconds::period>;

    auto begin = std::chrono::steady_clock::now();
    errs += verify(test_set, v1);
    auto end = std::chrono::steady_clock::now();
    Duration time_1 = end - begin;

    begin = std::chrono::steady_clock::now();
    errs += verify(test_set, v2);
    end = std::chrono::steady_clock::now();
    Duration time_2 = end - begin;

    std::cout << (time_2/time_1) << std::endl;
    return errs;
}

Without optimisation, I found that v1 was about 10 times the speed of v2, but gcc -O3 reduced the margin to about 5:1 or so. This is still embarrassing for the regex implementation - we would expect it to be close to our hand-rolled implementation (particularly as we've made sure that it also respects locale). I'd appreciate any comments that help explain the disparity.

Answer 5

I would use some standard library functions to help you out.

// Check correctness, return corresponding bool.
bool ok_tret(string const& nom) {
    if (not std::isalpha(nom[0])) {
        std::cout << err4 << "\n";
        return false;
    } 

    static constexpr char valid[] = "abcdef.......XYZ0123456789_";
    if (std::strspn(nom.c_str(), valid) != nom.size()) {
        std::cout << err4 << "\n";
        return false;
    }
    return true;
}

Answer 6

All three versions have a common bug:

Accessing the first element of nom is undefined behaviour if the string is empty. Check the size() of it before doing anything else!

---

All three versions have a problem with error output.

Firstly, error output should be separated from normal output, so use std::cerr rather than std::cout for these. That allows piping the output of your program into another to work in the usual way.

Secondly, it can limit your future options if utility functions such as these produce their own output. It's better to use the return value (or, in some cases, exceptions) to communicate with the calling code. That allows you to use the function in a daemon (reporting via syslog) or in a GUI program (reporting via a message window), or to take other corrective action.