c++ - 在C++中将std::sort与迭代器和模板一起使用

Question

我正在尝试使std::sort在使用模板和稍微复杂的数据结构时工作。我似乎无法弄清楚为什么以下命令会导致错误

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

其背后的数据结构如下所示。

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;
}

这会导致许多构建时间错误。 Xcode中的错误似乎是

"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' "

和更多

Answer 1

std::sort需要迭代器或指针。 graph->edge[0]返回Edge对象引用而不是指针。您需要传递指针:

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

假设您想对所有边缘进行排序，则第二个指针需要在列表末尾之后:

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

下一个问题是myComp需要引用而不是指针:

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

正如其他人指出的那样，用std::vector替换原始指针数组将简化代码并使其更安全:

#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>);    
}