equal_range sucks !

[Bonita Montero]

I just tried this:

pair<cpu_it, cpu_it> foundApicId = equal_range( apicIds.begin(),
apicIds.end(),
apicId, []( cpu_apic_id const &idRange, unsigned apicId ) { return
idRange.apicId == apicId; } );

It should be possible that the key for the range has a different type
than than the elemnens in the range so that I can compare against a
part of the range-objects like in the above code.

Instead I'd hat to write:

pair<cpu_it, cpu_it> foundApicId = equal_range( apicIds.begin(),
apicIds.end(),
cpu_apic_id( -1, apicId ), []( cpu_apic_id const &idRange, cpu_apic_id
const &id ) { return idRange.apicId == id.apicId; } );

[Bonita Montero]

And even more: I've to use const-references in my lambda.
Who thinks up such nonsense ?

[Bonita Montero]

I've got it:

equal_range uses sth. lower_bound and upper_bound need < and >
comparison. This could be realized by swapping the parameters
on the predicate, therefore the predicate must be symmetrical.
A solution would be a predicate that returns a strong_ordering
object, so that no swapping would be necessary.

[Bonita Montero]

I think it should look like the following then:

#pragma once
#include <iterator>
#include <concepts>
#include <compare>
#include <cassert>

template<typename RandomIt, typename T, typename Pred>
std::pair<RandomIt, RandomIt> xequal_range( RandomIt first, RandomIt
end, T const &key, Pred pred )
requires std::random_access_iterator<RandomIt>
&&
requires( Pred pred, typename
std::iterator_traits<RandomIt>::value_type &elem, T const &key )
{
{ pred( elem, key ) } -> std::convertible_to<std::strong_ordering>;
}
{
using namespace std;
size_t n = end - first;
if( !n )
return pair<RandomIt, RandomIt>( end, end );
strong_ordering so;
for( ; ; )
if( (so = pred( first[n / 2], key )) < 0 )
{
first += n / 2 + 1;
if( !(n -= n / 2 + 1) )
return pair<RandomIt, RandomIt>( end, end );
}
else
if( !(n /= 2) )
if( so == 0 )
break;
else
return pair<RandomIt, RandomIt>( end, end );
n = end - first;
RandomIt lower = first;
do
if( (so = pred( lower[n / 2], key )) > 0 )
n /= 2;
else
lower += n / 2 + 1,
n -= n / 2 + 1;
while( n );
end = lower;
return pair<RandomIt, RandomIt>( first, end );
}

[Juha Nieminen]

Bonita Montero <Bonita....@gmail.com> wrote:
> lower_bound and upper_bound need < and > comparison.

I'm pretty certain they only require that the elements are comparable
with std::less() (which means that operator<() is enough).

[Bonita Montero]

I used the predicated version because I don't want to overload
less myself, which is a larger effort than a lambda. But you
can use lower_bound and upper_bound with asymmetrical predicates.

[Bonita Montero]

This is easier:

#pragma once
#include <iterator>
#include <concepts>
#include <compare>
#include <cassert>

#include <algorithm>

template<typename RandomIt, typename T, typename Pred>

std::pair<RandomIt, RandomIt> xequal_range( RandomIt begin, RandomIt

end, T const &key, Pred pred )
requires std::random_access_iterator<RandomIt>
&&
requires( Pred pred, typename
std::iterator_traits<RandomIt>::value_type &elem, T const &key )
{
{ pred( elem, key ) } -> std::convertible_to<std::strong_ordering>;
}
{
using namespace std;

size_t lower, upper, mid, hit;
strong_ordering so;
for( lower = 0, upper = end - begin, hit = -1; lower < upper; )
{
mid = (lower + upper) / 2;
so = pred( begin[mid], key );
if( so >= 0 )

{
if( so == 0 )

hit = mid;
upper = mid;
}
else
lower = mid + 1;
}
if( hit == -1 )

return pair<RandomIt, RandomIt>( end, end );

begin += hit;
lower = 0;
upper = end - begin;
do
{
mid = (lower + upper) / 2;
so = pred( begin[mid], key );
if( so > 0 )
upper = mid;
else
// so == 0
lower = mid + 1;
} while( lower != upper );
end = begin + lower;
return pair<RandomIt, RandomIt>( begin, end );
}

[Marcel Mueller]

Am 23.11.21 um 15:59 schrieb Bonita Montero:

> I just tried this:
>
>     pair<cpu_it, cpu_it> foundApicId = equal_range( apicIds.begin(),
> apicIds.end(),
>         apicId, []( cpu_apic_id const &idRange, unsigned apicId ) {
> return idRange.apicId == apicId; } );
>
> It should be possible that the key for the range has a different type
> than than the elemnens in the range so that I can compare against a
> part of the range-objects like in the above code.

Feel free to write an asymmetric comparer that fits your needs.

You may also implement an asymmetric operator<, but implicitly comparing
apples with oranges is not a good advice.


Marcel

[Bonita Montero]

I've written an asymmetric version:

template<typename RandomIt, typename T, typename Pred>
std::pair<RandomIt, RandomIt> xequal_range( RandomIt begin, RandomIt
end, T const &key, Pred pred )
requires std::random_access_iterator<RandomIt>
&&
requires( Pred pred, typename
std::iterator_traits<RandomIt>::value_type &elem, T const &key )
{
{ pred( elem, key ) } -> std::convertible_to<std::strong_ordering>;
}
{
using namespace std;

assert(end >= begin);
size_t hit = -1, lower = 0, upper = end - begin, mid;
strong_ordering so;

while( lower != upper )

{
mid = lower + (upper - lower) / 2;

so = pred( begin[mid], key );
if( so >= 0 )
{
if( so == 0 )
hit = mid;
upper = mid;
}
else
lower = mid + 1;
}
if( hit == -1 )
return pair<RandomIt, RandomIt>( end, end );
begin += hit;

hit = 0, lower = 1, upper = end - begin;

while( lower != upper )

{
mid = (lower + upper) / 2;
so = pred( begin[mid], key );
if( so > 0 )
upper = mid;
else

assert(so == 0),
hit = mid,

lower = mid + 1;
}

end = begin + hit + 1;

[Bonita Montero]

Am 28.11.2021 um 17:04 schrieb Bonita Montero:

> template<typename RandomIt, typename T, typename Pred>
> std::pair<RandomIt, RandomIt> xequal_range( RandomIt begin, RandomIt
> end, T const &key, Pred pred )
>     requires std::random_access_iterator<RandomIt>
>     &&
>     requires( Pred pred, typename
> std::iterator_traits<RandomIt>::value_type &elem, T const &key )

Or is:
decltype(*RandomIt())
... more readable than ...

typename std::iterator_traits<RandomIt>::value_type

?