Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c++ > #82402 > unrolled thread

equal_range sucks !

Back to article view | Back to comp.lang.c++

Contents

  equal_range sucks ! Bonita Montero <Bonita.Montero@gmail.com> - 2021-11-23 15:59 +0100
    Re: equal_range sucks ! Bonita Montero <Bonita.Montero@gmail.com> - 2021-11-23 16:04 +0100
      Re: equal_range sucks ! Bonita Montero <Bonita.Montero@gmail.com> - 2021-11-23 17:13 +0100
        Re: equal_range sucks ! Bonita Montero <Bonita.Montero@gmail.com> - 2021-11-23 19:53 +0100
          Re: equal_range sucks ! Bonita Montero <Bonita.Montero@gmail.com> - 2021-11-25 15:02 +0100
        Re: equal_range sucks ! Juha Nieminen <nospam@thanks.invalid> - 2021-11-24 08:06 +0000
          Re: equal_range sucks ! Bonita Montero <Bonita.Montero@gmail.com> - 2021-11-24 18:18 +0100
    Re: equal_range sucks ! Marcel Mueller <news.5.maazl@spamgourmet.org> - 2021-11-28 12:36 +0100
      Re: equal_range sucks ! Bonita Montero <Bonita.Montero@gmail.com> - 2021-11-28 17:04 +0100
        Re: equal_range sucks ! Bonita Montero <Bonita.Montero@gmail.com> - 2021-11-28 17:23 +0100

#82402 — equal_range sucks !

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

[toc] | [next] | [standalone]

#82404

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 ?

[toc] | [prev] | [next] | [standalone]

#82406

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.

[toc] | [prev] | [next] | [standalone]

#82420

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

[toc] | [prev] | [next] | [standalone]

#82482

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

[toc] | [prev] | [next] | [standalone]

#82437

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

[toc] | [prev] | [next] | [standalone]

#82455

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.

[toc] | [prev] | [next] | [standalone]

#82501

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

[toc] | [prev] | [next] | [standalone]

#82503

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

[toc] | [prev] | [next] | [standalone]

#82504

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
?

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.c++

csiph-web