std:string::find vs std::find

[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:

std::string str = "\nElement1\nElement2...element1000\n"
str.find("\nElement3\n");

B:

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

[Laiq Ahmed]

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:

std::string str = "\nElement1\nElement2...element1000\n"
str.find("\nElement3\n");

B:

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

[petry]

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

[jencas]

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