STL Vector problems

[Franz]

I have two questions :confused:

1.How can I append a vector to the other vector?

2.

std::vector<int*> myvector;

int *pNum = new int;
*pNum = 4;
myvector.push_back(pNum);

*pNum = new int;
*pNum = 3;
myvector.push_back(pNum);

Now, I want to sort myvector. Therefore, the sequence will become 3, 4. I want to use stl sort function. How can I use that?


Any replies will be appreciated ;)

[zdf]

#include <vector>
#include <algorithm>

using namespace std;

int main()
{
vector<int> v1, v2;

// ...

// append v2 to v1
v1.insert(v1.end(), v2.begin(), v2.end() );

// sort v1
sort( v1.begin(), v1.end() );

//...

return 0;
}

Regards,

[Graham]

Correction to the sort solution, since the vector is holding pointers to int, and the OP seems to want it sorted on the int's value:

template <typename T>
struct DerefLess : public std::binary_function<const T*, const T*, bool>
{
bool operator()(const T* lhs, const T* rhs) {return *lhs < *rhs;}
};

// ....

std::sort(myvector.begin(), myvector.end(), DerefLess<int>());

[Anthony Mai]

Further correction to Graham's solution.

Be extremely careful with the third parameter when you use the three parameter version of

void std::sort(RanIt first, RanIt last, Pred pr);

The third parameter, when it is a class object, gets copied over and over again underneath the sort, when the object is more than a few bytes big, the copying takes so much time that it brings the std::sort totally down to its knee crawing when you are sorting a significant amount of data.

The you know whom gave an exellent example of that behavior when he feeded std::sort()'s third parameter with a class object that contains a whole copy of the vector. The result is a sort that could take a few minutes now takes days or even weeks.

In Graham's code, I do not see the need to inherit DerefLess from any base class to bloat the size of the object. You can use the smallest object possible, i.e., an empty struct DerefLess which inherit from nothing and contains just the operator (). This way the size of the object is just one byte (as discussed some where else, sizeof of an empty object is defined as 1).

Further, the third parameter doesn't have to be a class/struct object at all. In cases where when given the two elements to compare, there is still not enough information to compare them, a class object will be needed since the class object contains additional information needed to carry out the comparison. For example, when the elements to sort is merely an index, std::sort needs to know what exactly does the index index into, to do the comparison. The class object contains that information.

In our case, additional information is not needed, given two integer pointers, we can readily copare the two integers they point to, without help from any additional info. That's why our
DerefLess object can be an empty object.

Empty object never contains any information so it should never be used. So in this case we can simply use a plain old global function pointer instead:

// This is a global function, not a class member function
bool DerefLess2(const int* lhs, const int* rhs)
{
return *lhs < *rhs;
}

//...
std::sort(myvector.begin(), myvector.end(), DerefLess);

[jfaust]

I would wager that creating using the class is at least as fast as the global method. The compiler should be able to interpret everything and reduce it to the command "return *lhs < *rhs;", invoking no function calls.

Jeff

[Franz]

Thanks for your help~~:D

[jfaust]

Actually, I'm not so sure of what gets stripped away by the compiler. The copy constructor for this class is called quite often. With everything inlined, will this be optimized away?

Jeff

[Anthony Mai]

Jeff:

The passing of the third parameter of std::sort() is specified by the template. That can NOT be inlined or ommitted. The compiler has to do structly what the template tells it to do. The template tells it to construct a class object and pass it in as a third parameter, and the compiler will do exactly just that: call the default constructor and then push the object onto the stack.

The inline keyword does not always leads to the function actually being inlines. Many times it never gets inlined. Template source code contain no less than a zillion inline keywords every where in STL.

It's all nonsense!

How would you suppose a compiler implement the inline when you are talking inline functions call inline functions which calls another inline function, sometimes in a recursive way. If you inline them, where do the compiler find memory space to store all those local variables of all those nested function calls? In the case where recursion happens, the compiler does NOT even know how deep a call stack it will be and many local variables it will end up needing to store!!!

