DaniWeb Forum Index > Software Development > C++

C++ RSS

std:string::find vs std::find

Please support our C++ advertiser: Intel Parallel Studio Home

•

Join Date: Jul 2009

Posts: 2

Reputation: petry is an unknown quantity at this point

Solved Threads: 0

petry

Offline

Newbie Poster

std:string::find vs std::find

Jul 5th, 2009

Hi All:

I have a large number of elements to be stored into vector or basic string(delimited by \n). I need to search for an element and I would like to know what is faster:

A:

 Help with Code Tags 
 C++ Syntax (Toggle Plain Text) 
std::string str = "\nElement1\nElement2...element1000\n"
str.find("\nElement3\n");
std::string str = "\nElement1\nElement2...element1000\n"
str.find("\nElement3\n");

 Help with Code Tags 
 C++ Syntax (Toggle Plain Text) 
std::vector<string> v;
v.push_back("Element1"); v.push_back("Element2");  ....
std::find(v.begin(), v.end(), "Element3") != v.end() )
std::vector<string> v;
v.push_back("Element1"); v.push_back("Element2");  ....
std::find(v.begin(), v.end(), "Element3") != v.end() )

I'm only interested in search time, I don't need to access any of the elements for reading, modifying or removing.

Thanks a lot,
Petry

Last edited by petry; Jul 5th, 2009 at 5:11 am.

•

Join Date: Jun 2006

Posts: 147

Reputation: Laiq Ahmed will become famous soon enough

Solved Threads: 20

Laiq Ahmed Laiq Ahmed is offline

Offline

Junior Poster

Re: std:string::find vs std::find

Jul 5th, 2009

•

Originally Posted by petry

Hi All:

I have a large number of elements to be stored into vector or basic string(delimited by \n). I need to search for an element and I would like to know what is faster:

A:
Help with Code Tags

C++ Syntax (Toggle Plain Text)
std::string str = "\nElement1\nElement2...element1000\n"
str.find("\nElement3\n");
std::string str = "\nElement1\nElement2...element1000\n" str.find("\nElement3\n");
B:
Help with Code Tags

C++ Syntax (Toggle Plain Text)
std::vector<string> v;
v.pushback("Element1"); v.pushback("Element2");  ....
std::find(v.begin(), v.end(), "Element3") != v.end() )
std::vector<string> v; v.pushback("Element1"); v.pushback("Element2"); .... std::find(v.begin(), v.end(), "Element3") != v.end() )
I'm only interested in search time, I don't need to access any of the elements for reading, modifying or removing.

Thanks a lot,
Petry

try to figure out the algorithm used behind string.find(...), and compare it with standard string searching algorithm likes.

•

Rabin-Carp
Boyer- more
etc

the above algorithms have different complexity based on the size of the substring and size of the string in which you wanted to search teh substring... (its totally your effort.., see the STL string code and figure out).

as far as vector is concern again the complexity does matter.
if the size of the string is N elements(ignoring the string comparision cost). its O(N)...

its upto the implementation in which you are about to use .., because vector is more managed then the string which is delimited by some character(in your case \n).

what if you write the modified algorithm that meets your need, like binary search for vector container. or use some other container like BST or hash tables...

or use the STL binary_search with the predicate on string comparision.
Hope this helps

Last edited by Laiq Ahmed; Jul 5th, 2009 at 5:26 am. Reason: forgot STL binary_search

•

Join Date: Jul 2009

Posts: 2

Reputation: petry is an unknown quantity at this point

Solved Threads: 0

petry

Offline

Newbie Poster

Re: std:string::find vs std::find

Jul 5th, 2009

I have just tested the difference.

Filesize: 8mb
Lines: 700.000
Average line length: 15 characters

Time to fill:
vector: 3843ms
string: 3891ms

The search time for the last unique element is:
vector: 218
string: 172

•

Join Date: Dec 2007

Posts: 360

Reputation: jencas is just really nice

Solved Threads: 69

jencas

Offline

Posting Whiz

Re: std:string::find vs std::find

Jul 6th, 2009

If a STL container offers a specialized algorithm, use that one. Normally it is the one with the better performance, i.e. std::list::sort vs. std::sort

Last edited by jencas; Jul 6th, 2009 at 5:24 am.

If you are forced to reinvent the wheel at least try to invent a better one!

Please use code tags - Please mark solved threads as solved