映射或设置具有透明比较器和异构意义上的非唯一元素

Question

给定 std::set< T, less > 或 std::map< T, less > 独特元素的容器。 less 是异构比较器。 IE。它可以将另一种类型 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 吗？

Answer 1

关联容器要求table前的说明文字说：

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).

然后描述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)进行分区。

只要您满足这些要求，使用异构查找与容器中的多个键等效的东西就没有错。毕竟，the original proposal 中的激励示例是关于在 set 个名字中查找姓氏为 "Smith" 的每个人。

映射或设置具有透明比较器和异构意义上的非唯一元素

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

c++

containers

stl

heterogeneous

c++14