карта или набор с прозрачным компаратором и неуникальными элементами в неоднородном смысле

Дано std::set< T, less > или же std::map< T, less > контейнер уникальных элементов. less является гетерогенным компаратором. То есть он может сравнивать значение какого-то другого типа U против значения типа T, Тогда как все значения типа T уникальны, существует (может быть) множество значений типа T, который сравнивается равным некоторому конкретному значению типа U, Это неопределенное поведение?

Скажем, я хочу найти (один) элемент в контейнере, у которого есть ключ, эквивалентный значению типа U, Любой из них: первый, последний или средний, если их больше одного. Я знаю, что в контейнере более одного элемента, что эквивалентно значению u типа U, Могу ли я использовать std::set::find или же std::map::find функция для? Это неопределенное поведение?

Пример (здесь неточное сравнение с допуском 0.2):

#include <set>
#include <iostream>

double const eps = 0.2;

struct less
{
bool operator () (double l, double r) const { return l < r; }
using is_transparent = void;
bool operator () (int l, double r) const { return l + eps < r; }
bool operator () (double l, int r) const { return l + eps < r; }
};

int main()
{
std::set< double, less > s{0.0, 0.9, 1.0, 1.1, 2.0};
for (auto it = s.find(1); it != std::end(s); it = s.find(1)) {
std::cout << *it << ' ';
s.erase(it);
}
}

Вывод (порядок вообще не указан):

0,9 1 1,1

Это UB, чтобы использовать ассоциативно упорядоченные контейнеры уникальных элементов, как указано выше?

Должен ли я использовать std::multiset а также std::multimap вместо?

2

Решение

Пояснительный текст перед таблицей требований к ассоциативным контейнерам гласит:

kl такое значение, что a [так] разбивается на разделы ([alg.sorting])
в отношении c(r, kl), с r ключевое значение e а также e в
a; ku такое значение, что a разделен по отношению к
!c(ku, r); ke такое значение, что a разделен с уважением
в c(r, ke) а также !c(ke, r), с c(r, ke) подразумевающий !c(ke, r),

А затем описывает поведение a_tran.{find,count,equal_range}(ke), a_tran.lower_bound(kl) а также a_tran.upper_bound(ku), Поэтому требования таковы:

  • За find, count, а также equal_range:
    • Элементы в контейнере должны быть разделены относительно c(r, ke) а также !c(ke, r)
    • c(r, ke) должен подразумевать !c(ke, r)
  • За lower_boundэлементы в контейнере должны быть разделены относительно c(r, kl),
  • За upper_boundэлементы в контейнере должны быть разделены относительно !c(ku, r),

При условии, что вы соответствуете этим требованиям, нет ничего плохого в использовании гетерогенного поиска с чем-то, что эквивалентно нескольким ключам в контейнере. Мотивирующий пример в оригинальное предложение, в конце концов, о поиске всех, чья фамилия «Смит» в set имен.

1

Другие решения

Других решений пока нет …

По вопросам рекламы [email protected]