STL Vector problems

[Franz]

I have two questions

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

[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 [email protected], 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.