поиск гетерогенных контейнеров в C++98

В проекте, над которым я работаю, я вынужден использовать С++ 98. Имея необходимость выполнять быстрый поиск в определенных векторах структур, используя только несколько элементов этих структур в качестве ключей, я до сих пор с удовольствием передавал std::lower_bound и std::upper_bound параметр value с типом, отличным от этих структур, и функтором сравнения, который будет правильно обрабатывать этот гетерогенный случай.

Все работает, как и ожидалось, но сегодня я вдруг понял, что это не разрешено стандартом, и нашел подтверждение этой догадке в нескольких документах, например этот, который также предлагает поправку к стандарту, который, как я сейчас узнаю, был реализован в C ++0x, как подтверждает другой документ.

Мой вопрос: является ли тот факт, что мой код работает должным образом, несмотря на то, что он НЕ соответствует букве стандарта, простым совпадением, побочным эффектом конкретной реализации, негарантированный результат, я должен изменить компилятор и еще много чего?

Другими словами, должен ли я действительно действительно действительно изменить свой код, чтобы он соответствовал стандарту (что значительно усложнило бы его), или я могу просто не беспокоиться и оставить его, учитывая, что эта кодовая база не собирается компилироваться ни с чем, кроме g++ на данный момент?


c++ containers comparison c++-standard-library c++98
person Fabio A.    schedule 03.07.2017    source источник
comment
Почему вы считаете, что это запрещено? Я сам делал это пару раз, и если бы это было запрещено, прототип использовал бы std::iterator_traits<IteratorType>::value_type вместо T.   -  person Johannes Schaub - litb    schedule 03.07.2017
comment
Можете ли вы добавить крошечный фрагмент, показывающий ваш вариант использования? В настоящее время это не очень легко читать   -  person Passer By    schedule 03.07.2017
comment
Все это объяснено в первой статье, на которую я дал ссылку, вместе с вариантами использования.   -  person Fabio A.    schedule 03.07.2017
comment
Согласно cppreference, упорядоченное требование не так строго, как соблюдение строгого порядка. cppreference говорит, что диапазон [first, last) должен быть разделен относительно выражения element < value или comp(element, value). И cppreference намеревается задокументировать, по словам их создателей, все стандарты от C++03 до C++17.   -  person Johannes Schaub - litb    schedule 03.07.2017
comment
Да, @JohannesSchaub-litb, так оно и есть в C++0x и выше, но не так, как в C++98. Все это объясняется в первой статье, на которую я ссылаюсь, в которой предлагается именно та новая формулировка, которая затем была реализована в стандарте.   -  person Fabio A.    schedule 03.07.2017
comment
@JohannesSchaub-litb При всем уважении, cppreference является неудовлетворительным источником для такого вопроса, поскольку, несмотря на его стандарты качества, НЕЛЬЗЯ доверять тому, чтобы он на 100% соответствовал букве стандарта. И еще меньше можно доверять документированию каждого неясного требования или гарантии, налагаемой стандартом.   -  person    schedule 03.07.2017
comment
Для справки, вот нижний предел STL, который, вероятно, ближе к C++98, чем к стандарту C++11: sgi.com/tech/stl/lower_bound.html   -  person Johannes Schaub - litb    schedule 03.07.2017
comment
Если вы перейдете к C++11, формулировка изменится, чтобы учесть то, что вы делаете. Маловероятно, что поставщики компиляторов изменят работу своей стандартной библиотеки для старой версии стандарта.   -  person Galik    schedule 03.07.2017
comment
Это выпуск 270 LWG. Я помещу список DR на страницу.   -  person T.C.    schedule 03.07.2017

Ответы (1)


arrow_upward
1
arrow_downward

Только вы можете решить, стоит ли сохранение статус-кво риска. Однако, если вы перейдете к C++11, формулировка изменится, чтобы учесть то, что вы делаете.

Я думаю, что маловероятно, что поставщики компиляторов изменят работу своей стандартной библиотеки для старой версии стандарта. Поэтому я не вижу большой вероятности того, что ваш код C++98 сломается, если вы не переместите его в непроверенный компилятор. И даже если бы это произошло, вы всегда могли бы реализовать свою собственную (замещающую) версию std::lower_bound для размещения.

Согласно моему прочтению Стандарта C++11, у вас все в порядке.

25.4.3.1 нижняя_граница [ нижняя.граница ]

template<class ForwardIterator, class T>
ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last, const T& value);

template<class ForwardIterator, class T, class Compare>
ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last, const T& value, Compare comp);

1 Требуется: Элементы e из [first,last) должны быть разделены относительно выражения e ‹ value или comp(e, value).

2 Возвращает: самый дальний итератор i в диапазоне [first,last] такой, что для любого итератора j в диапазоне [first,i) выполняются следующие соответствующие условия: *j ‹ value or comp(* j, значение) != ложь.

3 Сложность: не более log 2 (последнее – первое) + O(1) сравнений.

Требование 2 не требует, чтобы value был того же типа, что и *e.

Также в документе, на который вы ссылаетесь, говорится:

Но законно ли это? Позиция стандарта по этому вопросу не обнадеживает. Во-первых, в 25.3 говорится, что для правильной работы алгоритмов объект сравнения должен индуцировать строгое слабое упорядочение значений.

Это взято из Стандарта C++03 и не соответствует той формулировке, которую я нашел в Стандарте C++11, в которой говорится следующее:

25.4 Сортировка и связанные операции [ alg.sorting ]

3 Для всех алгоритмов, использующих Compare, существует версия, в которой вместо этого используется оператор‹. То есть comp(*i, *j) != false по умолчанию *i ‹ *j != false. Для правильной работы алгоритмов, отличных от описанных в 25.4.3, comp должен индуцировать строгое слабое упорядочение значений.

Это дает явное исключение из алгоритма, используемого std::lower_bound:

25.4.3 Двоичный поиск [ alg.binary.search ]

1 Все алгоритмы в этом разделе являются версиями бинарного поиска и предполагают, что искомая последовательность разделена относительно выражения, сформированного путем привязки ключа поиска к аргументу неявной или явной функции сравнения. .

Эта формулировка позволяет «аргументу» функции сравнения иметь тип, отличный от типа элементов контейнера. Он просто должен соответствовать «ключу поиска».

person Galik    schedule 03.07.2017