Являетесь ли IEEE допустимыми ключевыми типами для std:: map и std:: set?

Ответ 1

Я подозреваю, что ограничения должны приниматься как отношение поведения отношения к значениям, фактически используемым в качестве ключей, не обязательно для всех значений типа. У вас нет времени на то, чтобы пройти через стандарт, который ищет язык "дымящегося пистолета", который относится к фактическим элементам контейнера, а не ко всем значениям типа.

Аналогичный случай: что, если компаратор (для контейнера указателей или смарт-указателей) вызывает виртуальную функцию, а кто-то связывает производный класс того типа, который он сравнивает, который переопределяет виртуальную функцию таким образом, чтобы компаратор не строгий слабый порядок? Программа становится undefined, даже если никто никогда не использует этот производный класс?

Если вы сомневаетесь, вы можете поддерживать NaN с помощью компаратора, который является строгим слабым порядком:

bool operator()(double a, double b) {
    if ((a == a) && (b == b)) {
        return a < b;
    }
    if ((a != a) && (b != b)) return false;
    // We have one NaN and one non-NaN.
    // Let say NaN is less than everything
    return (a != a)
}

Последние две строки "оптимизируются" до return (b == b);, хотя я не уверен, что комментарий оптимизируется с ним.

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

Это мало смысла, так как карта не вызывает значений из ниоткуда, она использует только значения, которые она дала (и их копии), но вопрос о правилах, а также правила, насколько я знать. С++ 0x - то же самое. Интересно, есть ли отчет о дефекте или какая-либо точка, подающая его.

Это также раздражает то, что в (очень редких) системах, где std::less является медленным для указателей, вы не можете использовать < в качестве компаратора в карте указателей, даже если вы знаете, что указатели - все элементы одного массива. Позор.

Другим вариантом является использование следующего класса в качестве типа ключа, поэтому ключи проверяются для NaN только при вводе на карту, а не при каждом сравнении, как указано выше.

struct SaneDouble {
    double value;
    SaneDouble (double d) : value(d) {
        if (d != d) throw std::logic_error();
    }
    static friend bool operator<(SaneDouble lhs, SaneDouble rhs) {
        return lhs.value < rhs.value;
    }
    // possibly a conversion to double
};

Возникает еще один вопрос: ясно, что кто-то может создать SaneDouble, а затем установить его value в NaN (при условии, что реализация позволяет им получить один из где-либо без сбоев). Так что, "элементы SaneDouble" строго-слабые или нет? Моя половинчатая попытка создать инвариант класса в конструкторе делает мою программу undefined, даже если никто фактически не разрушает инвариант, просто потому, что они могут и поэтому результаты этого являются "элементами SaneDouble"? Действительно ли это намерение стандарта, что поведение программы определено тогда и только тогда, когда value отмечено private? Стандарт фактически определяет где-нибудь, что такое "элементы" типа?

Интересно, следует ли нам интерпретировать "элементы Ключа", чтобы означать, что компаратор индуцирует строгий слабый порядок на некоторых элементах Клю. Предположительно включая те, которые фактически использовались. "У меня есть пончики", это не значит, что у меня есть каждый пончик. Это, однако, растяжение.

Ответ 2

Короче: это прекрасно (в том смысле, что ваш вопрос о).

Если вы не допустили значения (т.е. NaN), которые не удовлетворяли бы требованиям порядка, то поведение полностью определено.

Ответ 3

Помещение поплавков в качестве ключей ассоциативного контейнера иногда является плохой идеей, так как семантика равенства довольно бедна. Но это зависит от того, что вы хотите сделать. Имейте в виду, что NaN и бесконечности обычно не являются проблемой. Вы можете обрабатывать их со специальными функциями компаратора (обычно я этого не делаю), и, очевидно, требования стандарта касаются фактических ключей, которые попадут в контейнер, который вы можете увидеть как подмножество ключевого типа. Реализация карты никогда не представит ключевые экземпляры, которые вы не подали на карту.

Я использовал этот предикат для карты, где я мог бы отключить два очень близких значения:

struct FuzzyComparer
{
    template <typename T>
    bool operator()(T x, T y) const
    {
        static const T oneMinusEps = (T)1. - 64 * std::numeric_limits<T>::epsilon();
        return x / y < oneMinusEps;
    }
};

Это не дает вам хорошего отношения эквивалентности. Это полезно только тогда, когда вы хотите хранить дискретные значения с плавающей запятой, и вы готовы переносить некоторую ошибку округления в вычислении, которая дает ключ, который вы хотите получить. Для фактических ключей, которые будут вставлены, это даст отношение эквивалентности.

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

Вам либо нужно отбросить часть "отношения эквивалентности", которая не должна быть большой сделкой в ​​коде реального мира (я сомневаюсь, что транзитивность отношения отношения используется настолько, что это вас беспокоит типичная реализация карты) или отбросить совместимость с арифметическими операциями. Но в чем смысл использования значений с плавающей запятой в качестве ключей?

Ответ 4

Вы можете поместить float и double в качестве ключа к std:: map или std:: set, чтобы они были правильно отсортированы.

Проблема заключается в том, когда дело доходит до уникальности, поскольку вы можете получить дубликаты, возникающие из-за того, как сравниваются поплавки и парные.

Использование сравнения, основанного на эпсинонах (близкие значения, считающиеся равными), также небезопасно, поскольку вы могли бы устранить неподданные оригинальные не дубликаты для того, чтобы быть слишком близкими.

"Поиск" может не найти элемент, который существует, если вы используете простое "найти", поэтому вы можете использовать какой-то epsilon lookup с помощью функции upper_bound() в x-delta, где x - это то, что вы действительно ищете для и допускает значение, меньшее x + delta.

Учитывая все это, нет никакой проблемы использования float или double в качестве ключа в std:: multiset или std:: multimap, если вы используете upper_bound для поиска, а не equal_range.

Что касается NaNs, если набор или карта не являются пустыми, они будут считаться "равными" для любого уже существующего элемента и поэтому не будут вставляться. Если вы сначала введете NaN, все последующие вставки должны потерпеть неудачу.

Они будут считаться равными, потому что x<NaN и NaN<x оценивают false.

Конечно, по той же логике, если это карта и вы называете

myMap[ NaN ] = x;

он может по праву модифицировать любой элемент.

(То же самое, если вы делаете find(NaN), который может возвращать любой итератор).

Поэтому, если вы собираетесь использовать NaN в любой части этого расчета, используйте специальный компаратор, такой как Стив Джессоп.