在排序的字符串向量中进行有效搜索

Question

我有一个很长的字符串向量。示例：

std::string data;
data.push_back("abc");
data.push_back("bcd");
//...
data.push_back("zze");
data.push_back("zzz");

向量中的字符串按字母顺序排序。

我知道我可以使用 std::find 来查找 std::vector 中字符串的存在和位置。但是由于我的向量是按字母顺序排序的，是否有一种易于实现且更有效的方法来检查向量中是否存在值？

Answer 1

如果容器已排序，您可以使用 std::binary_search:

Checks if an element equivalent to value appears within the range [first, last).

std::string some_value = "xyz";

const auto found =
    std::binary_search(std::cbegin(data), std::cend(data), some_value);

所以如果找到 some_value，found 就是 true，否则 false。

如果您有兴趣获得指向您要查找的元素的迭代器，请考虑使用 std::lower_bound:

const auto it =
    std::binary_search(std::cbegin(data), std::cend(data), some_value);

if (it != std::cend(data)) {
    // element is found, it points to this element
}

在排序的字符串向量中进行有效搜索

Effective search in sorted string vector

c++

search

stdvector