intrusive bug: equal_range implementation vs bounded_range precondition
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. Matei
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. Ion
The precondition is wrong. It should read "('left_closed' AND 'right_closed') must be false.
Sorry. That's also incorrect: left_closed || right_closed == true. That is: first = upper_bound(lower_key); second = lower_bound(upper_key); leads to an invalid range, since "first" could be bigger than "second" if lower_key == upper_key. Ion
On Sat, 13 Dec 2014 00:03:56 +0100 Ion Gaztañaga <igaztanaga@gmail.com> 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
participants (1)
-
Ion Gaztañaga -
Matei David