The fear of the misterious

Jeff:
OK, so Paul pulled a fast one. A couple of weeks ago when I compare index sorting using qsort(), with dicret object sorting using std::sort(), Paul accused me of "pulling a fast one"
Now I am really talking about direct object sorting using Qsort, and Paul is talking about index sorting using std::sort(). Paul is pulling a fast one this time. Fine with me. We are just getting even.
But still comparing index sorting with direct object sorting is comparing apple with orange.
I know Paul is intelligent and can pull an intelligent one, but we are not competing programmer intelligence here. We are letting Qsort() and std::sort() competing here. Let them both sorting objects directly, OK? In such fair competition, std::sort() is clearly defeated by a large margin.
Don't you agree, at least in principle, sorting is an operating that moves objects around so they line up in certain order? Hence in principle, it should not be necessary to create new object or delete old ones, right?
std::sort simply can not move objects without detroying them and re-create them, repeatedly. This is teleportation: Basically you kill some one right on spot, and then replicate the person in a different city, in order to transport him from one city to another. It just sound weird to me.

Anthony,

Yes, I agree in principal that to sort something, you should not have to recreate items. You should be able to shuffle things around and that's it. Unfortunately, the C++ standard does not guarantee that this will work. This is an important point, and should not be ignored no matter unintuitive it may be.

Both std::sort and Q(q)sort have drawbacks. With std::sort, you have to choose your containers carefully. You need to be aware of what is happening or it will take a long time to sort.

Likewise, with Q(q)sort, you have to choose your containers carefully. If you choose the wrong container, the program will crash. Additionally, this will likely fail with certain compilers, which is of no fault of the compiler, but a fault with the source code.

It is more likely, at least in my experience, that a collection of objects of non-trivial classes will actually be a collection of pointers to those objects. In such cases, std::sort is faster.

In all cases, it is safer.

Jeff

There is still the issue of undefined behavior. As of the last message, the Pacific Group compiler did not sort correctly using qsort(), while std::sort does.

You can't in good faith comment on anything until, at the very least, you investigate why it doesn't work for this compiler. So as long as Phillip can't get it to work, what's the point? Everyone has been trying to tell you this, but you didn't want to listen.

As I pointed out std::sort has worked flawlessly on every compiler tried, and it is guaranteed by the ANSI/ISO standard to work the way it's documented to work. If it doesn't, then it is a bug in the implementation and the compiler vendor is required to fix it, if not the implementation is not ANSI/ISO C++ standard.

There is no guarantee that qsort() works with non-POD types by the ANSI/ISO C++ standard. If qsort doesn't work for a non-POD type, the compiler vendor will tell you to "take a hike" if you tried to report a bug concerning trying to sort a non-POD class with qsort().

Regards,

Paul McKenzie

Here's the problem, Anthony: the creators of std::sort had to instill in it the knowledge of objects [ie: copy constructors]. Why? The reason is that you can't directly copy a class's memory contents wholesale or "bad things" will happen. These people weren't idiots; they would have just used a memcpy() if they could have.

What you guys are arguing about isn't even what sort algorithm is fastest; AnthonyMai is merely stating the obvious: copy constructors can cost you performance if they're used superfluously. Hopefully, most people won't HAVE objects that allocate 4k of memory on the heap; if people DO have these types of objects, then hopefully they'll performance into consideration if they do anything like sorting. The problem's not std::sort; it's the fact that we're using copy constructors. Keep in mind that the "default copy constructor" in C++ [and C if you think about is] is the equivalent of a memcpy().

So ... Paul McKenzie's working with what he's got; he knows that copy constructors are costly ... and he uses the tools available to obtain fast sorting. You're right, Mai; std::sort() is slower than qsort() if copy constructors are costly. Unfortunately, qsort() potentially won't sort things properly. Of course you won't believe it until you see it [and even then I'm sure you'll come up with something]. The point is that McKenzie [and any performance-concious C++ programmer] knows that copy constructors can be a bottleneck if they're used too frequently ... and he can use the language to meet his goals. You don't want to use the language to meet your goals; you want to use what you already know in order meet your goals.

