Эффективный поиск в векторе отсортированных строк

У меня есть длинный вектор строк. Пример:

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

Строки в векторе отсортированы по алфавиту.

Я понимаю, что могу использовать std::find, чтобы найти наличие и позицию строки в std::vector. Но поскольку мой вектор отсортирован по алфавиту, есть ли простой в реализации и более эффективный метод проверки существования значения в векторе?


c++ search stdvector
person remi    schedule 21.01.2018    source источник
comment
Если вы хотите увидеть, существует ли значение вообще, я бы рекомендовал использовать std::binary_search (но он возвращает логическое значение, а не итератор для найденного элемента).   -  person orhtej2    schedule 21.01.2018
comment
... Но двоюродный брат std::binary_search, std::lower_bound, может помочь найти итератор для элемента, который вы ищете   -  person StoryTeller - Unslander Monica    schedule 21.01.2018

Ответы (1)


arrow_upward
3
arrow_downward

Если контейнер отсортирован, вы можете использовать std::binary_search:

Проверяет, появляется ли элемент, эквивалентный значению, в диапазоне [первый, последний).

std::string some_value = "xyz";

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

Таким образом, found равно true, если найдено some_value, и 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
}
person Edgar Rokjān    schedule 21.01.2018
comment
Глядя на критерии отсортированного вектора в описании std::binary_search, похоже, что это будет работать только для векторов чисел. Как binary_search понимает алфавитную сортировку? - person remi; 21.01.2018
comment
@ remi000 - std::string имеет перегруженный оператор <. std::binary_search понимает любой тип, если у типа есть компаратор меньше чем, который следует строгому слабому порядку. - person PaulMcKenzie; 21.01.2018
comment
@ remi000 remi000 это будет работать только для векторов чисел - совсем нет, это будет работать для любого типа, сравнимого через <. Также обратите внимание, что вы можете передать пользовательский предикат. - person Edgar Rokjān; 21.01.2018
comment
@PaulMcKenzie, только что заметил, что вы можете обновить свой последний пример? Вы говорите использовать lower_bound, но в примере он показывает двоичный_поиск. - person remi; 21.01.2018
comment
Вероятно, это имелось в виду для @EdgarRokyan. Тем не менее, то же самое верно и для lower_bound — если тип сопоставим с использованием <, тогда он будет работать. - person PaulMcKenzie; 21.01.2018