Мистическое ограничение на std :: binary_search

Описание проблемы:
Рассмотрим некоторую структуру, имеющую член std :: string name . Для ясности предположим, что это структура Human , представляющая информацию о людях. Помимо имени он также может иметь много других элементов данных.
Пусть есть контейнер std :: vector vec , в котором объекты уже отсортированы по имени . Также для ясности предположим, что все имена уникальны.
Проблема заключается в : имея некоторую строку 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 , особенно в случае, когда у них нет конструктора по умолчанию? установка магических значений может привести к созданию семантически недопустимого объекта.
Во-вторых, мы должны объявить этот конструктор как не явный , чтобы разрешить неявные преобразования во время алгоритма. Плохие последствия этого хорошо известны.
Кроме того, такой временный объект Human будет создаваться на каждой итерации, что может оказаться довольно дорогостоящим.

Попытка 2: преобразовать Human в std :: 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 .». Довольно запутанное ограничение, и мое последнее решение его нарушает. Давайте посмотрим, что об этом говорится в стандарте C ++:

25.3.3.4 binary_search

template
bool binary_search(ForwardIterator first, ForwardIterator last,
const T& value);

template
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 для решения этой проблемы, не сталкиваясь с проблемами, упомянутыми выше.

Заранее благодарим за помощь и за то, что нашли время прочитать мой вопрос.

Примечание: Я понимаю, что написание двоичного поиска вручную не требует времени и мгновенно решит проблему, но чтобы избежать повторного изобретения wheel Я хочу использовать std :: binary_search. Также мне очень интересно узнать о существовании такого ограничения по стандарту.