By using templates, basically the compiler's hands are tied and it can not do many things that it could have done to optimize. There is only so much a compiler can do and you can't expect miracle from it.

[Graham]

The following quotes all come from "Effective STL". These are Scott Meyers' words, not mine.

From Item 46:
... It may thus come as a surprise to learn that passing STL function objects - objects masquerading as functions - to algorithms typically yields code that is more efficient than passing real functions.

... 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. ... As a result, sort contains zero function calls and compilers are able to perform optimizations that on this call-free code that are otherwise not usually attempted.

... This situation is different for the call to sort using [a real function]. To see how it's different, we must recall that there's no such thing as passing a function as a parameter to another function. When we try to pass a function as a parameter, compiloers silently convert the function into a pointer to that function, and it's the pointer we actually pass. ... each time [the real function is] used inside sort, compilers make an indirect function call - a call through a pointer. Most compilers won't try to inline calls to functions that are invoked through function pointers, even if, as in this example, such functions have been declared inline and the optimization appears to be straightforward. ...
The fact that function pointer parameters inhibit inlining explains an observation that long-time C programmers often find hard to believe: C++'s sort virtually always embarrasses C's qsort when it comes to speed. ... In my tests on a vector of a million doubles, it ran up to 670% faster...
Please address all comments to Scott Meyers, not to me.

As for deriving the functor from std::binary_function, all that does is make a few typedefs available and increases the reusability of the functor. I hardly think that three typedefs constitutes "code bloat".

[jfaust]

But the functor is passed in by value, and sort itself continues to pass it around by value. Inlining works in STL largely because of the lack of many virtual methods. Constructors are always virtual, so I don't think they can be inlined. Since the functor is passed around by value, which invokes the copy constructor, I don't see how a call can be avoided.

Is my reasoning correct? My concern is purely academic, as I would use the functor regardless.

Jeff

[Paul McKenzie]

Also from "The C++ Standard Library - A Tutorial and Reference" by Nicolai Josuttis:

Section 5.9, "Function Objects", p. 127
Function objects are usually faster than ordinary functions.
The concept of templates usually allows better optimization because more details are defined at compile time.
Thus, passing function objects instead of ordinary functions often results in better performance.
The emphasis at the first line is the author's, not mine.

Address all follow-ups to Nicolai Josuttis. His email is libbook@josuttis.com, and he will be happy to hear any rebuttals.

Regards,

Paul McKenzie

[Graham]

"Constructors are always virtual"? I don't think so. Constructors are never virtual - that's why we create virtual Clone() amd Create() functions (also known colloquially as "virtual constructors"). I'm only passing on the words of Scott Meyers, and I think he knows a thing or two about the language.

[Graham]

Also, what's all this "passing it around" business? Where in the description of std::sort does it say that sort has to make multiple copies of any predicate passed to it?

[jfaust]

I misinterpreted my test results. There were 3 items in my vector and the copy constructor was called 3 times. I jumped to the assumption that the number of calls was linked with the size of the vector.

I added a few more items and the copy constructor calls remained at 3.

virtual constructors?
I guess virtual is the wrong word. But each class's constructor is called on construction, which to me is closer to the behavior of a virtual method than a regular method call. My real question is, "Can constructors be inlined?"

Jeff

[Graham]

Or, more to the point, can a "do-nothing" constructor (supplied by the compiler) be optimised away? Probably, yes. Don't forget, by defining a constructor in order to track it, you've moved the goalposts as far as optimisation is concerned.

[Chambers]

"But each class's constructor is called on construction, which to me is closer to the behavior of a virtual method than a regular method call"

