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

Groups > comp.lang.c++ > #82508

Re: binary_search accoring to its name

Show all headers | View raw

Am 29.11.2021 um 06:57 schrieb Juha Nieminen:

> And not only does it require a slower three-way comparison, ...

Check the generated code: the result of the three way comparison is
in the flags, depending on the type.

> ..., it also uses two conditionals instead of the one that
> std::binary_search/std::lower_bound uses.


The ==-conditional is predictable almost any time since it matches
only one time in the loop. But you're right: in most cases this
code is slower than with lower bound.
But I've developed a lower_bound alternative which is slightly
faster than the lower-bound alternative:

template<typename RandomIt, typename T, typename Pred>
inline
RandomIt xlower_bound( RandomIt begin, RandomIt end, T const &key, Pred 
pred )
	requires std::random_access_iterator<RandomIt>
	&&
	requires( Pred pred, decltype(*RandomIt()) &elem, T const &key )
	{
		{ pred( elem, key ) } -> std::convertible_to<std::strong_ordering>;
	}
{
	using namespace std;
	assert(end >= begin);
	size_t hit = end - begin, lower = 0, upper = hit, mid;
	while( lower != upper )
	{
		mid = lower + (upper - lower) / 2;
		if( pred( begin[mid], key ) >= 0 )
			hit = mid,
			upper = mid;
		else
			lower = mid + 1;
	}
	return begin + hit;
}

On a vector of 1, 4 million string_view-objects I get
about 3% more performance on my computer with clang 13.

Back to comp.lang.c++ | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

binary_search accoring to its name Bonita Montero <Bonita.Montero@gmail.com> - 2021-11-27 15:38 +0100
  Re: binary_search accoring to its name Marcel Mueller <news.5.maazl@spamgourmet.org> - 2021-11-28 12:27 +0100
    Re: binary_search accoring to its name Bonita Montero <Bonita.Montero@gmail.com> - 2021-11-28 17:03 +0100
    Re: binary_search accoring to its name Juha Nieminen <nospam@thanks.invalid> - 2021-11-29 05:57 +0000
      Re: binary_search accoring to its name Bonita Montero <Bonita.Montero@gmail.com> - 2021-11-29 08:26 +0100
        Re: binary_search accoring to its name Bonita Montero <Bonita.Montero@gmail.com> - 2021-11-29 14:02 +0100

csiph-web