Kompilieren Fehler, wenn sie in Einsatzpaar gesetzt

Question

Ich kann nicht verstehen, warum g ++ Fehler wie folgt zurück:

/usr/lib/gcc/x86_64-redhat-linux/4.1.2/../../../../include/c++/4.1.2/bits/stl_pair.h: In function 鈥榖ool std::operator<(const std::pair<_T1, _T2>&, const std::pair<_T1, _T2>&) [with _T1 = int, _T2 = stop]鈥 
/usr/lib/gcc/x86_64-redhat-linux/4.1.2/../../../../include/c++/4.1.2/bits/stl_function.h:227: instantiated from 鈥榖ool std::less<_Tp>::operator()(const _Tp&, const _Tp&) const [with _Tp = std::pair<int, stop>]鈥 
/usr/lib/gcc/x86_64-redhat-linux/4.1.2/../../../../include/c++/4.1.2/bits/stl_tree.h:921: instantiated from 鈥榮td::pair<typename std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator, bool> std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::insert_unique(const _Val&) [with _Key = std::pair<int, stop>, _Val = std::pair<int, stop>, _KeyOfValue = std::_Identity<std::pair<int, stop> >, _Compare = std::less<std::pair<int, stop> >, _Alloc = std::allocator<std::pair<int, stop> >]鈥 
/usr/lib/gcc/x86_64-redhat-linux/4.1.2/../../../../include/c++/4.1.2/bits/stl_set.h:321: instantiated from 鈥榮td::pair<typename std::_Rb_tree<_Key, _Key, std::_Identity<_Key>, _Compare, typename _Alloc::rebind<_Key>::other>::const_iterator, bool> std::set<_Key, _Compare, _Alloc>::insert(const _Key&) [with _Key = std::pair<int, stop>, _Compare = std::less<std::pair<int, stop> >, _Alloc = std::allocator<std::pair<int, stop> >]鈥 
newGraph.cpp:48: instantiated from here 
    /usr/lib/gcc/x86_64-redhat-linux/4.1.2/../../../../include/c++/4.1.2/bits/stl_pair.h:104: error: no match for 鈥榦perator<鈥in 鈥榑_x->std::pair<int, stop>::second < __y->std::pair<int, stop>::second鈥 

Hier ist mein Code:

#include <iostream> 
#include <vector> 
#include <string> 
#include <list> 

#include <set> 
#include <utility> // for pair 
#include <algorithm> 
#include <iterator> 

const int max_weight = INT_MAX; 

struct stop { 
    std::string name_stop; 
    int id_stop; 
    bool operator !=(const stop &rhs) const 
    { 
     return ((id_stop != rhs.id_stop) || (name_stop != rhs.name_stop)); 
    } 

}; 

struct neighbor { 

    stop target; 
    int weight; 
    neighbor(stop arg_target, int arg_weight) : target(arg_target), weight(arg_weight) { } 
}; 

std::list<stop> dijkstraComputeAndGetShortestPaths(stop src, 
              stop dst, 
              std::vector< std::vector<neighbor> > &adj_list, 
              std::vector<int> &min_distance, 
              std::vector<stop> &previous) 
{ 
    stop fake_stop; 
    fake_stop.id_stop = INT_MAX; 
    fake_stop.name_stop = "Null"; 

    std::list<stop> path; 
    int n = adj_list.size(); 
    min_distance.clear(); 
    min_distance.resize(n, max_weight); 
    min_distance[src.id_stop] = 0; 
    previous.clear(); 
    previous.resize(n, fake_stop); 
    std::set< std::pair< int, stop > > vertex_queue; 
    vertex_queue.insert(std::make_pair(min_distance[src.id_stop], src)); 

    while (!vertex_queue.empty()) 
    { 
     int dist = vertex_queue.begin()->first; 
     stop u = vertex_queue.begin()->second; 
     vertex_queue.erase(vertex_queue.begin()); 

     // Visit each edge exiting u 
     const std::vector<neighbor> &neighbors = adj_list[u.id_stop]; 

     for(std::vector<neighbor>::const_iterator neighbor_iter = neighbors.begin(); 
      neighbor_iter != neighbors.end(); 
     neighbor_iter++) 
     { 
      stop v = neighbor_iter->target; 
      int weight = neighbor_iter->weight; 
      int distance_through_u = dist + weight; 

      if (distance_through_u < min_distance[v.id_stop]) { 
       vertex_queue.erase(std::make_pair(min_distance[v.id_stop], v)); 

       min_distance[v.id_stop] = distance_through_u; 
       previous[v.id_stop] = u; 
       vertex_queue.insert(std::make_pair(min_distance[v.id_stop], v)); 

      } 

     } 
     if(u.id_stop == dst.id_stop) 
     { 
      std::cout << "Find : "; 
      for (; dst != fake_stop; dst = previous[dst.id_stop]) 
      { 
       path.push_front(dst); 
      } 

      return path; 
     } 
    } 
} 

int main() 
{ 

    std::vector< std::vector<neighbor> > adj_list(9); 
    stop stop_s; 
    stop_s.id_stop = 1001; 
    stop_s.name_stop = "A"; 

    stop stop_x; 
    stop_x.id_stop = 1002; 
    stop_x.name_stop = "B"; 

    adj_list[stop_s.id_stop].push_back(neighbor(stop_x, 5)); 

    stop_s.id_stop = 1003; 
    stop_s.name_stop = "C"; 

    adj_list[stop_x.id_stop].push_back(neighbor(stop_s, 15)); 

    stop_x.id_stop = 1004; 
    stop_x.name_stop = "D"; 

    adj_list[stop_s.id_stop].push_back(neighbor(stop_x, 20)); 

    stop_s.id_stop = 1001; 
    stop_s.name_stop = "A"; 

    std::vector<int> min_distance; 
    std::vector<stop> previous; 

    std::list<stop> path = dijkstraComputeAndGetShortestPaths(stop_s, stop_x, adj_list, min_distance, previous); 
    std::cout << "Distance from 1001 to 1004: " << min_distance[stop_x.id_stop] << std::endl; 
    //std::cout << "Path : "; 
    #if 0 
    for (int index = 0; index < path.size(); index++) 
    { 
     auto path_front = path.begin(); 
     std::advance(path_front, index); 

     std::cout << path_front->id_stop << " "; 

    } 
    std::cout << std::endl; 
    #endif 
    return 0; 
} 

Answer 1

std::set Sie benötigen einen operator < für die angeben Geben Sie es ein, oder Sie können Ihren eigenen Vergleichsfunktor als Vorlageparameter angeben. Da stop keine operator < hat, ist die operator < von std::pair nicht kompilierbar, da sie darauf angewiesen ist, die operator < der Typen zu verwenden, die sie enthält .. Sie müssen entweder einen eigenen Vergleichsfunktor angeben oder operator < für stop definieren.