STL Vector problems

jwbarton:
Did I say that compiler never inlines any thing even if you declare inline? I never said that.

All I said is those one zillion "inline" keyword you find in STL source code, none of them could cause the compiler to cause any of the STL function to be actually inlined. NONE.

In you example, the operator() is a function YOU defined (not STL!!!) with inline, and compiler choose to inline them. However the fact remains that NONE of the STL functions are actually inlined. What you saw inlined was your own operator(), which was not from STL.

Quote:

---

Originally posted by Graham

OK, not 670% - I concede defeat on that, since my system is obviously not the same a Scott Meyers'. But 410% is still pretty impressive.

---

Graham, here is a link to the C++ User's Jornal article on std::sort. At the end, it describes qsort().

http://www.cuj.com/experts/1908/aust...?topic=experts

In the article he properly states to stay away from qsort for non-trivial classes. I posted code that supposedly works, but now I have to rethink using the qsort on a class with std::string. I don't think I would have been so lucky if the strings were reference-counted and I used qsort().

BTW, here are the authors credentials:

Quote:

---

Matt Austern is the author of Generic Programming and the STL and the chair of the C++ standardization committee’s library working group. He works at AT&T Labs — Research and can be contacted at [email protected].

---

Also, another advantage of std::sort that you didn't point out: qsort() does not work on a deque<T>. std::sort() works for vectors and deques without any code changes. Take the code you provided, replace the vector<> with deque<>, and the qsort not only fails, it GPF's because it assumes everything is in contiguos memory. The std::sort() works flawlessly since it doesn't assume how the data is laid out or what structure you use, just as long as random access iterators are provided for the first and last element of std::sort (and of course, the optional functor/function pointer).

Of course, you could write your own qsort() to sort a deque, but let me tell you, it isn't easy. Even though list::sort is slightly different in terms of syntax, it also is trivial to change to list::sort if you're sorting a list<T>. I guess you could write a qsort() for list<T> also. ;)

I see that antother thread was started, but why comment on the code posted there? When a faster std::sort is posted (with the same functionality as std::sort as described above), myself and many other C++ programmers will take notice. Heck, I would even recommend sending it to PJ Plauger or even Boris at www.stlport.org. They would jump at the chance of including it in their libraries and may pay handsomely (Boris must have gotten something from Inprise when they adopted his library, so he could be rolling in dough :))

This reminds me of a thread started on comp.lang.c++ a few months ago. Someone wrote stating that he had a "faster string than std::string". He tried to prove this, and yes, his version was faster in some cases, but then the pros over there exercised his class in ways he didn't imagine. It failed some tests, it wasn't suitable in others, had bugs, and in a real world environment, failed miserably on a lot of timing tests. The interface wasn't std::string, so that also didn't work well. It wasn't based on any kind of "traits" so that wide character strings were supported, etc. etc. After a few weeks of pleading his case (and losing), he gave up. You may be able to get the thread if you do a Google search in the newsgroups. It will definitely remind you of this thread.

Regards,

Paul McKenzie

Quote:

---

Originally posted by Anthony Mai:

But the fact still remains that Scott Meyers is WRONG in asserting that inlining makes std::sort faster. I dumped both the release version and debug version compiled code to assembly. Guess what:
Not a single inline function is being actually inlined.

---

Quote:

---

Originally posted by Anthony Mai:

In you example, the operator() is a function YOU defined (not STL!!!) with inline, and compiler choose to inline them. However the fact remains that NONE of the STL functions are actually inlined. What you saw inlined was your own operator(), which was not from STL.

---

So which is it: "not a single inline function is being inlined", or "none of the STL inline functions is being inlined"?

Paul: thanks for the link - I'll check it out later.

Graham:
That's called "taking words out of context". You are taking my words out of context to distort what I mean.
Putting my words back to the context where I said them. It is very clear that I was discussing about the "inline" keywords in STL. I meant to say "Not a single STL function is being inlined".
It's a typo that I dropped the word STL. Big deal!!!
(Oh, OK, I am sorry, Graham, what I meant to say is "No big deal". I dropped a "No", just in case you want to nitpick again.)

... A typo that changed the entire meaning of the phrase. Unfortunately, I had my telepathy turned off at the time.

However, since you were also berating Scott Meyers' explanation of the speed up being due to inlining, and since Scott Meyers' was talking about all the inlining that could happen (including the supplied functor, not just the STL bits), I naturally made the connection. In future I will make sure that I search for hidden text, especially for words that aren't there.

This is in reply to Anthony Mai:

My code example was simply to refute the following claim by you:

Quote of Anthony Mai:

Quote:

---

But the fact still remains that Scott Meyers is WRONG in asserting that inlining makes std::sort faster. I dumped both the release version and debug version compiled code to assembly. Guess what:
Not a single inline function is being actually inlined.

---

When Scott Meyers explains why function objects will often work better than functions (in Item 46 of Effective STL), he is referring to the inlining of operator().

Quote from Effective STL (Item 46) by Scott Meyers:

Quote:

---

The explanation for this behavior is simple: inlining. If a function object's operator() function has been declared inline (either explicitly via inline or implicitly by defining it in its class definition), the body of that function is available to compilers, and most compilers will happily inline that function during template instantiation of the called algorithm.

---

Scott Meyers never says that the sort() routine itself will be inlined, but instead says that the calls to the operator() may be inlined (they don't have to be, but most compilers will inline this function). From my own experiments, I have seen that Visual C++ will inline this call unless the routine becomes too complicated.

John