STL сортировка по вложенным классам - PullRequest
Новая
       25

STL сортировка по вложенным классам

0 голосов
/ 26 сентября 2011

У меня есть класс графа с вектором узлов.В каждом узле есть вершина и список ребер STL.По сути это список смежности.

Для моего задания я пытаюсь отобразить вершины с наибольшим количеством ребер.Я решил отсортировать вектор графа узлов по размеру ребра и вывести верхние вершины N.

Итак, я пытаюсь выяснить сортировку STL, но у меня возникают трудности.

Iиметь 

 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

Ответы [ 2 ]

3 голосов
/ 26 сентября 2011

Ваша функция-член должна быть 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 >' в качестве 'this' аргумента 'bool Node:: operator <(const Node &) [с T = std :: basic_string] '<strong> отбрасывает квалификаторы

Я выделил светящиеся биты.Это говорит мне о том, что в реальном коде OP из-за того, как код построен (возможно, вызов sort сам по себе в const функции-члене? Кто знает ...) указатель this должен быть const,но, как мы видим из опубликованного объявления operator<, метод не const.«Квалификаторы», упоминаемые в ошибках компилятора, - это то, что Стандарт называет «cv-квалификаторами».«cv» означает «const / volatile».

Когда компилятор говорит «Передача const X как this в Node::operator< сбрасывает квалификаторы», он действительно пытается сказать:

«Вы сказали, что X был постоянным, но затемВы пытались вызвать неконстантную функцию-член через const X. Чтобы сделать этот вызов, мне нужно было бы сбросить квалификатор const на X. Мне не разрешено делатьэто значит, что вы должны исправить свой код. "

Квалификаторы, которые здесь" отбрасываются ", являются квалификаторами самого метода.Другими словами, operator< должна быть константной функцией-членом, но это не так.

1 голос
/ 26 сентября 2011 
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>());
...