Solved

Signature of predicate for std::sort

Posted on 2013-12-04
6
372 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
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 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
Independent Software Vendors: We Want Your Opinion

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 
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

Industry Leaders: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Templates For Beginners Or How To Encourage The Compiler To Work For You Introduction This tutorial is targeted at the reader who is, perhaps, familiar with the basics of C++ but would prefer a little slower introduction to the more ad…
This article will show you some of the more useful Standard Template Library (STL) algorithms through the use of working examples.  You will learn about how these algorithms fit into the STL architecture, how they work with STL containers, and why t…
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 learn how to user default arguments when defining functions. This method of defining functions will be contrasted with the non-default-argument of defining functions.

705 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