Want to win a PS4? Go Premium and enter to win our High-Tech Treats giveaway. Enter to Win

x
Solved

# Signature of predicate for std::sort

Posted on 2013-12-04
Medium Priority
379 Views
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());
``````

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());
``````
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&)
``````

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

0
[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
• 3
• 3

LVL 40

Accepted Solution

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

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?

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

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

LVL 19

Author Comment

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

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

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

## Featured Post

Question has a verified solution.

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

Included as part of the C++ Standard Template Library (STL) is a collection of generic containers. Each of these containers serves a different purpose and has different pros and cons. It is often difficult to decide which container to use and â€¦
Go is an acronym of golang, is a programming language developed Google in 2007. Go is a new language that is mostly in the C family, with significant input from Pascal/Modula/Oberon family. Hence Go arisen as low-level language with fast compilationâ€¦
The goal of the video will be to teach the user the difference and consequence of passing data by value vs passing data by reference in C++. An example of passing data by value as well as an example of passing data by reference will be be given. Botâ€¦
The viewer will learn how to clear a vector as well as how to detect empty vectors in C++.
###### Suggested Courses
Course of the Month11 days, 5 hours left to enroll