c++stlcontainersc++14heterogeneous

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?

Solution

  • 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:

    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.