• Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 381
  • Last Modified:

Signature of predicate for std::sort

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
mrwad99
Asked:
mrwad99
  • 3
  • 3
2 Solutions
 
evilrixSenior Software Engineer (Avast)Commented:
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
 
mrwad99Author Commented:
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
 
evilrixSenior Software Engineer (Avast)Commented:
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
Technology Partners: 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!

 
mrwad99Author Commented:
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
 
evilrixSenior Software Engineer (Avast)Commented:
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
 
mrwad99Author Commented:
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.

  • 3
  • 3
Tackle projects and never again get stuck behind a technical roadblock.
Join Now