STL Sort on nested Classes

Question

I have a graph class that has a vector of nodes. In each node, there is a vertex and a STL list of edges. Essentially it's an adjacency list.

For my assignment, I am trying to display the vertices with the most edges. I figured I would sort the graph's vector of nodes by edge size and print the top N vertices.

So I am trying to figure out STL sort, but I'm having difficulties.

I have

 std::sort(path.begin(), path.end());

Where path is the vector of nodes (node = vertex value and list of edges)

In my node class, I have

bool operator<(const Node<T>& rhs){
    return size < rhs.size; //size is how many edges the vertex has
}

But it's giving me errors. How can I construct the operator< function in my node class to work with STL sort?

Here are the errors:

$ make
g++ -c -g -std=c++0x graphBuilder.cpp
In file included from /usr/lib/gcc/i486-slackware-linux/4.5.2/../../../../include/c++/4.5.2/algorithm:63:0,
             from graph.h:6,
             from graphBuilder.cpp:2:
/usr/lib/gcc/i486-slackware-linux/4.5.2/../../../../include/c++/4.5.2/bits/stl_algo.h: In function '_RandomAccessIterator std::__unguarded_partition(_RandomAccessIterator, _RandomAccessIterator, const _Tp&) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<Node<std::basic_string<char> >*, std::vector<Node<std::basic_string<char> >, std::allocator<Node<std::basic_string<char> > > > >, _Tp = Node<std::basic_string<char> >]':
/usr/lib/gcc/i486-slackware-linux/4.5.2/../../../../include/c++/4.5.2/bits/stl_algo.h:2249:70:   instantiated from '_RandomAccessIterator std::__unguarded_partition_pivot(_RandomAccessIterator, _RandomAccessIterator) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<Node<std::basic_string<char> >*, std::vector<Node<std::basic_string<char> >, std::allocator<Node<std::basic_string<char> > > > >]'
/usr/lib/gcc/i486-slackware-linux/4.5.2/../../../../include/c++/4.5.2/bits/stl_algo.h:2280:54:   instantiated from 'void std::__introsort_loop(_RandomAccessIterator, _RandomAccessIterator, _Size) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<Node<std::basic_string<char> >*, std::vector<Node<std::basic_string<char> >, std::allocator<Node<std::basic_string<char> > > > >, _Size = int]'
/usr/lib/gcc/i486-slackware-linux/4.5.2/../../../../include/c++/4.5.2/bits/stl_algo.h:5212:4:   instantiated from 'void std::sort(_RAIter, _RAIter) [with _RAIter = __gnu_cxx::__normal_iterator<Node<std::basic_string<char> >*, std::vector<Node<std::basic_string<char> >, std::allocator<Node<std::basic_string<char> > > > >]'
graph.h:32:13:   instantiated from 'void Graph<T>::topN(int) [with T = std::basic_string<char>]'
graphBuilder.cpp:10:17:   instantiated from here /usr/lib/gcc/i486-slackware-linux/4.5.2/../../../../include/c++/4.5.2/bits/stl_algo.h:2211:4: error: passing 'const Node<std::basic_string<char> >' as 'this' argument of 'bool Node<T>::operator<(const Node<T>&) [with T = std::basic_string<char>]' discards qualifiers
make: *** [graphBuilder.o] Error 1

Answer 1

Your member function needs to be const-qualified:

bool operator<(const Node<T>& rhs) const{

EDIT

Per request, here is a bit more how I knew that you needed to make the member function const.

Divining the hidden meanings in stdlib-related compiler errors is something of an art, and something that you get better at with practice. Stdlib-related errors will often emit a whole series of compiler errors. Usually the most useful of these errors is the last one, because that one is generated from the context of the code you actually wrote, rather than coming from the bowels of the library code.

In this case, the last compiler error was:

graphBuilder.cpp:10:17: instantiated from here /usr/lib/gcc/i486-slackware-linux/4.5.2/../../../../include/c++/4.5.2/bits/stl_algo.h:2211:4: error: passing 'const Node >' as 'this' argument of 'bool Node::operator<(const Node&) [with T = std::basic_string]' discards qualifiers

I've highlighted the illuminating bits. This tells me that in OP's actual code, because of how the code is constructed (maybe the sort call is itself in a const member function? who knows...) the this pointer must be const, but as we can see from the posted declaration of operator<, the method is not const. The "qualifiers" referred to in the compiler errors are what the Standard calls "cv-qualifiers". "cv" stands for "const/volatile."

When the compiler says "Passing const X as this to Node::operator< discards qualifiers" what it's really trying to say is:

"You said X was const but then you tried to call a non-const member function through const X. In order for me to make this call, I would have to discard the const qualifier on X. I'm not allowed to do that, so you have to fix your code."

The qualifiers being "discarded" here are the qualifiers on the method itself. In other words, operator< must be a const member function, but it's not.

Answer 2

bool operator<(const Node<T>& rhs) const {
    return size() < rhs.size();
}

Making the operator const as it should be may help with not angering the compiler.

Note: The problem arises because this is always const so the compiler expects you to promise not to change it which you specify by making the method using this to have the const qualifier.

Alternately you could make a non-member comparison for use with sort like so:

<template typename T>
struct CompareNodes {
bool operator()(const Node<T>& lhs, const Node<T>& rhs) const
{
     return lhs.size() < rhs.size();
}
};

std::sort(path.cbegin(), path.cend(), CompareNodes<T>());