Orient - 2 months ago 12

C++ Question

Given

`std::set< T, less >`

`std::map< T, less >`

`less`

`U`

`T`

`T`

`T`

`U`

Say, I want to find (one) element in the container, which have the key, equivalent to the value of type

`U`

`u`

`U`

`std::set::find`

`std::map::find`

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`

`std::multimap`

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

- The elements in the container must be partitioned with respect to
- 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.