Re: [Boost-users] [Multi-Index] performance difference between lower_bound() and upper_bound()

Subject: Re: [Boost-users] [Multi-Index] performance difference between lower_bound() and upper_bound()
From: Dominique Devienne (ddevienne_at_[hidden])
Date: 2013-11-28 07:55:29

On Fri, Nov 22, 2013 at 9:21 PM, Joaquin M Lopez Munoz <joaquin_at_[hidden]>wrote:

> [...] The following
>
>   auto first=c.lower_bound("a 0");
>   auto last=c.upper_bound("a 9");
>   while(first!=last)std::cout<<*first++<<", ";
>
> produces the output
>
>   a 0, a 000, a 1, a 9
>
> while this
>
>   auto first=c.lower_bound("a 0");
>   auto last=c.lower_bound("a :");
>   while(first!=last)std::cout<<*first++<<", ";
>
> produces
>
>   a 0, a 000, a 1, a 9, a 90,
>
> See the difference? Is this related to your problem?
>

Indeed it is. You're right on the money, thank you Joaquín!

By not taking the full-range into account, I was not really getting the
"max suffix", so when I was trying to insert a new entry with name "$prefix
$max_suffix_int", I was again getting a conflict, which triggered another
loop necessary for a different conflict resolution scheme (the new one is
supposed to find a non-conflicting name in a single pass, at the cost of
scanning the range of possible conflicts to find the max_suffix_int of
really conflicting entries - some entries have the same name, butother keys
make them non-conflicting).

I also tested that both lower_bound(prefix + " :") and upper_bound(prefix +
" 9999999999") (I use an int32_t suffix) give me the same upper range
iterator, with similar performance.

So it was all in my buggy code (well, more that I can't properly sort
lexicographically in my head...), and BMI is behaving as expected (as I
suspected all along).

Thank you again for helping me get to the bottom of this. --DD