查找在有序STL容器中以前綴開頭的所有字符串（非低位ASCII）

Question

我有一個巨大的STL容器std::string（數十萬條目）。目前我正在使用vector，但我很樂意改變。內容按字母順序排序，由字母小寫字母a-z 加ñ組成。

我想實現一個函數，它接收一個const std::string& prefix並返回一對迭代器，一個指向以這樣的前綴開頭的第一個元素，另一個指向最後一個。如果沒有字符串匹配條件，則返回任意兩個相同的迭代器。我在查找時需要效率，因爲矢量很大，所以我想利用它爲二進制搜索進行排序。

我認爲std::lower_bound是我正在尋找，但我缺少一個函數來比較std::string s可以處理西班牙ñ。

Answer 1

您可以使用std::equal_range獲得與數值相同的整個範圍。如果集合中至少有一個匹配的字符串，它會給你一對迭代器，一個迭代器開始，一個迭代器超過範圍末尾。如果字符串不存在，它將會在字符串所屬的位置之後立即給出第一個點的兩個相同的迭代器。

鑑於你只關心尋找一個相同的子字符串，一個正常的字符串比較（的前N個字符）應該工作正常。如果你想支持（比如）一對輸入字符串，並找到它們之間的所有輸入，所以你需要從（比如說）「m *」到「o *」（用你的「ñ*」字符串視爲介於兩者之間），那麼你就必須要有一點點愛好者（通常的做法是建立一個以字符代碼作爲索引的對照表，並將相對順序作爲每個位置的值）。