I think that maybe the tact of seeing this from the compiler vendor's point of view is the best way to sum this all up

Envision these phone calls to tech support:

Quote:

---

--------------------------------------------------
Phone Call 1:

Support: "Hello, Pacific Group C++ tech support. How may we help you".

C++ Coder: "I have a problem with your implementation of std::sort. I sent you an email with the code attached. I'm attempting to sort this class, but std::sort is not working".

Support: "Yes, we saw your e-mail, and according to ANSI C++ specs, it should work. We'll report this to the engineers right away."

C++ Coder: "Thank you"
-------------------------------------------------
Phone Call 2:

Support: "Hello, Pacific Group C++ tech support. How may we help you".

C++ Coder: "I have a problem with your implementation of qsort. I sent you an email with the code attached. I'm attempting to sort this class, but qsort is not working".

Support: "Yes, we saw your e-mail, and according to ANSI C++ specs, the standard library qsort() is not guaranteed to sort these types of classes."

C++ Coder: "Yes, but, it works on VC++..."

Support: "Sorry sir, but qsort is not required to sort these types of classes correctly. If you have a problem with qsort sorting integers, doubles, etc. then we will fix it right away."

C++ Coder: "What do you mean? Are you stupid?"

Support: "Sir, if you have a complaint, I can have other engineers explain that qsort is not guaranteed to work correctly for these classes as the ANSI C++ specification makes no guarantees that qsort work for these classes."

C++ Coder: "What do you mean? I can't believe this! You people there know nothing about...Hello...Hello.."
--------------------------------------------------

---

So the bottom line is whether the compiler vendor is required to fix qsort if it can't sort a non-POD class for the compiler to be compliant. The answer is an emphatic no.

Is the vendor required to fix a problem with std::sort if it doesn't follow ANSI specs, and remain to have a standard's conforming compiler? Yes.

Regards,

Paul McKenzie

Quote:

---

Originally posted by AnthonyMai
you do not know what you think you know.

---

Ok fine, but i havent said any time "i dont need to read this or that or go here or there and no one has responsiblity to tell me what should i do" . If someone advice me then i surely read that book and go to that side, just like Paul advice me to read one good book of STL.

And now only one program related to your questions of static. Hope it shows what i want to say.

Code:

---

#include <iostream>
using namespace std;

class C
{
public:
        static void StaticFun(C* pC)
        {
                pC->NonStaticFun();
        }

        void NonStaticFun()
        {
                cout << "Non Static Fun" << endl;
        }
};

int main()
{
        C objC;
        C::StaticFun(&objC);
        return 0;
}

---

I used this type of techniques lots of time when using threading in VC where the thread function need void pointer and i pass the address of the class and then access other data from that pointer. Of course that thread function is static in my that class, because it hase to be.

Quote:

---

Originally posted by AnthonyMai
You are lucky to have it work on VC6 because in your virtual function you are not touching any class data member.

---

Thats what i want to said, this code runs on VC6 because i explore the memory layout of VC6, but it doesnt mean it runs on other compiler. Why? Because it is not standard, and if it is standard then it should be run on every plateform. And that artical disuss ATL not C++ so i discuss those techniques which ATL use internally.

Quote:

---

Originally posted by AnthonyMai
There CAN be different ways of v-table implementation.

---

Finally you accept this, thats what i want to say, v-table is not standard.

Quote:

---

Originally posted by AnthonyMai
no matter how v-table is implemented, it would have to be put into the same chunk of memory where all other class data members sit

---

Excuse me, v-ptr is exists with class data. (In case of VC and most of other compiler, it is not standard too). v-table is not exists with class data. I think again take a look at Part 1 and Part 2 where i show this with small program on VC.

Quote:

---

Originally posted by AnthonyMai
There is just no reasonable way to put data pertaining to a class's state into two different chunks of memory. And I have not seen any implementation does it in such un-thinkable way.

---

OK, but what about output of this program?

Code:

---

#include <iostream>
using namespace std;
class C
{
        char ch1;
        int i;
        char ch2;
};

