The Qsort challenge

Quote:

---

Originally posted by Yves M P.S. Please don't get into flame-wars ;) This thread (and the last one on qsort) is interesting, so it's best not to get too personal. I would hate to have to close this thread :/

---

Yves, Mai's QSort shenanigans are starting to become troll bait.

If I started a thread called "it is safe to use delete on operator new[]" would you keep allowing me to post code after code showing that "compiler x accepts it", knowing full well that doing this is undefined by ANSI standards? What would be my goal of continuosly posting it? What if I started another thread, "returning references to local variables is OK", and I showed that for "compiler x it is safe", how long would I get away with it? In general, how long can someone post saying "I've beaten the standard -- I got it to work for such-and-such a compiler" without people who know better turning it into a personal discussion? If you had a chance to take a look, you saw what happened at comp.lang.c++. It turned into polite explanation, to hostility after a few rounds with Mai (who never really ventured in there -- it took myself to post his findings to comp.lang.c++).

Copying non-POD objects without invoking the proper constructor is not defined by the ANSI standard, therefore not guaranteed to work (as is reported by Phillip Nicoletti when run on g++ and PG compilers). Is Mai claiming that it is guaranteed to work? If he is stating this, he should say "yes it is guaranteed to work" or "no, it is not guaranteed to work". At least we can somewhat pin down what his goal is here of posting this stuff. If he is saying that it is guaranteed to work, the experts will disagree, point to line and verse in the standard, and have a good laugh. If he is saying it is not guaranteed to work, at least state where it is not guaranteed to work (i.e. under what conditions, etc.).

As Paul Wendt mentions, every compiler known to man may work with QSort code, but maybe not. All the compilers Mai has may work if you call "delete" on a "new char[]". Does this make it correct code? Mai would think so, the experts know better.

Regards,

Paul McKenzie

Paul,

For all the good and bad things, we're not on comp.lang.c++ or comp.std.c++ here, so I assume many of the people who post here don't necessarily have a copy of the standard. This is one of the reasons why I think this discussion is interesting, as it shows what you can't do with simple memcpy.

Quote:

---

Is Mai claiming that it is guaranteed to work? If he is stating this, he should say "yes it is guaranteed to work" or "no, it is not guaranteed to work". At least we can somewhat pin down what his goal is here of posting this stuff.

---

True, it would be interesting to know. I guess the answer is that it is faster and works in "many" cases. Of course it might be interesting to know what "many" means. But ultimately it is a "useless" discussion because it's not guaranteed by the standard.

What this discussion exemplifies though is that std::sort has pitfalls in its speed.

Nevertheless, I don't like people shouting at each other ;)

Gabriel posted:

Code:

---

class SomeClass
{
public:
        SomeClass():val_(0){self_=this;}
        ~SomeClass(){};
        SomeClass(const SomeClass& src){self_=this; val_=src.val_;}
        SomeClass& operator=(const SomeClass& src){        val_=src.val_; self_=this; return *this;};
        int get_val()const{return self_->val_;}
        void set_val(int i){self_->val_=i;}
private:
          SomeClass *self_;
          int val_;

};

---

Gabriel: Nothing works for every thing, not even the STL. std::sort would not work objects that is not copyable. The problem with your sample code is that your class contains a pointer which points to certain instance of the class, which are being moved around, voiding the pointer.

So this is the sort of object that is NONE-copyable. Yes you have written a copy assignment operator. But the truth is, the object you copied using your copy assignment operator is NOT identical to the original!!!

How come? Try make a copy from an invalid object whose self pointer was corrupted, you will get a valid object nevertheless. An invalid object and a valid object certainly are NOT equivalent. Your copy operator copies an invalid object and turn it into a valid one, so it is NOT making an authentic copy!!!

General speaking, when your class contains a pointer that points to data of the same type, such objects are not exactly copyable, and std::sort may fail on such objects when no meaningful copying can be carried out.

For an example, replace your
SomeClass *self_;
with
SomeClass * pPrevious;

pPrevious would point to the previous element in the vector, or NULL, if it is the first element in the vector, or if it is a stand along object. Try sort the vector with std::sort, then you will find that pPrevious no longer makes sense any more.

In previous discussions I do point out that Qsort is suitable as long as it does not contain data who depend on the location of the object itself. And I point out that when it does, then proper copying of the object itself is impossible and std::sort would not work either.

