Как отсортировать массив структур с помощью std::binary_search или std::sort

#c #algorithm #data-structures #stl #structure

#c #алгоритм #структуры данных #stl #структура

Вопрос:

У меня есть отсортированный массив структур. Я хочу использовать для этого std::binary_search или std::find .

Куда бы я ни посмотрел, я нахожу примеры, которые показывают, как это сделать с вектором структур. Никогда с массивом структур. Я не уверен, должен ли я использовать предикат или перегружать = оператор или что.

Каким должен быть третий параметр для std::find , если я использую следующий вызов:

template< class InputIt, class T > InputIt find( InputIt first, InputIt last, const Tamp; value );

Кроме того, в нем говорится, что вышеупомянутые вызовы вернут итератор или вернут последний. Как это работает со структурами. Структуры не имеют итераторов, не так ли?

1. То же самое происходит с массивом в виде вектора. Если вы используете массивы C, они должны быть std::array , и std::begin и std::end работать независимо.

2. Нет способа сделать это без std::arrays? что, если я использую обычную структуру a [MAX]?

3. std::begin и std::end работают независимо . А для массивов итератором будет указатель. Указатели соответствуют требованиям итераторов с произвольным доступом.

4. @chris и как определить, std::find какой конкретный элемент данных структуры использовать для сравнения? перегружать = оператор? И что будет содержать возвращаемое значение? индекс?

5.Как указано в любой ссылке, std::find использует operator== , или вы можете использовать std::find_if . И это возвращает итератор (указатель здесь) на найденный элемент или last .

Ответ №1:

Если вы хотите применить это к (допустимому) диапазону массивов [a, b) массива arr , InputIt должно быть std::begin(arr) a и OutputIt должно быть std::begin(arr) b . Если b равно количеству элементов в arr , то вы также можете задать OutputIt значение std::end(arr) .

std::begin и std::end вызванный массив типа T возвращает T *. Таким образом, вы всегда можете заменить T * на InputIt и OutputIt , когда думаете об этих функциях в массивах. std::find возвращает InputIt. Итак, вы получаете указатель на соответствующий элемент массива. Если ничего не было найдено, он возвращает last .