CODEWITHSUNDEEP
c++sortingtemplatesiteratorstd
RoryHector
RoryHector

Reputation: 196

Using std::sort in c++ with iterators and templates

I'm trying to get std::sort to work when using templates and a slightly complicated data structure. I can't seem to figure out why the following command causes errors 

sort(graph->edge[0], graph->edge[(graph->E)-1], myComp<T>);

The data structures behind this are shown below. 

template <typename T>
class Edge
{
    public:
    int src, dest;
    T weight;
};

template <typename T>
class Graph_krus
{
    public:
    int V, E;
    Edge<T>* edge;
};

template <typename T>
Graph_krus<T>* createGraph(int V, int E)
{
    Graph_krus<T>* graph = new Graph_krus<T>;
    graph->V = V;
    graph->E = E;
    graph->edge = new Edge<T>[E];
    return graph;
}

template <typename T>
bool myComp(Edge<T>* a, Edge<T>* b)
{
    bool greater = a->weight > b->weight;
    return greater;
}

This causes many build time errors. The errors from Xcode seem to be

"No type named 'difference_type' in 'std::__1::iterator_traits >'"

"No type named 'value_type' in 'std::__1::iterator_traits >' "

"Invalid operands to binary expression ('Edge' and 'Edge') "

"Cannot decrement value of type 'Edge' "

and more

Upvotes: 1

Views: 346

Answers (1)

Alan Birtles
Alan Birtles

Reputation: 36399

std::sort requires iterators or pointers. graph->edge[0] returns an Edge object reference not a pointer. You need to pass pointers instead:

std::sort(graph->edge, graph->edge + graph->E-1, myComp<T>);

Presuming you want to sort all the edges your second pointer needs to be one past the end of your list:

std::sort(graph->edge, graph->edge + graph->E, myComp<T>);

The next issue is that myComp needs to take references not pointers:

template <typename T>
bool myComp(const Edge<T>& a, const Edge<T>& b)
{
    bool greater = a.weight > b.weight;
    return greater;
}

As others have pointed out replacing your raw pointer arrays with std::vector would simplify your code and make it safer:

#include <algorithm>
#include <vector>
#include <memory>

template <typename T>
class Edge
{
    public:
    int src, dest;
    T weight;
};

template <typename T>
struct Graph_krus
{
    int V;
    std::vector<Edge<T>> edge;
};

template <typename T>
std::unique_ptr<Graph_krus<T>> createGraph(int V, int E)
{
    auto graph = std::make_unique<Graph_krus<T>>();
    graph->V = V;
    graph->edge.resize(E);
    return graph;
}
template <typename T>
bool myComp(const Edge<T>& a, const Edge<T>& b)
{
    bool greater = a.weight > b.weight;
    return greater;
}

int main()
{
    auto graph = createGraph<int>(1,1);
    std::sort(graph->edge.begin(), graph->edge.end(), myComp<int>);    
}

Upvotes: 4

Related Questions