By adding the virtual keyword before a function you are telling the compiler that a derived class may have an overiding function that should be called in place of the abstract classes function. In the case of a pure virtual function (= 0 on end) the derived class must have an overiding function or the compiler will throw a linker error. It is possible to have inline virtual functions, but I understand that compile time increases over normal inline functions. As Graham said the constructor is never virtual because the base class must always be created (if you use the watch on an object of a derived class, when debugging, you will see the inherited classes appear as an object of the derived class - as opposed to actually absorbing the functions and variables into the this pointer of the derived object).

I'm not really sure what your trying to say, but to me the constructor is closer to a regular function call since a more abstract function cannot be used instead (correct me if I'm wrong), for the objects construction. To me it is like a regular function, because, like all regular functions, they are detailed wholly within that classes scope and no other.

Anyway, back to you guys, I'm finding this whole topic of conversation very interesting.

Alan.

[jfaust]

And another argument against myself: constructors don' t behave polymorphically.

I guess constructors are really different beasts altogether. Calling a constructor calls a string of methods starting with the most-base constructor down to the most derived constructor.

It seams that this calling sequence is known at compile time, and therefor could be inlined somewhat. I don't know--there's probably other issues that get in the way.

Thanks for the clarifications,

Jeff

[Graham]

There was a discussion about ctors on comp.lang.c++.moderated, prompted by the question "why don't ctors have return values?" The general consensus seemed to be that ctors (and dtors) are "special" - they're not functions (in the general sense) since they obey all sorts of special rules. And because they don't have a return type. Their purpose is to construct an object: if the object doesn't need construction (like the functor above), the compiler ought to be at liberty to optimise the ctor away (unless you do anything to try to see how often the ctor is being called, in which case, it's obliged to keep it and call it). A good reason for not defining a ctor if the compiler-generated one is sufficient, I suppose.

[Anthony Mai]

I am not going to contact Scott Meyers or Nicolai Josuttis or any of a couple of million guy out of this planet of 6 billion population, to discuss any issue. I don't have time to do so, more than they have time to come to me to discuss them. (They are welcome to do so, though)

But, look, the fact is it is plain wrong to assume that compiler can inline any thing as long as you declare it as inline, especially when it comes to STL. And thank God, virtually NONE of the STL stuff are actually inlined, otherwise we will be seeing simple programs written in STL becomes so big they could easily fill up a whole hard disk, due to the function inlining.

There mere fact that although most STL based applications are bloatware, they are not yet bloated in any ridicurious way, says to the truth that virtually nothing in STL has actually been inlined.

Gosh, how many times have I read on this board of the pro-STL guys complaining this and that compiler could not compile a piece of template code correctly? Templates are so complicated to implement that most compilers can't implement them correctly. How could you expect any compiler do a smart job in inlining template functions?

I am not convinced of Scott Meyers's claim that his test result show std::sort faster than qsort() by 670%. Show me the code. Paul tried to show me once how std::sort() can sort as fast as qsort, but his example failed him miserably by showing a speed many orders of magnitude slower.

If any one can show me a piece of code that shows std::sort() is faster than qsort() in sorting the same thing, I'd like to see it here.

Finally, std::sort() does use recursive function calls. So any inlining is impossible even in theory. Here is the sorce code, re-written in a moreadable fashion:

template<class _RI, class _Ty, class _Pr>
inline void _Sort
(
_RI _F,
_RI _L,
_Pr _P,
_Ty *
)
{
for (; _SORT_MAX < _L - _F; )
{
_RI _M = _Unguarded_partition(
_F,
_L,
_Median(
_Ty(*_F),
_Ty(*(_F + (_L - _F) / 2)),
_Ty(*(_L - 1)),
_P
),
_P
);

if (_L - _M <= _M - _F)
{
_Sort(_M, _L, _P, _Val_type(_F));
_L = _M;
}
else
{
_Sort(_F, _M, _P, _Val_type(_F)),
_F = _M;
}
}
}

[Alexey B]

