Anton Pevtsov wrote:
The attached file contains my attempt to update lib.alg.partiton and
lib.alg.stable_partiton tests and port them to new test driver.
I think we should rewrite the test and hardcode the initial and
partitioned sequences. I don't think we can sufficiently exercise
the interesting/corner cases by generating the sequence. Also, I
think we should be able to eliminate one of the two predicates.
It's sufficient to exercise the algorithm with just one so long
as we exhaustively verify all the requirements. Let me know if
this makes sense to you and/or if you have any questions.
I suspect a bug in the stable_partiton algorithm implementation.
Suppose that for all elements of an array the predicate is true.
The stable_partition should return "last" in this case.
But call of the stable_partiton on this array fails with the following
assertion:
stdlib\tests\src\alg_test.cpp:135: __thiscall X::~X(void):
Assertion 'id_ && id_ <= id_gen_' failed.
In the debugger you can see that the id_ of the deleting X object is
equal to 0 (I suppose that this X is invalid), but the "this" looks
good.
Yes, the id_ member is reset in the dtor to indicate that the
object has already been destroyed (no valid id_ is ever 0).
What do you think about this issue?
It's certainly possible that there is a bug in the algorithm, but
I would be more inclined to suspect the test before the algorithm
just because you just made making non-trivial changes to it.
I plan investigate this more deeply.
A simple test case would be helpful.
Current test version includes the tests on which stable_partiton fails
and these tests are marked using comments.
Also, there is another intresting thing with the stable_partition
algorithm.
Suppose that an array contains only one element. According to the
standard the complexity in this case should be equal to 0 swaps. Actually
there are 0 swaps, but there is 1 assignment. I guess this is not a bug
(the standard talks nothing about the assignments), but may be there are
unnecessary assignment operations in the stable_partitions
implementation.
What do you think about it?
There is no reason to do anything if there's only one element in
the range, but if the standard allows it we don't need to go to
heroic measures eliminating it. That said, if it's an easy change
we should definitely do it.
A few more comments below...
With best wishes,
Anton Pevtsov
------------------------------------------------------------------------
[...]
template <class T>
struct LessThanPredicate : ComparePredicateBase
{
LessThanPredicate (const int value) : ComparePredicateBase (value) {}
// return a type other than bool but one that is implicitly
// convertible to bool to detect incorrect assumptions
ConvertibleToBool operator() (const T &arg) {
Let's replace the type with the canned conv_to_bool type defined
in alg_test.h.
[...]
// exercises std::partition() and std::stable_partition()
template <class T, class Iterator, class Predicate>
void test_partitions (const std::size_t line, const std::size_t N,
line should be int to match the type of the __LINE__ macro.
const Iterator& it, const Predicate& pr,
const T* , int val, bool stable)
{
_RWSTD_UNUSED(pr);
const char* const itname = type_name (it, (T*)0);
const char* const fname =
stable ? "stable_partition" : "partition";
const char* const funname = Predicate::name();
rw_info (0, 0, 0,
"%s %s (%1$s, %1$s, %s)",
itname, fname, funname);
// create an array of T
T::gen_ = gen_seq;
T *buf = new T[N];
for (std::size_t i = 0; i < N; ++i) {
const Iterator first = make_iter (buf, buf, buf + i + 1, it);
The end pointer above should be (buf + i), not (buf + i + 1). (This is
true in general for all these tests. I corrected this in the others but
forgot to mention it.)
Martin
