#include <map>
#include <list>
#include <string>
#include <functional>
#include <iostream>

// -------------------------------------------------------------------
// Three example types, just enough to effectively simulate
// the original (compile-time) problem.
struct Edge {
    Edge() : eName("") {}
    Edge(const std::string& name) : eName(name) {}
    std::string eName;
};
typedef std::string edgeDescriptor;
typedef std::map<edgeDescriptor, Edge> Graph;

// -------------------------------------------------------------------
// The SortByName template-struct functor type.
template <typename Graph, typename edgeDescriptor>
struct SortByName : public std::binary_function<edgeDescriptor, edgeDescriptor, bool>
{
public:
    SortByName(const Graph& g) : g_(g) { }

    bool operator()(const edgeDescriptor& a, const edgeDescriptor& b)
    {
        // NOTE: g_ is const, so if there isn't a const
        // Graph::operator[] then we can't use it.
        //return g_[a].eName < g_[b].eName; // fails for Graph == std::map.
        return g_.find(a)->second.eName < g_.find(b)->second.eName;
    }

private:
    // SortByName needs a Graph to work, so disable default constructor.
    SortByName();

    // This is a bit dicey, as a SortByName functor will be useless if
    // the corresponding Graph object is destructed.
    const Graph& g_;
};

// -------------------------------------------------------------------
// The Sort_Test template-function attempts to actually *use*
// SortByName. 
template <typename Graph>
void Sort_Test(Graph& g)
{
    typedef std::list<edgeDescriptor> edge_list;
    edge_list A;

    // Put some edges into the edge_list A.
    A.push_back(edgeDescriptor("Fred"));
    A.push_back(edgeDescriptor("Barney"));
    A.push_back(edgeDescriptor("Wilma"));
    A.push_back(edgeDescriptor("Betty"));

    // Attempt to sort using a SortByName functor.
    A.sort(SortByName<Graph, edgeDescriptor>(g));

    // Output the sorted result, assuming the sort succeeds.
    for (std::list<edgeDescriptor>::iterator i = A.begin(); i != A.end(); ++i) {
        std::cout << *i << " => " << g[*i].eName << std::endl;
    }
}

// -------------------------------------------------------------------
// Just populate a Graph object and passes it to Sort_Test.
int main(int argc, const char* argv[])
{
    Graph the_graph;

    the_graph["Fred"] = Edge("Flinstone");
    the_graph["Barney"] = Edge("Rubble");
    the_graph["Wilma"] = Edge("Flintstone");
    the_graph["Betty"] = Edge("Rubble");

    Sort_Test<Graph>(the_graph);

    return 0;
}