2

给定std::set< T, less >或std::map< T, less >包含独特元素的容器。less是异构比较器。即它可以将其他类型U的值与 type 的值进行比较T。尽管 type 的所有值T都是唯一的，但（可能）有很多 type 的值T，它们比较等于 type 的某个特定值U。它是未定义的行为吗？

说，我想在容器中找到（一个）元素，它有键，相当于 type 的值U。任何一个：第一个、最后一个或中间（如果有多个）。我知道，容器中有多个元素，相当于utype的值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::multisetandstd::multimap代替吗？

4

1 回答 1

1

关联容器需求表之前的解释性文本说：

kl是一个值，使得a[ sic ] 相对于 进行分区（[alg.sorting]），c(r, kl)键值r为e和ein 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)。

只要您满足这些要求，就可以使用异构查找与容器中的多个键等效的东西。毕竟，最初提案中的激励示例是关于在名字中查找姓氏为“Smith”的每个人set。

于 2016-11-09T10:47:46.993 回答