C++：搜索以给定前缀开头的字符串数组

Question

假设我给出了一个字符串向量vector<string> names = {"ab","abs","act","add"}。我也给了一个字符串前缀string prefix ("ab")。我的工作是填充另一个字符串矢量（我们称之为vector<string> name_list），其中包含以给定前缀开头的所有名称。目前我正在通过简单地使用字符串比较功能来做到这一点，如下所示：

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

这适用于小向量。在上面的例子中，输出将是["ab","abs"]我的问题是如果这是最有效的算法，当names让我们说数百万字符串。如果不是，还可以使用哪些其他算法？

Answer 1

从迭代器开始，迭代器被std::set<std::string>::lower_bound(prefix)重新搜索并且线性向前搜索。

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