CODEWITHSUNDEEP
c++stringvectorsubstringprefix
Karsh
Karsh

Reputation: 19

C++: Searching an array of strings that begin with a given prefix

Suppose I am given an string vector vector<string> names = {"ab","abs","act","add"}. I am also given a string prefix string prefix ("ab"). My job is to populate another string vector (let's call it vector<string> name_list) with all the names that begin with the given prefix. Currently I am doing this by simply using a string compare function like follows:

for (int i = 0; i < names.size(); ++i)
{
    if (names[i].compare(0, prefix.size(), prefix) == 0) // If name begins with prefix
        (*name_list).push_back(names[i]);
}

This works well for small vectors. In the example above the output would be ["ab","abs"] My question is if this is the most efficient algorithm when the names has let's say millions of strings in it. If not, what other algorithms could be used?

Upvotes: 1

Views: 1786

Answers (1)

bobah
bobah

Reputation: 18864

Start from the iterator retrned by std::set<std::string>::lower_bound(prefix) and search linearly forward.

std::set<std::string> names {"ab","abs","act","add"};
std::string prefix = "ab";
auto itr = names.lower_bound(prefix);
while (itr != names.end() && !prefix.compare(*itr, 0, prefix.size())) {
     // matching string
     ++itr;
}

Upvotes: 1

Related Questions