I don't want to dispute which function is faster, as if I was to sort a million structures, I would certainly write an algorithm myself. Now, I have two questions: Why would one of the functions, sort and qsort be significantly faster than the other. Don't they both implement the QuickSort algorithm?
Why does the std::sort use a recursive structure? I have always found that an iterative approach is faster and more efficient.

[Paul McKenzie]

Originally posted by Anthony Mai
Show me the code. Paul tried to show me once how std::sort() can sort as fast as qsort, but his example failed him miserably by showing a speed many orders of magnitude slower.

I showed you no such thing. What I did show you is that std::sort works on indices, and it was pointed out to you as such. Please stop spreading this propaganda here and on other threads.

As far as not wanting to talk to Meyers , all it takes is to post your claims at comp.lang.c++.moderated and you will get responses since he and others are there. That's all, and it only takes a few clicks using IE or Netscape to ask a question in a newsgroup. I post there, NMTop40 posts there, James Curran posts there, and even newbies to C++ who post to CodeGuru post there also. What's wrong with just clicking on the link that I gave to Josuttis's e-mail? It just takes a move of a mouse and a push of a button, not exactly yeoman's work.

Regards,

Paul McKenzie

[Graham]

#include <vector>
#include <algorithm>
#include <functional>
#include <iostream>
#include <cstdlib>
#include <ctime>

using namespace std;

typedef vector<int> intvec;

void randomise_vector(intvec& v)
{
srand(time(0));
for (intvec::iterator i = v.begin(); i != v.end(); ++i)
*i = rand();
}

inline bool stllessfunc(int lhs, int rhs)
{
return lhs < rhs;
}

inline int qscompare(const void* lhs, const void* rhs)
{
return *(static_cast<const int*>(lhs)) < *(static_cast<const int*>(rhs)) ? -1 :
(*(static_cast<const int*>(rhs)) < *(static_cast<const int*>(lhs)) ? 1 : 0);
}

int main()
{
intvec v(1000000, 0);

randomise_vector(v);

cout << "std::sort using functor: ";
clock_t start = clock();
sort(v.begin(), v.end(), less<int>());
clock_t stop = clock();
cout << stop - start << " ticks" << endl;

randomise_vector(v);

cout << "std::sort using function: ";
start = clock();
sort(v.begin(), v.end(), stllessfunc);
stop = clock();
cout << stop - start << " ticks" << endl;

randomise_vector(v);
cout << "qsort: ";
start = clock();
qsort(static_cast<void*>(&v[0]), 1000000, sizeof(int), qscompare);
stop = clock();
cout << stop - start << " ticks" << endl;

char c;
cin >> c;
return 0;
}


Output from program:

std::sort using functor: 830 ticks
std::sort using function: 1530 ticks
qsort: 3400 ticks

[jfaust]

Woohoo!

Similar results:

std::sort using functor: 380 ticks
std::sort using function: 591 ticks
qsort: 1212 ticks

smiles,

Jeff

[Paul McKenzie]

Here are the results from Borland Builder C++ 6.0:

std::sort using functor: 265 ticks
std::sort using function: 422 ticks
qsort: 531 ticks

Regards,

Paul McKenzie

[Paul McKenzie]

Here is Sun Solaris (very slow):

std::sort using functor: 4950 ticks
std::sort using function: 5380 ticks
qsort: 7250 ticks

Regards,

Paul McKenzie

[Anthony Mai]

Hold on to the excitement yet!

In Graham's code, the two comparison function use are not equivalent in code complexity. So it is not quote a fair comparison.

Granted when taking that difference away, qsort() is still slower than std::sort(). I accept that. And I looked into qsort source code, and see why:


static void __cdecl swap (
char *a,
char *b,
unsigned width
)
{
char tmp;

if ( a != b )
/* Do the swap one character at a time to avoid potential alignment
problems. */
while ( width-- ) {
tmp = *a;
*a++ = *b;
*b++ = tmp;
}
}