int main()
{
        cout << sizeof(C) << endl;
        return 0;
}

---

It should be 6, but in VC and on gcc 2.96 Rad Hat Linux 7.0 it is 12. Now change it little bit.

Code:

---

#include <iostream>
using namespace std;
#pragma pack(1)
class C
{
        char ch1;
        int i;
        char ch2;
};

int main()
{
        cout << sizeof(C) << endl;
        return 0;
}

---

I m sure you know what is pragma pack.

I still dont know why you compare algorithm with specification. qsort is algorithm and std::sort is an specification. And if you really want to compare algorithm analysis take a look at


The Art of Computer programming vol 3
by Doneld E Knuth


It seem you consider all

Graham
Paul McKenzie
jfaust
Philip Nicoletti
Ruslan Abdikeev

of them wrong although they give so solid logical reasong. Or may be you want to create the longest thread on codeguru. Ok if all of us are wrong then why not directly mail to your code to Bjarne Stroustrup, scott Meyrs, Herb Sutter, Stan Lippman or Andrew Koenig, Douglas Schmidt, Barbra Moo, Andrei Alexandrescu, Rob Murrey etc.

At least write and artical on CUJ on this, and gain fame.

Hope to here yoo on comp.lang.c++, comp.lang.c++.moderated and CUJ soon.

Zeehan:
With due respects, I know pragma pack and the concept of byte align long time before I started my first job. You don't need to teach me that. Also, you do need to read my previous post carefully, instead of taking it out of context. I quote it here again:

Quote:

---

But I made a reasonable, and sensible assumption that no matter how v-table is implemented, it would have to be put into the same chunk of memory where all other class data members sit, not counting the few bytes gap intentionally un-used to make class data members properly byte aligned.

There is just no reasonable way to put data pertaining to a class's state into two different chunks of memory. And I have not seen any implementation does it in such un-thinkable way.

---

Didn't I meantion the word "byte aligned"? Those few bytes are intentionally left there and they are un-used. Actually on MIPS based systems, trying to access none-byte-aligned data would cause a system fault.

OK, there is this little detail v-ptr and v-table. v-table is a static table and v-ptr is part of the class data members. v-ptr points to v-table. That doesn't change my argument. v-ptr still sticks to the rest of class data members, as long as v-ptr's are copied together with the rest of data member to a new memory location, it will work just fine.

It seems that all these people

Graham
Paul McKenzie
jfaust
Philip Nicoletti
Ruslan Abdikeev
and you

are trying in vain to proving me wrong by pointing out the obvious: i.e., my use of Qsort() does not agree with the C++ standard so it is wrong.

Such logic is frauded. I gladly accept that my method does NOT comply with the C++ standard. But I fully reject that it is wrong.

A standard, any standard, is neither right nor wrong. 8.5"x11" paper size is an American standard. So is 8.5"x11" right or wrong? Other country may be using a different size, are they right or wrong?

You can say a standard is good or bad. though good or bad is opinion oriented. You can not say a standard is right or wrong. AND YOU CAN NOT SAY A PIECE OF CODE IS RIGHT OR WRONG, BASED ON WHETHER IT COMPLY WITH ANSI C++ STANDARD OR NOT.

Technically ANSI C++ standard is not even an international standard. The A in ANSI stands for American. Practically, though we all agree it is an international standard. But again there is no right or wrong in a standard, however wide that standard is applied.

You are entitled to say your opinion whether a piece of code is good or bad. But you really can't say its right or wrong based on standard compliance. If my code works on a specific platform, then my code is right for that specific platform. If my code does not work on a specific platform, then it is wrong for that platform.

A piece of fully ANSI C++ compliant STL based code would not work on an embedded system, and I can say it is wrong for that platform. My plain C code works, and I can say it is right.

I hope that clears things up. If you guys try to prove that my method is none-ANSI C++ compliant. Save it. I never disagree that it is indeed none-compliant.

If you guys are trying to prove me WRONG, by citing clauses from the ANSI C++ standard or citing what Plaugher said. Save it. The logic simply is fauded. None-compliant does not equal to wrong in logical concept.

