3
\$\begingroup\$

This function returns true if the string contains zero or one periods, and returns false if the string contains more than one period.

bool isStringValid(std::string str){
    std::size_t pos = str.find('.', 0);
    if(pos != std::string::npos){
        pos = str.find('.', pos + 1);
        if(pos != std::string::npos){
            std::cout << "\nError: Multiple decimal marks\n";
            return false;
        }
    }
    return true;
}

For example:

  • If str is 1.519, it returns true;
  • If str is 159, it returns true;
  • If str is 1.541.1, it returns false;
  • If str is 1.1.1.1, it returns false, and so on.

I am using the Boost C++ libraries elsewhere in the program, if that's useful in any way. This code isn't specific for finding the period . character, it should work with any character, but this is the use case for me.

Can this be done more efficiently?

\$\endgroup\$

1 Answer 1

7
\$\begingroup\$

Optimize for maintainability first

Is the complexity of your function really needed? The functionality can be implemented in one line using only standard-library algorithms.

bool
is_valid(const std::string& str)
{
  return (std::count(std::begin(str), std::end(str), '.') <= 1);
}

Let's see how this will compare against your version. I hope we can agree that for readability, it is a clear win. Considering performance:

  • If the string is valid, both algorithms will iterate over the entire string exactly once.
  • If the string is not valid (contains more than one .), your algorithm will short-circuit and immediately return while std::count will continue iterating until the end of the string.

But do you really expect that the case of strings that

  1. are invalid,
  2. very long and
  3. contain the second . near the beginning

is frequent enough to optimize for? It certainly won't buy you anything in the worst-case scenario. Even if you think it is, I would strongly encourage you to benchmark first. You might very well be surprised.

Don't make copies you don't need

Conceptually, your function is read-only. In order to answer whether a string has a certain property, we don''t have to modify it. Copying strings can be expensive so that operation might well dwarf any other improvement you make. (The iteration is \$\mathcal{O}(n)\$ but copying is also \$\mathcal{O}(n)\$ plus a substantial cost for allocating (and later deallocating) the buffer. Plus potentially touching cold memory.)

The corollary of this is of course to make your function take its parameter as a const reference (as I did in the alternative above).

Don't mix concerns

Your function is a predicate for strings. Predicates should be pure. Producing output shouldn't be any of that function's business. Let the caller of your function decide what they want to do with the result. (To illustrate, think how awkward it would be if std::string::find would write to standard output whenever it found something. Leave alone the performance implications of doing I/O like this.)

Avoid deeply nested control structures

You could improve the readability of your code by reducing the levels of nested structures by returning early. For example, if you start by

const auto pos = str.find('.', 0);
if (pos == std::string::npos)
  return true;

then you can flush the remainder of the code to the left. I also find this style more readable because I don't have to check whether the function will actually do anything else after that point.

\$\endgroup\$
3
  • \$\begingroup\$ Generally i would prefer to use the container functions rather than the algorithm ones. so str.begin() rather than std::begin(str) \$\endgroup\$
    – miscco
    Commented Oct 24, 2016 at 8:03
  • \$\begingroup\$ @miscco People's preferences on this differ and apparently, so do yours and mine. In the end, it doesn't really matter in non-generic code. \$\endgroup\$
    – 5gon12eder
    Commented Oct 25, 2016 at 0:03
  • 1
    \$\begingroup\$ @Anonymous std::begin(c) works in all situations where c.begin() works but the converse is not true. For built-in arrays, only the free function can be used. If you know the type of c and it's a standard container, then it's just a matter of style which version you use. But in generic code, where you don't know the type of c, using the free functions is more general. \$\endgroup\$
    – 5gon12eder
    Commented Oct 25, 2016 at 9:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.