Описание проблемы: Рассмотрим некоторую структуру, имеющую член std::string name.Для ясности предположим, что это struct Human, представляющий информацию о людях.Помимо name он также может иметь много других элементов данных.Пусть будет контейнер std::vector<Human> vec, где объекты уже отсортированы по name.Также для наглядности предположим, что все имена уникальны. Проблема в : наличие некоторой строки nameToFind выяснить, существует ли элемент в массиве с таким именем.
Решение и мой прогресс: Очевидное и естественное решение, по-видимому, выполняет бинарный поиск с использованием функции std::binary_search.Но есть проблема: тип искомого элемента (std::string) отличается от типа элементов в контейнере (Human), а для std :: binary_search необходимо правило для сравнения этих элементов.Я попытался решить эту проблему тремя способами, описанными ниже.Первые два приведены только для иллюстрации эволюции моего решения и проблем, с которыми я столкнулся.Мой главный вопрос относится к третьему.
Попытка 1: преобразовать std::string в Human.
Напишите функцию сравнения:
bool compareHumansByNames( const Human& lhs, const Human& rhs )
{
return lhs.name < rhs.name;
}
Затем добавьте конструктор, который создает объект Human из std::string:
struct Human
{
Human( const std::string& s );
//... other methods
std::string name;
//... other members
};
и используйте двоичный_поиск в следующей форме:
std::binary_search( vec.begin(), vec.end(), nameToFind, compareHumansByNames );
Кажется работающим, но получаетсядве большие проблемы:Во-первых, как инициализировать другие элементы данных, кроме Human::name, особенно в случае, когда у них нет конструктора по умолчанию?установка магических значений может привести к созданию объекта, который семантически недопустим.Во-вторых, мы должны объявить этот конструктор как не explicit, чтобы разрешить неявные преобразования во время алгоритма.Плохие последствия этого хорошо известны.Кроме того, такой временный объект Human будет создаваться на каждой итерации, что может оказаться довольно дорогим.
Попытка 2: преобразовать Human в std::string.
Мы можем попытаться добавить operator string () к классу Human, который возвращает его name, а затем использовать сравнение для двух std::string с.Однако этот подход также неудобен по следующим причинам:
Во-первых, код не будет компилироваться сразу из-за обсуждаемой проблемы здесь .Нам нужно будет немного поработать, чтобы компилятор использовал соответствующий operator <.Во-вторых, что значит «преобразовать человека в строку»?Наличие такого преобразования может привести к семантически неправильному использованию класса Human, что нежелательно.
Попытка 3: сравнить без преобразований.
Лучшее решение, которое я получилпока что нужно создать
struct Comparator
{
bool operator() ( const Human& lhs, const std::string& rhs )
{
return lhs.name < rhs;
}
bool operator() ( const std::string& lhs, const Human& rhs )
{
return lhs < rhs.name;
}
};
и использовать бинарный поиск как
binary_search( vec.begin(), vec.end(), nameToFind, Comparator() );
. Это компилируется и выполняется правильно, все вроде бы нормально, но вот где начинается интересная часть:
Посмотрите на http://www.sgi.com/tech/stl/binary_search.html. Здесь сказано, что тип значения ForwardIterator равен того же типа, что и T . ».Довольно запутанное ограничение, и мое последнее решение нарушает его.Давайте посмотрим, что говорит об этом стандарт C ++:
25.3.3.4 binary_search
template<class ForwardIterator, class T>
bool binary_search(ForwardIterator first, ForwardIterator last,
const T& value);
template<class ForwardIterator, class T, class Compare>
bool binary_search(ForwardIterator first, ForwardIterator last,
const T& value, Compare comp);
Требуется: Тип T isLessThanComparable (20.1.2).
Ничего явно не сказано о типе ForwardIterator.Но в определении LessThanComparable , приведенном в 20.1.2 , говорится о сравнении двух элементов одного типа .И вот что я не понимаю.Действительно ли это означает, что тип объекта поиска и тип объектов контейнера должны совпадать, и мое решение нарушает это ограничение?Или это не относится к случаю, когда используется компаратор comp, а относится только к случаю, когда для сравнения используется значение по умолчанию operator <?В первом случае я запутался в том, как использовать std::binary_search, чтобы решить эту проблему, не сталкиваясь с проблемами, упомянутыми выше.
Заранее благодарен за помощь и нашел время, чтобы прочитать мой вопрос.
Примечание: Я понимаю, что написание бинарного поиска вручную не занимает много времени и решит проблему мгновенно, ночтобы не изобретать велосипед, я хочу использовать std :: binary_search.Также мне очень интересно узнать о существовании такого ограничения согласно стандарту.