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

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

关联容器要求表前的说明文字说:

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 中的激励示例毕竟，它是关于在集合 名称中查找姓氏为“Smith”的每个人。