I explained my method, explained its philosophy, and posted sample code that every one can test. My code works on a number of different platforms, so it is right, at least for the platforms that I tested.

If you try to prove me wrong by citing that on a specific combination of a small potato compiler and an un-common platform, my code does not work. Also save it. You can tell me whether your STL based code would work on my VCR, on my cell phone, on my GPS navigation system, or on the microwave stove in my kitchen.

Does any STL code work for any of the systems I cited? NO! All those are embedded systems. None of them support STL. Most of them support some sort of stripped down C++ but very few embedded system support STL at all.

I can cite much more systems that doesn't care about STL at all, than you guys can cite systems that are ANSI C++ compliant.

If you really want portability, maintainability, platform independent, stay away from STL, used the minimum denominator part of C++. That's my opinion. And that is also the opinion of a large group of people. Ever heard of the Embedded C++ Standard?

Again, stop wasting time trying to prove me wrong by citing clauses from the writting of the ANSI C++ standard. If you are trying to prove I am not standard compliant, you have made your point already. If you are trying to say none-compliance equals wrong, you are wasting you time on a frauded logic.

Quote:

---

So is 8.5"x11" right or wrong

---

Right or wrong depending on how you look at it. A non-standard sized piece of paper is not guaranteed to work as a standard sized piece of paper. It may or may not work in a printer, fax, shredder, envelope, folder, binder, etc. Similarly your non-standard code is not guaranteed to work with any given compiler.

Wait, I just said I was done arguing this. I just can't resist shoving an argument back at the person.

OK, now I'm really done. No, really...

Jeff

Jeff:

I can't help laughing when seeing your last comment on standard or none-standar paper. It just amazes me.

Thow away all your C++ books out of your window. Obviously they are wrong and they don't work because they are not printed on standard 8.5"x11" papers. NONE of them. :-)

Look, the world of paper is much bigger than 8.5x11. And the world of computing is MUCH bigger than C++ STL. OK? A group of people come along to express their philosophy of the art of programming, and comes up to a unified opinion, which forms the basis of ANSI C++. Needlessly saying, there is a huge group of people agreeing with that philisophy.

But that doesn't prevent a different group of people who believes something else, practice something differently, and even form their own standard. It's perfect OK if they get their systems work in the way they desire. It's a free world, right?

I feel we are falling into a religious fight now.

Quote:

---

Graham
Paul McKenzie
jfaust
Philip Nicoletti
Ruslan Abdikeev
and you

are trying in vain to proving me wrong by pointing out the obvious: i.e., my use of Qsort() does not agree with the C++ standard so it is wrong.

---

Not in vain, but very easily proven wrong.

Just you mentioning other compilers as "small potatoes", just because they can't run your "code", just shows more arrogance on your part. These "Small Potatoes (© 2002)" compilers ran std::sort flawlessly. If they barf on your code, they still are working -- it is your code that is faulty. Compiler vendors are concentrating on getting their compilers up to ANSI/ISO C++ standard, are they wasting their time? And BTW, Stroustrup is Danish not American. Tell him that ANSI only means American.

You mention embedded systems. If an embedded system compiler doesn't support STL, then it isn't a conforming ANSI C++ compiler. This forum is an ANSI C++ forum. C++ knows nothing about embedded systems -- it is just a general purpose language defined by the ANSI/ISO C++ standard. Like it or leave it.

And as to you saying that "it works on 'x' platform", unless you can get a guarantee from the compiler vendor that their non-ANSI compliant behavior will not change from version to version, then and only then can you make the claim that "it will work on 'x' platform". A classic example is writing to a const char * for the VC++ series of compilers. You can do it in V5, but V6 bombs out. Same platform, right? Different results. Undefined behavior.

No, myself and every other C++ programmer worth anything will stick with std::sort. There is no need for further comment.

Regards,

Paul McKenzie

Quote:

---

Originally posted by jfaust
Similarly your non-standard code is not guaranteed to work with any given compiler.

---

It's not even guaranteed to work on these "embedded" compilers he keeps touting, even ones that don't have STL.

