On Fri, Nov 22, 2013 at 9:21 PM, Joaquin M Lopez Munoz <joaquin@tid.es> 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