Orient Orient - 28 days ago 7
C++ Question

map or set with transparent comparator and non-unique elements in heterogeneous sense

Given

std::set< T, less >
or
std::map< T, less >
container of unique elements.
less
is heterogeneous comparator. I.e. it can compare value of some another type
U
against a value of type
T
. Whereas all the values of type
T
are unique, there are (maybe) a plenty of values of type
T
, that compare equal to some particular value of type
U
. Is it undefined behaviour?

Say, I want to find (one) element in the container, which have the key, equivalent to the value of type
U
. Any one: either first, last or middle of them if there more then one. I know, that there are more then one element in the container, which are equivalent to the value
u
of type
U
. Can I use
std::set::find
or
std::map::find
function for? Is it undefined behaviour?

Example (here imprecise comparison with tolerance
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);
}
}


Output (order generally unspecified):


0.9 1 1.1


Is it UB to use associative ordered containers of unique elements as above?

Should I use
std::multiset
and
std::multimap
instead?

Answer

The explanatory text before the associative container requirements table says:

kl is a value such that a [sic] is partitioned ([alg.sorting]) with respect to c(r, kl), with r the key value of e and e in a; ku is a value such that a is partitioned with respect to !c(ku, r); ke is a value such that a is partitioned with respect to c(r, ke) and !c(ke, r), with c(r, ke) implying !c(ke, r).

And then describes the behavior of a_tran.{find,count,equal_range}(ke), a_tran.lower_bound(kl) and a_tran.upper_bound(ku). Therefore, the requirements are:

  • For find, count, and equal_range:
    • The elements in the container must be partitioned with respect to c(r, ke) and !c(ke, r)
    • c(r, ke) must imply !c(ke, r)
  • For lower_bound, the elements in the container must be partitioned with respect to c(r, kl).
  • For upper_bound, the elements in the container must be partitioned with respect to !c(ku, r).

Provided that you meet those requirements, there's nothing wrong with using heterogeneous lookup with something that's equivalent to multiple keys in the container. The motivating example in the original proposal, after all, is about looking up everyone whose family name is "Smith" in a set of names.