CODEWITHSUNDEEP
c++stringboost
psyche
psyche

Reputation: 443

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

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.

Upvotes: 15

Views: 69089

Answers (7)

Fred Larson
Fred Larson

Reputation: 62083

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.

Upvotes: 35

HappyTran
HappyTran

Reputation: 513

You can try this:

   string s1 = "Hello";
   string s2 = "el";
   if(strstr(s1.c_str(),s2.c_str()))
   {
    cout << " S1 Contains S2";
   }

Upvotes: 0

Mouze
Mouze

Reputation: 706

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

Upvotes: 2

afakih
afakih

Reputation: 365

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();

Upvotes: 1

Simon Schmei&#223;er
Simon Schmei&#223;er

Reputation: 369

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.

Upvotes: 1

Tom Tanner
Tom Tanner

Reputation: 9354

Given your statement that you want something faster than string::find, the only thing I can think of would be to create a class which had highly customised assignment operators which on every update of the string updated an internal table which contained the first position in the string of every possible character (256 for a char string, 65536(?) for a wide string). This has O(1) lookup at the expense of quite a lot of complexity added to non-const operations.

Upvotes: 0

Rontogiannis Aristofanis
Rontogiannis Aristofanis

Reputation: 9063

There is only one way to do this. Just iterate over the string to check if the character you are seeking exists. You can do this by using the string::find function, which gets a character and returns the first position that it occurs in the string, or string::npos if the value is not present. You could also use std::find, which gets two iterators, begin and end and a key value 'k' and returns an iterator pointing at the first occurrence of k in the range [begin, end], or end if k wasn't found. And of course, you can implement the find function by yourself, like this:

string::size_type pos=string::npos;
for(string::size_type i=0; i<s.size(); ++i) {
  if(s[i] == key) {
     pos=i;
     break;
  }
}
if(pos != string::npos) {
  // key was found
} else {
  // not found
}

or this:

string::iterator pos=s.end();
for(string::iterator i=s.begin(); i!=s.end(); ++i) {
  if(*i == key) {
    pos=i;
    break;
  }
}
if(pos != s.end()) {
  // found
} else {
  // not found
}

More about the std::string::find and std::find:

Upvotes: 0

Related Questions