The swap function used by qsort swaps object one byte at a time, while as std::sort has the benefit of compiler optimization and swaps things at least 4 times faster (a 4 bytes integer at a time). So indeed qsort is bad in this aspect.


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.


std::sort() wins this battle over qsort purely by the fault of qsort author not being able to write something that copies more than a byte at a time. It also thanks to the fact that the object less<int> Graham used is an empty object, and hence passing it is never a huzzle. Next time when the object is more than a trivial int, and you are passing a none-empty comparator object in, you will be in trouble using std::sort. Paul's code has already demonstrated that.

[Paul McKenzie]

Assuming you only looked at VC++ source code, what is your explanation for Borland Builder 6.0 and Solaris std::sort beating qsort()?

And of course, Meyers is wrong (/sarcasm off).

Regards,

Paul McKenzie

[Paul McKenzie]

Originally posted by Anthony Mai
Next time when the object is more than a trivial int, and you are passing a none-empty comparator object in, you will be in trouble using std::sort. Paul's code has already demonstrated that. And so qsort() will beat std::sort() if there is, say a string as opposed to an int. OK, whatever you say.

VC 6.0:


#include <vector>
#include <algorithm>
#include <functional>
#include <iostream>
#include <cstdlib>
#include <ctime>
#include <string>

using namespace std;

class SomeClass
{
public:
std::string fld1;
};

struct SortFld
{
bool operator() (const SomeClass& first, const SomeClass& second)
{
return strcmp(first.fld1.c_str(), second.fld1.c_str())<0?true:false;
}
};


typedef vector<SomeClass> intvec;

void randomise_vector(intvec& v)
{
srand(time(0));
char szBuf[15];
for (intvec::iterator i = v.begin(); i != v.end(); ++i)
{
sprintf(szBuf, "%d", rand());
(*i).fld1 = szBuf;
}
}

inline bool stllessfunc(const SomeClass& lhs, const SomeClass& rhs)
{
return strcmp(lhs.fld1.c_str(), rhs.fld1.c_str())<0?true:false;
}

inline int qscompare(const void* lhs, const void* rhs)
{
return strcmp(((SomeClass *)lhs)->fld1.c_str(), ((SomeClass *)rhs)->fld1.c_str());
}

int main()
{
intvec v(1000000);

randomise_vector(v);

cout << "std::sort using functor: ";
clock_t start = clock();
sort(v.begin(), v.end(), SortFld());
clock_t stop = clock();
cout << stop - start << " ticks" << endl;

randomise_vector(v);

cout << "std::sort using function: ";
start = clock();
sort(v.begin(), v.end(), stllessfunc);
stop = clock();
cout << stop - start << " ticks" << endl;

randomise_vector(v);
cout << "qsort: ";
start = clock();
qsort(static_cast<void*>(&v[0]), 1000000, sizeof(SomeClass), qscompare);
stop = clock();
cout << stop - start << " ticks" << endl;

char c;
cin >> c;
return 0;
}

Output:
std::sort using functor: 6339 ticks
std::sort using function: 8672 ticks
qsort: 8762 ticks

Regards,

Paul McKenzie

[Graham]

I am not convinced of Scott Meyers's claim that his test result show std::sort faster than qsort() by 670%. Show me the code. Paul tried to show me once how std::sort() can sort as fast as qsort, but his example failed him miserably by showing a speed many orders of magnitude slower.

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.

The swap function used by qsort swaps object one byte at a time, while as std::sort has the benefit of compiler optimization and swaps things at least 4 times faster (a 4 bytes integer at a time). So indeed qsort is bad in this aspect.

So how do you propose to improve qsort's swapping? One of the arguments we've used against qsort is its lack of type-safety. It's that lack that is directly responsible for its inefficiency in swapping. I would hope that any half-decent std::sort implementation would use std::swap to swap objects, because then I can specialise swap for my class and make it efficient. You can swap two vectors (of any size) in the time it takes to swap two pointers: you can tell std::sort that, but you can't tell qsort.

