Find if a string contains a character in C++ (boost allowed)

Question

Suppose I have a string and I want to find whether a specific character (like '|') is present or not, what is the best and fastest technique to do so? I know string find implementation.I am asking for even faster implementation than this one.

Solution 1

Use std::string::find

if (str.find('|') != std::string::npos)
{
    // ...
}

There's unlikely to be anything more efficient. O(n) is the best you can do. The standard library implementation should be pretty much optimal.

Solution 2

From this source empirical test done with Visual Studio 2013 Compiler shows that strchr routine is about 2x faster than std::string::find implementation.

Solution 3

Adding on the answer of Tom Tanner. If you don't want to do any a priori calculations you will be stuck at O(n), ie there is a linear correlation between the length of the string you are searching in and the time consumption. Tom suggested to set up an array (or vector) of booleans that indicate whether a certain character occurred. It would need O(n) once to index the string, but then you can check for any number of characters in O(1) (constant time) if it is included. The downside with this approach is that you will need a lot of memory (once you decide you need to support unicode).

As a compromise you could use a std::set or similar, storing only the characters that actually exist in your input string. Memory consumption would then be around linear with regard to the number of different characters in the string but lookup would be O(log n), ie logarithmic in time.

Of course you should measure/profile and then explain here what use case you are actually optimizing for. Until you have done so, stick with what is easiest to understand and read.

Solution 4

Another way is to use the strchr function on the corresponding c_str string:

if(strchr(str.c_str(), '|'))
{
    \\found
}

Not sure how it compares to std find in terms of speed though...

The position of the found character is

size_t pos = strchr(str.c_str(),'|') - str.c_str();

View more solutions

Comments

[namezero]

"If the character is not found, the function returns a null pointer". So in your example, you're subtracting from a NULL pointer in that case. Pointer overflow is UB.

[afakih]

@namezero That's why we start with an if statement before attempting to get the pos by subtraction, so if the character is not found we don't attempt to get the pos.

[afakih]

@Peter yeah obviously we need to provide the character we are looking for..(fixed)