Boost Users :
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
- If both ends are open, rg.first cannot have any meaningful value,
perhaps just container.end(). It makes sense to disallow this.
Boost-users list run by williamkempf at hotmail.com, kalb at libertysoft.com, bjorn.karlsson at readsoft.com, gregod at cs.rpi.edu, wekempf at cox.net