Hi,

I have a vector of objects (custom class) and I try to sort it this way:

std::vector list; // the vector

struct tSortFunctor
{
   bool operator()(
     ClObject* o1
     , ClObject* o2
     )
   {
     ...
   }
}
;

tSortFunctor sort_sequence;
std::sort(
     list.begin()
     , list.end()
     , sort_sequence
     );

when the list contains less than 16 items it works fine, as soon as it 
contains more than 16 I get an EAccessViolation inside the functor.
Having investigate this I found that at a given time in the sort 
processing (exactly on the 20iest test) le functor is called with a bad 
  ClObject* pointer (333... a value that is obviously not a good memory 
place).
I have tried to dump (printf) my vector before the sort => everything is 
fine, no bad pointer in it.
Is this a problem of the stl shipped with BCB6 ? Is there any solution ?

thank you for your help

"Chris Uzdavinis (TeamB)"  wrote:

>I graduated from my CS coursework in 1996, which was before the STL
>had really become mainstream.  In my OO Design class (1995?), someone
>asked if for an assignment we could use the STL, and the answer was
>"no".

Much of the codebase I'm primarily (supposed to be) working on dates
from 1991. Lots of hand rolled lists and the like.

(And one day the parsing code will become Spirit, once I work out how to
actually get the parse tree out of a successful parse.)

>That was the first time I had heard of the STL, and decided to look
>into it.  Compilers still widely lacked support for a lot of its
>features, in particular member function templates.  So it was more
>theoretical than practical at the time. 

I pretty well grabbed every feature as it turned up.

>After reading that book, I went to the campus bookstore and bought
>Borland C++ 5.0 (not .01 or .02) because it said on the box "All the
>lastest ANSI features" and mentioned the STL on the back too.  I was
>rather disappointed to find that it too lacked member function
>templates, and generally didn't do very well at *anything* (until,
>that is, 5.01 patch was released).  This update dramatically improved
>the product--from a dud to something I thought to be rather excellent.

This code started out on Zortech C++. That became Symantec, and was
pretty shortly afterwards dropped by them in favour of Java (which they
then dropped?). Then new modules got written in Microsoft C++ with MFC
(hey, it was a framework better than my home rolled one).

On going 32-bit, the MS stuff stayed MS, but the other stuff came to
BCB3.

Alan Bellingham
-- 
Team Browns
ACCU Conference 2008: 2-5 April 2008 - Oxford, UK

Alan Bellingham  writes:

> I think one of the problems is that not everyone actually understands
> what strict weak ordering actually is about. Or am I the only one who
> used sort for years before falling over this issue?

I graduated from my CS coursework in 1996, which was before the STL
had really become mainstream.  In my OO Design class (1995?), someone
asked if for an assignment we could use the STL, and the answer was
"no".

That was the first time I had heard of the STL, and decided to look
into it.  Compilers still widely lacked support for a lot of its
features, in particular member function templates.  So it was more
theoretical than practical at the time. 

I bought Musser's book on the STL Tutorial and Reference, and read it
cover to cover before I had *ever* used the STL, and so was introduced
to the ideas and concepts before actually running into anything.

After reading that book, I went to the campus bookstore and bought
Borland C++ 5.0 (not .01 or .02) because it said on the box "All the
lastest ANSI features" and mentioned the STL on the back too.  I was
rather disappointed to find that it too lacked member function
templates, and generally didn't do very well at *anything* (until,
that is, 5.01 patch was released).  This update dramatically improved
the product--from a dud to something I thought to be rather excellent.

-- 
Chris (TeamB);

"Chris Uzdavinis (TeamB)"  wrote:

>(Also, I understand the explanations in the thread.  FWIW, that is
>precisely why I asked if the operator defined a strict weak
>ordering...)

I think one of the problems is that not everyone actually understands
what strict weak ordering actually is about. Or am I the only one who
used sort for years before falling over this issue?

In my case, I am particularly sensitive to the !(a < b) construct purely
because I've fallen over it in my own code, which Is why I looked for it
in the code example.

Alan Bellingham
-- 
Team Browns
ACCU Conference 2008: 2-5 April 2008 - Oxford, UK

E B  writes:

> the whole problem was due to a functor that was not implementing a
> strict '<' which cause std::sort algorithm to go weird !!! (see code
> and explanations in this thread)