In the case of Gabriel's example, if we allow the self pointer to be NULL and use that to represent special meanings, for example NULL means the object has not been initialized or has been temporary nullified, etc., then std::sort would NOT sort it properly either.

I didn't know that the an object whose copy constructor or assignment operators didn't make identical copies were non-copyable (or none-copyable?!?). I thought that was the difference between shallow and deep copy?

Also, just a point, but I thought the register keyword was always ignored by visual c++, but it looks like that is the compiler that this was built for...

If I'm wrong, I know I'll find out...

Hi, Anthony:

It is up to me as the author of my class to determine what behaviour the class should manifest when copying.

std::sort respects my design decisions by calling my operators on my class to do what I want. If it can't (because my class is copy-protected) then it will inform me at compile time.

QSort blindly assumes that when I say copy that I meant bitwise copy. If it is wrong, it doesn't tell me at compile time. It doesn't fail gracefully at runtime. It tells me by corrupting my data. Thanks, QSort.

Personally, I don't think that using QSort is worth the potential maintenance nightmares for a minimal (if any at all) performance increase.

Regards,
Bassman

Quote:

---

Originally posted by AnthonyMai
So this is the sort of object that is NONE-copyable. Yes you have written a copy assignment operator. But the truth is, the object you copied using your copy assignment operator is NOT identical to the original!!!

---

Hum, I get it ;) an object is only copyable if it performs a bit-wise copy of itself when the copy constructor is called. Hence Qsort works on all copyable objects and there is no need for std::sort (or even a copy constructor).

Is this what you mean ?

Quote:

---

Hum, I get it an object is only copyable if it performs a bit-wise copy of itself when the copy constructor is called. Hence Qsort works on all copyable objects and there is no need for std::sort (or even a copy constructor).

Is this what you mean ?

---

No, that is not what I mean. I never said that copy must be done bit by bit. ALSO I never said Qsort makes copies bit by bit. Qsort never copies objects, it merely swap objects, in a bit by bit fashion. Because Qsort does not need to make object copies, it is much faster than std::sort when the object is none-trivial to copy.

How you copy an object depends on what you need to copy it for. If you copy it because you need a duplicated object for external use, probably a shallow copy is good enough.

But the copying in std::sort is meant to be copying in order to swap the object. As such, you want to preserve as much as possible how the object looks like, before and after copy. If as the result of std::sort copying and swapping, the objects are change some how, then the next effect is more than just sorting them, you have altered them, which is not acceptable.

Look at Gabriel's copy operator below again, you will see that only one member from the source object is copied, the other member, the self pointer, no matter what it was in the source object, is totally ignored. So at best it is only a partial copy, and the object have been altered during copying, and the copied object and the original does not look the same.

But then again, Gabriel's case is a case where the object can not be appropriately copied. One really should be surprised at the concept that some objects can not be copied. Singleton, for example, can not be copied by its very definition.

And by definition, std::sort can not sort objects that can not be exactly copied. The advantage of Qsort is that even if an object is none-copyable, Qsort may still sort it, since Qsort swap them without making copies.

But just like std::sort can not work on all situations, neither can Qsort. If there is a kind of object that can neither be copied, nor can it even be swapped at all, then Qsort would not work. Certainly if you can not swap the order of two objects, you can not hope to sort them at all, no matter what you use.

Such objects do exists.

Code:

---

class SomeClass
{
public:
        SomeClass():val_(0){self_=this;}
        ~SomeClass(){};
        SomeClass(const SomeClass& src){self_=this; val_=src.val_;}
        SomeClass& operator=(const SomeClass& src){        val_=src.val_; self_=this; return *this;};
        int get_val()const{return self_->val_;}
        void set_val(int i){self_->val_=i;}
private:
          SomeClass *self_;
          int val_;

};

---

Quote:

---

std::sort respects my design decisions by calling my operators on my class to do what I want. If it can't (because my class is copy-protected) then it will inform me at compile time.

QSort blindly assumes that when I say copy that I meant bitwise copy. If it is wrong, it doesn't tell me at compile time. It doesn't fail gracefully at runtime. It tells me by corrupting my data. Thanks, QSort.

---