There is nothing stopping someone from writing a std::sort equivalent for these embedded C++ compilers (for any compiler for that matter), that is ANSI compliant (doesn't invoke undefined behavior). Heck, Boris Fomitchev at STLPort has done it. His STLPort is specifically aimed at compilers that don't have STL and/or their library is not ANSI compliant.

A responsible C++ expert who has to deal with a compiler that may not have STL, or may not even have templates would have done the following steps:

a) research how the STL sort works for classes. Understand the algorithms used (i.e. pick up a version of STLPort or the SGI implementation)

b) Adapt the code to work for their compiler. If it supports templates, then templatize the code. If it doesn't unroll the code, and make it "skeleton" code, so (as an example) in the future, you just plug in the desired data type into the skeleton. While doing all this, adhering to the ANSI C++ specs.

c) Fine tune any other parts that could be fine-tuned, again adhering to ANSI C++ specs.

The person described above would

a) have a version of sort that works correctly for non-POD types

b) can guarantee that their code will work on *any* compiler (i.e. no undefined behavior) including embedded, Small Potatoes (© 2002), VC++, and ones the author knows nothing about. If it doesn't work on a particular compiler (bugs not withstanding), it is the compiler implementation that is faulty, not the code.

c) Make it around the lecture circuit and post articles on how to use the code efficiently with various class types.

d) Get acknowledged by Stroustrup, Meyers, et. al. in their latest books and articles.

Regards,

Paul McKenzie

Quote:

---

I can't help laughing when seeing your last comment on standard or none-standar paper. It just amazes me.
Thow away all your C++ books out of your window. Obviously they are wrong and they don't work because they are not printed on standard 8.5"x11" papers. NONE of them. :-)

---

The examples you gave for paper were made for a specific purpose, and not made for general purpose use. They may not work for general purpose.

Similarly, you've created a method that works for specific compilers, but may not work in general. At the same time, you're trying to pass it off as a general purpose method. Sorry, it's not.

So laugh away and be amazed, C boy, the comparison holds.

Jeff

Quote:

---

If you really want portability, maintainability, platform independent, stay away from STL, used the minimum denominator part of C++. That's my opinion. And that is also the opinion of a large group of people. Ever heard of the Embedded C++ Standard?

---

Please cite name and document where these "groups of people" have stated this. Everyone else is tired of citing you names, documents and periodicals, now it should be your turn. And this is not the "Embedded C++ Forum". This forum discusses ANSI C++, in its fullest glory, STL, templates, exception handling, and all. If you have a problem with that, go ask the moderator to start an Embedded C++ Forum. And for those who want to know what the inventor of the C++ language thinks about EC++, here it is:

http://www.research.att.com/~bs/bs_faq.html#EC++

Also, your problem has nothing to do with STL. It is that you are copying non-POD objects using behavior that's undefined. This doesn't matter about embedded or non-embedded. Your code could blow to bits an embedded C++ compiler, just as it is now blowing up the Pacific Group compiler.

Regards,

Paul McKenzie

Paul:

With due respect, The name of this board does not say "ANSI", nor does it say "standard" nor does it say "STL". So this board is for the discussing of all C++ topics, including all flavor and taste of C++, not limiting to ANSI C++ standard and STL.

Also as you pointed out a long time ago, legacy C functions, stuff like memcpy(), strcmp(), etc. are also included as part of the standard C++ library. So it is totally a legitimate topic to discuss usage of legacy C functions in the context of C++.

Please read what the subject of this forum is:

Quote:

---

Ask or answer C++ questions not related to Visual C++. This includes Console programming, Linux programming, or general ANSI C++

---

You don't like templates, exception handling, standard library, fine. Whether you like it or not, they are part of ANSI C++. ANSI C++ is defined by the ANSI ISO/IEC 14882 standard document. In that document describes what has been explained to you by others, both on CodeGuru and comp.lang.c++ as to why your code is faulty.

And yes, those functions you mentioned exist in the C++ library. That doesn't mean they can be used any old place you feel like using them.

Regards,

Paul McKenzie