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