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

Question

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?

I think using a suffix array can reduce the number of comparison. — rendon
– rendon, Commented Feb 27, 2014 at 1:19

bobah · Accepted Answer · 2014-02-27 01:21:51Z

1

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;
}

answered Feb 27, 2014 at 1:21

bobah

19k2 gold badges43 silver badges74 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

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

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related