These factors are not annoying little details that help to explain away an inconvenient result - they are fundamental reasons why std::sort is preferable to qsort.

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.

And just think, if the compiler did inline those functions, just how embarrasing the comparison would be then.

In Graham's code, the two comparison function use are not equivalent in code complexity. So it is not quote a fair comparison.

Don't talk tosh. I tried to make the two functions of equivalent complexity. That I couldn't is entirely down to qsort's requirements on the function (the need for void* arguments and a three-valued result). Don't tell me it's not fair, both functions were as efficient as the constraints allowed - it's another fundamental factor in the comparison: std::sort allows you to to use less complex comparison functions.

std::sort() wins this battle over qsort purely by the fault of qsort author not being able to write something that copies more than a byte at a time.

Cobblers. It's not the author's fault - he's hamstrung by the nature of qsort.

It also thanks to the fact that the object less<int> Graham used is an empty object, and hence passing it is never a huzzle.

And the original functor I proposed (and that you objected so strongly to) is also an empty object. That's another factor: any predicate should be an empty object.

[jwbarton]

I checked the compiled output of Visual C++ 6.0 to see if the calls to operator() were being inlined. As far as I could tell, as long as the operator() was not too big, Visual C++ 6.0 would inline the call. This was compiled using the default release mode optimizer option to Maximize speed.

In order to verify that the inlining of the calls was making a difference, I modified the test program which sorted a vector of ints to test using a version with an external operator() (which can't be inlined) against a version which can be inlined.

When I ran this test on my machine, I got the following output:

std::sort using functor: 470 ticks
std::sort using functor without inline: 1042 ticks
std::sort using function: 1011 ticks

I think that this shows that Scott Meyers' claims about inlining improving the performance of the sort to be true.

This is the test program that I used:

extern.h
class SomeClass
{
public:
int fld1;
};

struct SortFldExtern
{
bool operator() (const SomeClass& first, const SomeClass& second);
};



extern.cpp
#include "extern.h"

bool SortFldExtern ::operator() (const SomeClass& first, const SomeClass& second)
{
return first.fld1 < second.fld1;
}


main.cpp
#include <vector>
#include <algorithm>
#include <functional>
#include <iostream>
#include <cstdlib>
#include <ctime>
#include <string>
#include "extern.h"

using namespace std;


typedef vector<SomeClass> intvec;


void randomize_vector(intvec& v)
{
srand(time(0));
for (intvec::iterator i = v.begin(); i != v.end(); ++i)
(*i).fld1 = rand();
}


struct SortFld
{
bool operator() (const SomeClass& first, const SomeClass& second)
{
return first.fld1 < second.fld1;
}
};


inline bool stllessfunc(const SomeClass& lhs, const SomeClass& rhs)
{
return lhs.fld1 < rhs.fld1;
}


int main()
{
intvec v(1000000);

randomize_vector(v);

cout << "std::sort using functor: ";
clock_t start = clock();
sort(v.begin(), v.end(), SortFld());
clock_t stop = clock();
cout << stop - start << " ticks" << endl;

randomize_vector(v);

cout << "std::sort using functor without inline: ";
start = clock();
sort(v.begin(), v.end(), SortFldExtern());
stop = clock();
cout << stop - start << " ticks" << endl;

randomize_vector(v);

cout << "std::sort using function: ";
start = clock();
sort(v.begin(), v.end(), stllessfunc);
stop = clock();
cout << stop - start << " ticks" << endl;

char c;
cin >> c;
return 0;
}

[Anthony Mai]

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.

[Paul McKenzie]

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/austern.htm?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:
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 austern@research.att.com.

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

[Graham]

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.

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.

[Anthony Mai]

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.)

[Graham]

... 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.

[jwbarton]

This is in reply to Anthony Mai:

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

Quote of 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.


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:
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