Двоичный поиск в отсортированном списке со всеми узлами как структура Переполнение стека
У меня есть список со всеми элементами в виде структуры формы
typedef struct person_node{
string name;
string country;
}person;
std::list<person> list;
Список уже отсортировано по имени.
Как использовать встроенный binary_search () функция в этом?
Я уже знаю, как использовать это binary_search () в списке только с числами в качестве данных, но мне интересно, как я могу использовать его для такого списка.
Я использую эту двоичную функцию как:
binary_search (list.begin(), list.end(), value, compare_function);
Единственное, что я не знаю, это то, что я должен ввести вместо значение, если мне нужно искать конкретное имя в списке?
Тоже хочу итератор указать на этот узел, если найден.
Решение
Вы вводите person содержащий name ты хочешь найти.
Также обратите внимание, что binary_search полезен только в редких случаях (он говорит только о том, присутствует ли элемент, а не о том, где он находится в коллекции. std::listпотому что это требует, чтобы итераторы с произвольным доступом работали вообще хорошо (который std::list не обеспечивает).
Итак, что вы, вероятно, хотите, это std::vector<person> или же std::deque<person>, который вы, вероятно, захотите найти std::lower_bound или же std::upper_bound, std::lower_bound а также std::upper_bound каждый из них возвращает итератор найденного элемента, предоставляя вам доступ к этому объекту.
Другие решения
Третий пункт описывает то, что вы ищете, таким образом, что вы можете позвонить
compare_function(*iter, value )
или же
compare_function( value, *iter )
где iter является действительным итератором в вашей коллекции. Это должно вернуться true в первом случае, если *iter должен появиться раньше value в вашем списке, чтобы он оставался отсортированным, а во втором случае наоборот.
Обратите внимание, что вы можете передать string в качестве третьего параметра, если ваш compare_function поддерживает обе эти перегрузки. Прототип является:
template <class ForwardIterator, class T, class Compare>
bool binary_search ( ForwardIterator first, ForwardIterator last,
const T& value, Compare comp );
и необязательно, чтобы T был типом значения итератора.
Кстати, пока вы можете использовать его для std::list, это крайне неэффективно для итераторов, которые не имеют произвольного доступа, поскольку каждый std::advance заявление O(N) Таким образом, вся операция O(N log N), Даже регулярный std::find будет быстрее.
использование vector или же multiset если вы можете иметь дубликаты или set если вы не разрешите дубликаты.
Также binary_search сам возвращается true/false относительно того, существует ли предмет и не находит вас предмет (так что вы не будете знать их страну). Если у вас есть дубликаты, вы можете использовать std::equal_range чтобы получить список всех таких значений. Если вы не можете использовать std::lower_bound который доставит вам итератор к первому элементу с именем, равным или большим, чем у вас, а затем проверьте, равен ли он, а не больше.