Re: [Boost-users] intrusive bug: equal_range implementation vs bounded_range precondition

Subject: Re: [Boost-users] intrusive bug: equal_range implementation vs bounded_range precondition
From: Matei David (matei_at_[hidden])
Date: 2014-12-12 18:27:34

On Sat, 13 Dec 2014 00:03:56 +0100
Ion Gaztañaga <igaztanaga_at_[hidden]> wrote:

> El 12/12/2014 2:02, Matei David escribió:
> > In the absence of a bug tracker, I'll post the potential bug here:
> >
> > I'm seeing some strange results out of `multiset::equal_range`. I
> > didn't isolate a test case, but looking at the code something seems
> > wrong:
> >
> > The `bstree_algorithms::equal_range(const KeyType &,
> > KeyValueCompare)` method is currently implemented (in
> > `bstree_algorithms.hpp`) as a call to
> > `bstree_algorithms::bounded_range(header, key, key, comp, true,
> > true)`. However, `bounded_range` states as prerequisite: If
> > 'lower_key' == 'upper_key', ('left_closed' or 'right_closed') must
> > be false.
> >
> > Either the `equal_range` implementation or the `bounded_range`
> > precondition is wrong.
> 
> The precondition is wrong. It should read "('left_closed' AND 
> 'right_closed') must be false.

But they are both true in the call!

I think it should be that at least 1 is true; i.e.:

  'left_closed' OR 'right_closed' must be TRUE.

Look at it another way. If called with lower_key==upper_key:

- The most sensible thing is to have both ends closed (which is what
  the call is doing). Then the function should return the range of
  elements with key equal to the argument.

- If either end is open, the returned range (rg) will necessarily be
  empty (rg.first==rg.last), but the actual iterator (rg.first) can
  still be meaningful: if right_open, rg.first=upper_bound(key); if
  left_open, rg.first=lower_bound(key).

- If both ends are open, rg.first cannot have any meaningful value,
  perhaps just container.end(). It makes sense to disallow this.

M