People still don't get the idea. How many times do I need to repeat that Qsort sorts NOT by making copies, but by simply swapping objects, without making copies of the object.

Never at any moment during Qsort operation that any new object is created or any old one is destroyed. However many objects you have at the beginning of the Qsort, you still have that many during and after Qsort. Nothing is created, nothing is destroyed, nothing is copied. Objects are just swapping positions with each other. So copying is really irrelevant.

On the contrary, std::sort() constantly creates new objects, makes copies, and destroys old objects, in order to sort. Just as you said, if un-fortunately your object is copy protected, std::sort() would not work.

And Qsort would still work, even if the object is copy protected.

Now, how are you supposed to sort an object array who are copy protected?

Quote:

---

Objects are just swapping positions with each other. So copying is really irrelevant. On the contrary, std::sort() constantly creates new objects, makes copies, and destroys old objects, in order to sort

---

So here is the question: Why do you think std::sort does this? Is it because the persons who coded the std::sort are inferior programmers or don't know what they're doing? Why didn't they "just swap objects in memory" as you're doing? Are they dunderheaded junior level coders? Are you doing all of this to show that you're better than all of the C++ programmers and experts who crafted std::sort? What is it? An answer to this question from you will reveal much more than this crud you're posting as your holy grail.

This is really getting ridiculous folks. I'm sorry to say this but it really is. We know what the standard says on non-POD objects, but Mai thinks the standard is something to throw away if something "seems to work". Objects are not required to have their storage in contiguous memory, and experts have shown that objects derived from virtual base classes are in some cases not implemented in contiguous memory.

But again the (rhetorical) question still remains Why has no implementation of std::sort done what Mai's done?

Regards,

Paul McKenzie

Quote:

---

People still don't get the idea. How many times do I need to repeat that Qsort sorts NOT by making copies, but by simply swapping objects, without making copies of the object.

---

Ridiculous. You ARE copying the object. Bit by bit. One object's data ends up in a different memory location from where it was instantiated. That data is a copy of the original object. It is NOT the original object.

Quote:

---

And Qsort would still work, even if the object is copy protected.

---

That's the point. Why would I want to ignore a clear design decision that made an object copy protected? If an object is not initially designed to have copies, you SHOULDN'T MAKE COPIES. std::sort acknowledges this. QSort doesn't.

If you need to revisit the design, revisit the design. Don't try to hack your way around it by using an unstandardized, flawed method.

Quote:

---

Now, how are you supposed to sort an object array who are copy protected?

---

You don't. Sort an array of indices. Sort an array of pointers.

Regards.
Bassman

Quote:

---

Originally posted by Bassman
That's the point. Why would I want to ignore a clear design decision that made an object copy protected? If an object is not initially designed to have copies, you SHOULDN'T MAKE COPIES. std::sort acknowledges this. QSort doesn't.

---

Check up on Phillip Nicoletti's findings on how QSort fails on the g++ and Pacific Group compilers. Mai is trying to dismiss this and look the other way, but I certainly will not let this little tidbit of information get lost in this debate.

Quote:

---

If you need to revisit the design, revisit the design. Don't try to hack your way around it by using an unstandardized, flawed method.

---

Which is the basic flaw of many 'C' coders: If they can't find or don't know a C++ way of doing things, they resort to using something their familiar with, and that is hacking with 'C', regardless if the hack is deemed to be undefined by the language.

This is why it is emphasized that C and C++ are two separate languages. There is the C++ mind, and the 'C' mind. Approaching the concept of classes, algorithms, containers, etc. with a 'C' mind is a dangerous mix. A 'C' programmer is trained that a struct is just some member variables that are copyable. A 'C' programmer uses sizeof(struct whatever) throughout their code, they copy structures all over the place with memcpy's etc. All of this is valid in a 'C' world. For C++, structs (and classes) that are not 'C' structs (i.e. non-POD) take on a different persona. They just can't merely be copied all over the place with memcpy(), or any of the other things that a 'C' coder usually does with a 'C' type structs. The only kind of C++ struct/class that you can use for 'C' type copying are POD structs. This is emphasized in the standard, something that Mai throws away like a used paper towel. Some 'C' programmers understand this and know that C++ has subtelties that 'C' does not come close to having. Others are stubborn and can't grasp this concept. We know which camp Mai falls into.

Regards,

