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; } );

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

Am 23.11.2021 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.

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; } );

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

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

Am 23.11.2021 um 16:04 schrieb Bonita Montero:

Am 23.11.2021 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.

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; } );

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

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.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

Am 23.11.2021 um 17:13 schrieb Bonita Montero:

Am 23.11.2021 um 16:04 schrieb Bonita Montero:

Am 23.11.2021 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.

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; } );

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

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.

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 );
}

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

Bonita Montero <Bonita.Montero@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).

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

Am 24.11.2021 um 09:06 schrieb Juha Nieminen:

Bonita Montero <Bonita.Montero@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).

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.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

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 );
}

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

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

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

Am 28.11.2021 um 12:36 schrieb 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.

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;
return pair<RandomIt, RandomIt>( begin, end );
}

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

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
?

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)