在带有迭代器和模板的 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] returns 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>);    
}

在带有迭代器和模板的 C++ 中使用 std::sort

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

c++

sorting

templates

iterator

std