I see Alan helped, and am glad to hear it's solved.  

(Also, I understand the explanations in the thread.  FWIW, that is
precisely why I asked if the operator defined a strict weak
ordering...)

-- 
Chris (TeamB);

E B  wrote:

>Thank you very much for your help.

It's a pleasure. Helping someone to not only the solution of their
problem, but understanding of what was wrong as well is in itself quite
rewarding.

Alan Bellingham
-- 
Team Browns
 Borland newsgroup descriptions
      netiquette

the whole problem was due to a functor that was not implementing a 
strict '<' which cause std::sort algorithm to go weird !!! (see code and 
explanations in this thread)

Chris Uzdavinis (TeamB) a écrit :
> E B  writes:

Alan Bellingham a écrit :

> 
> The problem you have is that !(a < b) translates into (a >= b).

Can not believe it was so simple (and I'll have hard time explaining why 
I spent some much time on this ¤$*ù%# problem).
Changing !(r1r1 was the only right thing to do. I will look 
for my old logic courses.

Thank you very much for your help.

E B  wrote:

>You were right
>
>Following your remark, I added
>
>     if ( r1 == r2 )
>     {
>       return memcmp((void*)o1,(void*)o2,sizeof(ClObject*)) > 0;
>     }
>
>just before (in previous message in thread)
>
>     return !(r1 < r2);

I think you've overcomplicated things. A simpler insertion would have
been:

    if ( r1 == r2 )
    {
      return false;
    }

The only reason for the memcmp() is to do an extra level of comparison
when two values are apparently equal. Note that if you changed that
memcmp() return to be "!(memcmp(...) < 0)", you'd almost certainly have
the original problem back again.
  
The simpler fix would have been 

     return (r2 < r1);

or

     return (r1 > r2);

unless you require that extra level of comparison.

(Also, doing memcmp() on objects is an especially bad idea. But that's a
different issue.)

>and now everything works fine (I must admit that I do not really see why 
>now but I'll remember this), thank you for the hint I would never have 
>found without it.

The problem is that the functor you provide *must* comply with strict
weak ordering. This means that *either* op()(a, b) is true, *or* op()(b,
a) is true, or *both* are false (if they are equal). You originally
provided a functor where it's possible for *both* to be true (when r1 ==
r2), and this can be lethal.

The problem is due to the fine tuned nature of the algorithm. For
example, it *needn't* keep checking to see if the two values being
compared are the same object, since that's only necessary when the
comparisons say they two values have the same value.

This has issues when the algorithm is basically one that starts with a
pointer at either end of an array, and moves them together, swapping the
values pointed at when in the wrong relative order. It may only need to
check if the pointers have met when it sees them pointing at equal
objects. With your functor, that never happened. As a result, your
pointers could cross, and run off the ends of the underlying array.

I simplify the logic somewhat, but that's the idea.

And yes, I've been bitten by this.

Alan Bellingham
-- 
Team Browns
ACCU Conference 2008: 2-5 April 2008 - Oxford, UK

E B  writes:

> Hi,
>
> I have a vector of objects (custom class) and I try to sort it this way:
>
> std::vector list; // the vector

list is a misleading name for an instance of a vector!  In the
standard library, lists and vectors are explicitly different and this
is confusing.

> struct tSortFunctor
> {
>   bool operator()(
>     ClObject* o1
>     , ClObject* o2
>     )
>   {
>     ...
>   }

This function should be const.
It's hard to say what should happen since you don't show what the
operator is doing.
Are you sure it defines a strict weak ordering, and doesn't access
invalid memory?  We can't check any of that because you didn't show
the code.  (Or what ClObject even is, for that matter.)

> when the list contains less than 16 items it works fine, as soon as it
> contains more than 16 I get an EAccessViolation inside the functor.

Interesting symptom.

> Having investigate this I found that at a given time in the sort
> processing (exactly on the 20iest test) le functor is called with a
> bad ClObject* pointer (333... a value that is obviously not a good
> memory place).
> I have tried to dump (printf) my vector before the sort => everything
> is fine, no bad pointer in it.
> Is this a problem of the stl shipped with BCB6 ? Is there any solution ?

Are you sure that your vector contains valid pointers before the sort?

-- 
Chris (TeamB);