Дано 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
вместо?
Пояснительный текст перед таблицей требований к ассоциативным контейнерам гласит:
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
имен.
Других решений пока нет …