Описание проблемы:
Рассмотрим некоторую структуру, имеющую член std::string name. Для ясности пусть пусть a 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
};
и используйте binary_search в следующей форме:
std::binary_search( vec.begin(), vec.end(), nameToFind, compareHumansByNames );
Кажется, работает, но появляется две большие проблемы:
Во-первых, как инициализировать другие члены данных, но Human::name, особенно в случае, когда у них нет конструктора по умолчанию? установка магических значений может привести к созданию объекта, который является семантически незаконным.
Во-вторых, мы должны объявить этот конструктор как не explicit, чтобы разрешить неявные преобразования во время алгоритма. Плохие последствия этого хорошо известны.
Кроме того, такой временный объект Human будет построен на каждой итерации, что может оказаться довольно дорогостоящим.
Попытка 2: конвертировать Human в std::string.
Мы можем попытаться добавить operator string () в класс Human, который возвращает его name, а затем использовать сравнение для двух std::string s. Однако этот подход также неудобен по следующим причинам:
Во-первых, код не будет компилироваться сразу из-за обсуждаемой проблемы здесь. Нам придется немного поработать, чтобы компилятор использовал соответствующий 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. ". Довольно запутанное ограничение, и мое последнее решение нарушает его. Посмотрите, что говорит об этом стандарт С++:
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 является LessThanComparable (20.1.2).
В явном виде ничего не сказано о типе ForwardIterator. Но в определении LessThanComparable, приведенном в 20.1.2, говорится о сравнении двух элементов того же типа. И вот что я не понимаю. Действительно ли это означает, что тип исследуемого объекта и тип объектов контейнера должны совпадать, и мое решение нарушает это ограничение? Или это не относится к случаю, когда используется компаратор comp и относится только к случаю, когда по умолчанию используется operator < для сравнения? В первом случае я смущен тем, как использовать std::binary_search для решения этой проблемы, не сталкиваясь с проблемами, упомянутыми выше.
Заранее благодарим за помощь и находим время, чтобы прочитать мой вопрос.
Примечание. Я понимаю, что запись двоичного поиска вручную не требует времени и решит проблему мгновенно, но чтобы избежать повторного создания колеса, я хочу использовать std:: binary_search. Также мне очень интересно узнать о существовании такого ограничения в соответствии со стандартом.
