Re: [Boost-users] [BGL] Unable to sort list of edge_descriptors

Subject: Re: [Boost-users] [BGL] Unable to sort list of edge_descriptors
From: Peter Wright (pete_at_[hidden])
Date: 2010-11-07 01:20:50

Hi Mike,

This problem intrigued me enough that I felt like actually doing the
work to make sense of it - which turned out to be a useful learning
experience, as I now:

(a) better understand the typename keyword, and
(b) realise how amazingly helpful the Clang C++ compiler output can be. :)

Short explanation - I think you did at least three things wrong:

1. you used the "typename" keyword incorrectly,
2. you defined the SortByName functor class incorrectly (inheriting
   from std::binary_function when the operator() was _not_ a binary
   function), then
3. you *used* the SortByName functor incorrectly (by supplying it to
   std::list::sort, which expects a 2-arg function instead of 3-arg).

Longer explanation below:

On 06/11 02:04:57, Mike Douglass wrote:
> I'm trying to sort a list of edge_descriptors, but I get the
> compiler error described below.
[ ... ]
> //With the above line uncommented the compiler says:
> 
> /*
> ./Includes/Utilities.cpp: In function ???void Sort_Test(Graph&)???:
> ./Includes/Utilities.cpp:539: error: wrong number of template arguments (1, 
> should be 2)
> ./Includes/Utilities.cpp:513: error: provided for ???template<class Graph, class 
> edgeDescriptor> struct SortByName???
> make: *** [plc] Error 1
> */
[ ... ]
>  But clearly there are two template arguments - < typename Graph,
>  typename edgeDescriptor >

(Note: I rewrote your code into a bastardised form that doesn't use
Boost::Graph, as the problem doesn't look like it's got anything to do
with that.)

Compile the attached douglass-broken.cpp with GNU g++ and you get
error output closely matching your report (I've replaced GCC's open/close
single-quotes with ' to avoid encoding issues):

----------------------------------------------------------------------
$ g++ douglass-broken.cpp -o douglas-broken
douglass-broken.cpp: In function 'void Sort_Test(Graph&)':
douglass-broken.cpp:45:62: error: wrong number of template arguments (1, should be 2)
douglass-broken.cpp:21:8: error: provided for 'template<class Graph, class edgeDescriptor> struct SortByName'
$
----------------------------------------------------------------------

I agree, it's not a particuarly helpful error message - in fact it's
outright misleading.

The output from clang++, however, is *extremely* helpful (though it's
much easier to read with the default coloured/bolded output, here it's
just plain text):

----------------------------------------------------------------------
$ clang++ douglass-broken.cpp -o douglass-broken
douglass-broken.cpp:45:32: error: expected a qualified name after 'typename'
    A.sort(SortByName<typename Graph, typename edgeDescriptor>());
                               ^
douglass-broken.cpp:45:48: error: expected a qualified name after 'typename'
    A.sort(SortByName<typename Graph, typename edgeDescriptor>());
                                               ^
In file included from douglass-broken.cpp:2:
In file included from /usr/include/c++/4.5.1/list:65:
/usr/include/c++/4.5.1/bits/list.tcc:286:12: error: no matching function for call to object of type
      'SortByName<std::map<std::basic_string<char>, Edge, std::less<std::basic_string<char> >,
      std::allocator<std::pair<std::basic_string<char> const, Edge> > >, std::basic_string<char> >'
              if (__comp(*__first2, *__first1))
                  ^~~~~~
/usr/include/c++/4.5.1/bits/list.tcc:398:7: note: in instantiation of function template specialization 'std::list<std::basic_string<char>,
      std::allocator<std::basic_string<char> > >::merge<SortByName<std::map<std::basic_string<char>, Edge,
      std::less<std::basic_string<char> >, std::allocator<std::pair<std::basic_string<char> const, Edge> > >, std::basic_string<char> > >'
      requested here
                    __counter->merge(__carry, __comp);
                    ^
douglass-broken.cpp:45:5: note: in instantiation of function template specialization 'std::list<std::basic_string<char>,
      std::allocator<std::basic_string<char> > >::sort<SortByName<std::map<std::basic_string<char>, Edge, std::less<std::basic_string<char>
      >, std::allocator<std::pair<std::basic_string<char> const, Edge> > >, std::basic_string<char> > >' requested here
    A.sort(SortByName<typename Graph, typename edgeDescriptor>());
    ^
douglass-broken.cpp:64:5: note: in instantiation of function template specialization 'Sort_Test<std::map<std::basic_string<char>, Edge,
      std::less<std::basic_string<char> >, std::allocator<std::pair<std::basic_string<char> const, Edge> > > >' requested here
    Sort_Test<Graph>(the_graph);
    ^
douglass-broken.cpp:23:10: note: candidate function not viable: requires 3 arguments, but 2 were provided
    bool operator()(const Graph& g, const edgeDescriptor& a, const edgeDescriptor& b)
         ^
3 errors generated.
----------------------------------------------------------------------

So, the first problem is that you used typename where it shouldn't be
used, in this line:
    
    A.sort(SortByName<typename Graph, typename edgeDescriptor>());

...and I suspect that confused the g++ parser so that it interpreted
the expression "typename Graph, typename edgeDescriptor" as a *single*
type, resulting in the confusing error message.

You can verify this by adding extra nonsense types in the same way, eg.:

    A.sort(SortByName<typename Graph, typename edgeDescriptor, typename NonexistentType, typename Rubbish, typename Bollocks>());

Compile that and the error message supplied by my g++ (I'm using
version 4.5.1) is still the same "wrong number of template arguments
(1, should be 2)", despite it now looking like *five* arguments :).

As you can see, the Clang C++ compiler does a much better job, both
pointing out the typename-usage error *and* reporting (albeit
indirectly) that you're supplying a three-argument functor to the
std::list::sort, when it actually requires a binary functor/function.

(Note: To be fair to GCC, once you remove the two incorrect "typename"
keywords in the A.sort line, it also generates a usable error message.)

One way to fix it would be as Cedric suggested, and that's the model I
used in my douglass-working.cpp (attached). I changed SortByName so it
requires a const Graph& in its constructor, stores a reference to that
in a private variable, *then* changed SortByName::operator() to take
two edgeDescriptor args and return bool.

It is dicey in one way, in that it stores a *reference* to its Graph -
so if the SortByName object outlives the Graph then it could blow up
spectacularly. But the alternative of copying the entire graph seemed
a bit excessive.

Another way to fix it (and also avoid the reference-storing problem)
requires using Boost::Bind - change SortByName to this:

----------------------------------------------------------------------
template <typename G, typename ED>
struct SortByName
{
    typedef bool result_type;   // required for use by STL algorithms.
    result_type operator()(G& g, const ED& a, const ED& b)
    {
        return g[a].eName < g[b].eName;
    }
};
----------------------------------------------------------------------

...and the A.sort call to this:

    A.sort( boost::bind(SortByName<Graph, edgeDescriptor>(), g, _1, _2) );

That seems to work fine, and may be a closer match to what you
originally intended.

Pete.
-- 
"DAMN WHO MESSED WITH MY CAPSLOCK KEY that's better."
	-- geoff lane, <e886430646_at_[hidden]>, asr