?
Solved

Signature of predicate for std::sort

Posted on 2013-12-04
6
Medium Priority
?
375 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 1000 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 1000 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

Free Tool: ZipGrep

ZipGrep is a utility that can list and search zip (.war, .ear, .jar, etc) archives for text patterns, without the need to extract the archive's contents.

One of a set of tools we're offering as a way to say thank you for being a part of the community.

Question has a verified solution.

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

Unlike C#, C++ doesn't have native support for sealing classes (so they cannot be sub-classed). At the cost of a virtual base class pointer it is possible to implement a pseudo sealing mechanism The trick is to virtually inherit from a base class…
Often, when implementing a feature, you won't know how certain events should be handled at the point where they occur and you'd rather defer to the user of your function or class. For example, a XML parser will extract a tag from the source code, wh…
The goal of the tutorial is to teach the user how to use functions in C++. The video will cover how to define functions, how to call functions and how to create functions prototypes. Microsoft Visual C++ 2010 Express will be used as a text editor an…
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.
Suggested Courses

764 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