对嵌套类进行 STL 排序

Question

我有一个具有节点向量的图类。每个节点都有一个顶点和一个 STL 边列表。本质上它是一个邻接列表。

对于我的作业，我试图显示具有最多边的顶点。我想我应该按边大小对图的节点向量进行排序并打印前 N 个顶点。

所以我试图找出STL排序，但我遇到了困难。

我有

 std::sort(path.begin(), path.end());

路径是节点向量（节点=顶点值和边列表）

在我的节点类中，我有

bool operator<(const Node<T>& rhs){
    return size < rhs.size; //size is how many edges the vertex has
}

但它给了我错误。如何在节点类中构造 operator< 函数来使用 STL 排序？

以下是错误：

$ make
g++ -c -g -std=c++0x graphBuilder.cpp
In file included from /usr/lib/gcc/i486-slackware-linux/4.5.2/../../../../include/c++/4.5.2/algorithm:63:0,
             from graph.h:6,
             from graphBuilder.cpp:2:
/usr/lib/gcc/i486-slackware-linux/4.5.2/../../../../include/c++/4.5.2/bits/stl_algo.h: In function '_RandomAccessIterator std::__unguarded_partition(_RandomAccessIterator, _RandomAccessIterator, const _Tp&) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<Node<std::basic_string<char> >*, std::vector<Node<std::basic_string<char> >, std::allocator<Node<std::basic_string<char> > > > >, _Tp = Node<std::basic_string<char> >]':
/usr/lib/gcc/i486-slackware-linux/4.5.2/../../../../include/c++/4.5.2/bits/stl_algo.h:2249:70:   instantiated from '_RandomAccessIterator std::__unguarded_partition_pivot(_RandomAccessIterator, _RandomAccessIterator) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<Node<std::basic_string<char> >*, std::vector<Node<std::basic_string<char> >, std::allocator<Node<std::basic_string<char> > > > >]'
/usr/lib/gcc/i486-slackware-linux/4.5.2/../../../../include/c++/4.5.2/bits/stl_algo.h:2280:54:   instantiated from 'void std::__introsort_loop(_RandomAccessIterator, _RandomAccessIterator, _Size) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<Node<std::basic_string<char> >*, std::vector<Node<std::basic_string<char> >, std::allocator<Node<std::basic_string<char> > > > >, _Size = int]'
/usr/lib/gcc/i486-slackware-linux/4.5.2/../../../../include/c++/4.5.2/bits/stl_algo.h:5212:4:   instantiated from 'void std::sort(_RAIter, _RAIter) [with _RAIter = __gnu_cxx::__normal_iterator<Node<std::basic_string<char> >*, std::vector<Node<std::basic_string<char> >, std::allocator<Node<std::basic_string<char> > > > >]'
graph.h:32:13:   instantiated from 'void Graph<T>::topN(int) [with T = std::basic_string<char>]'
graphBuilder.cpp:10:17:   instantiated from here /usr/lib/gcc/i486-slackware-linux/4.5.2/../../../../include/c++/4.5.2/bits/stl_algo.h:2211:4: error: passing 'const Node<std::basic_string<char> >' as 'this' argument of 'bool Node<T>::operator<(const Node<T>&) [with T = std::basic_string<char>]' discards qualifiers
make: *** [graphBuilder.o] Error 1

Answer 1

您的成员函数需要是 const 限定的：

bool operator<(const Node<T>& rhs) const{

编辑

根据请求，这里有更多我知道您需要使成员函数成为 const 的信息。

挖掘与 stdlib 相关的编译器错误中隐藏的含义是一门艺术，并且通过练习可以变得更好。与 Stdlib 相关的错误通常会引发一系列编译器错误。通常，这些错误中最有用的是最后一个错误，因为该错误是从您实际编写的代码的上下文中生成的，而不是来自库代码的内部。

在这种情况下，最后一个编译器错误是：

graphBuilder.cpp:10:17：从这里实例化
/usr/lib/gcc/i486-slackware-linux/4.5.2/../../../../include/c++/4.5.2/bits/stl_algo.h:2211:4:
错误：传递“const Node >” 作为“这个”
'bool Node::operator<(const Node&) 的参数 [with T =
std::basic_string]' 丢弃限定符

我已经突出显示了有启发性的部分。这告诉我，在 OP 的实际代码中，由于代码的构造方式（也许 sort 调用本身位于 const 成员函数中？谁知道......） this 指针必须是 const，但从发布的 operator< 声明中可以看出，该方法不是 const代码>.编译器错误中提到的“限定符”是标准所说的“cv 限定符”。 “cv”代表“常量/易失性”。

当编译器说“将 const X 作为 this 传递给 Node::operator< 丢弃限定符”时，它真正想说的是：

“你说 X 是 const，但随后您尝试通过 const X 调用非常量成员函数。为了让我进行此调用，我必须。丢弃const X 上的限定符不允许我这样做，所以你必须修复你的代码。”

这里“丢弃”的限定符是方法本身的限定符。换句话说，operator< 必须是 const 成员函数，但事实并非如此。

Answer 2

bool operator<(const Node<T>& rhs) const {
    return size() < rhs.size();
}

将运算符设置为 const 可能有助于不激怒编译器。

注意：出现问题的原因是 this 始终是 const，因此编译器希望您承诺不更改您通过使用 this 创建方法指定的值> 具有 const 限定符。

或者，您可以进行非成员比较以与排序一起使用，如下所示：

<template typename T>
struct CompareNodes {
bool operator()(const Node<T>& lhs, const Node<T>& rhs) const
{
     return lhs.size() < rhs.size();
}
};

std::sort(path.cbegin(), path.cend(), CompareNodes<T>());