Faster lower_bound / upper_bound
From
Bonita Montero@Bonita.Montero@gmail.com to
comp.lang.c++ on Mon Nov 2 10:24:16 2026
From Newsgroup: comp.lang.c++
I wondered why lower_bound and upper_bound are almost twice as fast
with clang-cl than with MSVC. I inspected the code and MSVC didn't
use conditional moves (see below) and the non-predictible branches
did really hurt.
So I wrote two generic functions which do the same and make it easier
for MSVC to do the optimization. And it worked: The MSVC-code is only
slightly slower than the clang-cl-code with that.
#pragma once
#include <type_traits>
#include <functional>
template<typename Iterator, typename Ref, typename Cmp = std::less<std::iter_value_t<Iterator>>>
inline Iterator xlower_bound( Iterator begin, Iterator end, const Ref
&value, Cmp cmp = Cmp() )
{
for( size_t n = end - begin; n; )
{
size_t
mid = n / 2,
nRight = n - mid - 1;
Iterator right = begin + mid + 1;
bool less = cmp( begin[mid], value );
begin = less ? right : begin;
n = less ? nRight : mid;
}
return begin;
}
template<typename Iterator, typename Ref, typename Cmp = std::less<std::iter_value_t<Iterator>>>
inline Iterator xupper_bound( Iterator begin, Iterator end, const Ref
&value, Cmp cmp = Cmp() )
{
for( size_t n = end - begin; n; )
{
size_t
mid = n / 2,
nRight = n - mid - 1;
Iterator right = begin + mid + 1;
bool less = cmp( value, begin[mid] );
begin = less ? begin : right;
n = less ? mid : nRight;
}
return begin;
}
--- Synchronet 3.22a-Linux NewsLink 1.2