Paul McKenzie

Quote:

---

Originally posted by AnthonyMai:
So this is the sort of object that is NONE-copyable.

---

A non-copyable class is spelled like this in C++:

Code:

---

class non_copyable
{
    /*.....*/
private:
    non_copyable(const non_copyable&);
    non_copyable& operator=(const non_copyable&);
};

---

If 'valid copy' and 'bit-by-bit copy' were synonyms, one would never need to write a copy-ctor or an operator =.

Quote:

---

Originally posted by AnthonyMai:
...if the original challenge do believe it doesn't work for a specific object type on a specific compiler...

---

I have given you an example of a class that breaks Qsort but is handled correctly by std::sort. Philip Nicoletti gave you an example of another class and a compiler where Qsort fails. At lest three or four people posted what the Standard states about copying non-POD types.

Quote:

---

Now, how are you supposed to sort an object array who are copy protected?

---

If a class is copy protected because of a good reason, you will be able to create an array of objects only by using their default ctor. You won't be able to push_back (or equivalent) such objects. The result would in most cases be an array that contains identical objects -- thus no need to sort it.

Assuming that the default ctor creates different objects (by using a static variable, or whatever), you take an array of pointers to the objects and sort that.

A sorting function is of no use without a specification about the objects that can be sorted. std::sort has such a specification. What is the specification of Qsort, in your oppinion? Can you write it down and back it up with the Standard? If not, we're wasting our time.

Quote:

---

If a class is copy protected because of a good reason, you will be able to create an array of objects only by using their default ctor. You won't be able to push_back (or equivalent) such objects. The result would in most cases be an array that contains identical objects -- thus no need to sort it.

---

push_back is a concept in std::vector. An object array is not necessarily a std::vector, it can be a C like array, in which case there is no need to use push_back. And you can allow all kinds of public constructors for the object, except that you would NOT allow a copy constructor or a copy assignment operator.

There are plenty of examples where we can construct a type of object in a number of ways, but you want to prohibit the copying of the object. The reason is each instance of the object is unique and you never ever want to duplicate it.

For example you may have a thread object, each has a unique thread ID, priority and all other related information. Each thread object is certainly unique so you never ever want to duplicate it at any moment. Now, the operating system need to sort these thread objects by priority. How do you do it? It must be sorted without making duplications at any given moment.

Another example is objects which each has a unique sequence number and the sequence number must be unique and continuous. The object can be constructed at different spots, at different times, using a number of different constructor, but each of these constructors would all call a base class constructor which calls a global sequence number generator to fetch and assign the sequence number properly.

Now I want to sort these objects, according to their individual sequence number, or according to other sorting criterials. Mean while I do NOT want to scramble their sequence numbers or disturb the global sequence number generator. How would you do it? Obviously you can NOT call any constructor at all if you can not disturb the sequence number generator, so you really can't sort using std::sort.

And under this situation Qsort would work better than std::sort, because it swaps objects without actually making any copies.

Quote:

---

Assuming that the default ctor creates different objects (by using a static variable, or whatever), you take an array of pointers to the objects and sort that.

---

There will be cases you are not satisfied with an indirect index array, but you want to sort the objects themselves directly.

Quote:

---

A sorting function is of no use without a specification about the objects that can be sorted. std::sort has such a specification. What is the specification of Qsort, in your oppinion? Can you write it down and back it up with the Standard? If not, we're wasting our time.

---

std::sort can only sort objects that an appropriate copy operation can be carried out, and is not prohibited to carry out. Qsort does not have such limitation. But Qsort has its own limitation, an object must not have pointers (explicit or hidden) that directly points to itself or members within itself. By having such pointers once the object moves in the memory it is no longer valid.

Quote:

---

There will be cases you are not satisfied with an indirect index array, but you want to sort the objects themselves directly.

---

I can't think of any such example. Pointers to objects avoid slicing. Arrays and polymorphic objects just don't mix.

Quote:

---

But Qsort has its own limitation, an object must not have pointers (explicit or hidden) that directly points to itself or members within itself.

---

... and must not be used on non-POD types.

Jeff

Nice conversation.

Although some of you are completely frustrated, it really helps me to understand the C++ concepts.

In the end, dinosaurs that can't accept change die a horrible death.

Thanks for these boards. ;)