Solved

Signature of predicate for std::sort

Posted on 2013-12-04
6
360 Views
Last Modified: 2013-12-05
Ah hello.

I am revisiting sorting of vectors, and have the following two questions.

1) Please consider the following simple code:
struct MyStruct
{
	MyStruct(int n) : m_n(n){}
	int m_n;
};

//...

std::vector<MyStruct*> vec2;
for (int i = 3; i >= 0; --i)
{
	vec2.push_back(new MyStruct(i));
}
std::sort(vec2.begin(), vec2.end());

Open in new window


This compiles as-is; I didn't expect it to as I have not defined any operator< for MyStruct, nor is there a global operator<.  I stepped through the code but quickly got lost amongst it; the STL is not the easiest thing to read, so can someone please tell me what is being used to sort here please?  

2) Please consider the following updated code:

struct MyStruct
{
	MyStruct(int n) : m_n(n){}
	int m_n;
};

struct MyStructPredicate
{
	bool operator()(const MyStruct* const & rhs, const MyStruct*const & lhs)
	{
		return rhs->m_n < lhs->m_n;
	}
};

struct MyStructPredicate2
{
	bool operator()(const MyStruct* rhs, const MyStruct* lhs)
	{
		return rhs->m_n < lhs->m_n;
	}
};

//...

std::vector<MyStruct*> vec2;
for (int i = 3; i >= 0; --i)
{
	vec2.push_back(new MyStruct(i));
}
std::sort(vec2.begin(), vec2.end(), MyStructPredicate());
std::sort(vec2.begin(), vec2.end(), MyStructPredicate2());

Open in new window

Clearly here I have added two predicates for sorting, both of which work perfectly well on their own.  My question is simply which is the preferred signature of the predicate's operator(): I could not find any documentation suggesting which one to use, but I was recently told that "const references to pointers is unwarranted" in this case (which confused me) so tried to find documentation suggesting that the signature should be

operator()(const T&, const T&)

Open in new window


...where T in my case is MyStruct*, but couldn't find any!  It seems that when we store pointer types, we can pass by value (since no expensive copying is involved) but if we were storing, in this case, MyStruct objects, references would make more sense to avoid the copying...

Can someone advise please?
0
Comment
Question by:mrwad99
  • 3
  • 3
6 Comments
 
LVL 40

Accepted Solution

by:
evilrix earned 250 total points
ID: 39695554
1)

It's a vector of pointers so it's just using the inbuilt operators for pointers for that.

2)

I'd us MyStructPredicate2 as it saves on a level of indirection. The reference to pointer don't really do much of anything and could impede the compilers ability to cache values. Generally, it's better to pass intrinsics by value and user defined by const reference. The compiler can perform optimisations when intrinsics are pass by value that it might not be able to do otherwise.
0
 
LVL 19

Author Comment

by:mrwad99
ID: 39695669
Hi Rx!  Long time no see!  I trust you are well.

1) Right, ok, so the pointer values are being sorted.  Makes sense.

2) Impede the compilers ability to cache values?  Optimisations when intrinsics are passed by value?

Can you elaborate on these please?  please?

Also, is there any logic in what I was told as "const references to pointers is unwarranted" in this case?
0
 
LVL 40

Expert Comment

by:evilrix
ID: 39696567
Very well, thanks. And you?

1) Yeah, that's pretty much what's happening.

2) Well, the compiler could cache a value if it the function is called many times and the passed in value doesn't change. It couldn't be able to do that if it's passed by reference. Of course, unless you are writing high-performance code it's probably not that big of a deal but I'm a great believer in writing code that helps the compiler optimise. That's not to say I am suggesting premature optimisation, I'm just suggesting that it doesn't hurt to write code that is optimal.

>> is there any logic in what I was told...
Well give that a reference is really just syntactic sugar for a pointer when you pass a reference to a pointer you are actually passing a pointer to a pointer and, this, introducing another level of indirection. Of course, the compiler takes care of all the messy dereferencing business but it is still happening (one way or another). I guess the question to ask yourself is what do you gain by doing that?
0
How to run any project with ease

Manage projects of all sizes how you want. Great for personal to-do lists, project milestones, team priorities and launch plans.
- Combine task lists, docs, spreadsheets, and chat in one
- View and edit from mobile/offline
- Cut down on emails

 
LVL 19

Author Comment

by:mrwad99
ID: 39697950
I am ok thanks :)

Hmm...why wouldn't the compiler be able to cache the value if it was a reference, since references cannot be changed?  Sorry I have misunderstood...
0
 
LVL 40

Assisted Solution

by:evilrix
evilrix earned 250 total points
ID: 39697980
Because what is passed to the function isn't the value but the address of the value. The compiler is less likely to be able to assume it can cache the value being referenced. Also, the compiler will have to perform the dereferencing, which is slower than direct access. Either way, you are introducing an unnecessary step for the compiler to optimise away, meaning there is less chance for optimisation. Of course, all compilers implement optimisations and references differently but, as a general rule, it is better to pass an intrinsic by value than by reference, unless you specifically need reference semantics.

Look at it another way, passing an int by value is no more expensive than passing a pointer to int by value (they are, generally, the same size - the standard allows casting from pointer to int and back again, safely) but with the pointer you'll have to deference it to get the int. Passing by reference requires the same dereferencing to take place (assuming the compiler implements references via pointers, which they generally do).
0
 
LVL 19

Author Closing Comment

by:mrwad99
ID: 39697985
Marvellous.  As always, many thanks :)
0

Featured Post

How to run any project with ease

Manage projects of all sizes how you want. Great for personal to-do lists, project milestones, team priorities and launch plans.
- Combine task lists, docs, spreadsheets, and chat in one
- View and edit from mobile/offline
- Cut down on emails

Join & Write a Comment

Article by: SunnyDark
This article's goal is to present you with an easy to use XML wrapper for C++ and also present some interesting techniques that you might use with MS C++. The reason I built this class is to ease the pain of using XML files with C++, since there is…
IntroductionThis article is the second in a three part article series on the Visual Studio 2008 Debugger.  It provides tips in setting and using breakpoints. If not familiar with this debugger, you can find a basic introduction in the EE article loc…
The goal of the video will be to teach the user the concept of local variables and scope. An example of a locally defined variable will be given as well as an explanation of what scope is in C++. The local variable and concept of scope will be relat…
The viewer will be introduced to the member functions push_back and pop_back of the vector class. The video will teach the difference between the two as well as how to use each one along with its functionality.

757 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

18 Experts available now in Live!

Get 1:1 Help Now