벡터 반복 반복 및지도에서 실제로 반복자가 가리키는 객체 추가

Question

그래프 클래스에서 필자는 Vertex 클래스 객체의 정렬되지 않은지도를 키로 만들고 매핑 된 값으로 떠있었습니다. 버텍스 클래스에는 사용자 정의 클래스 객체를 키로 사용하기 위해 구현 한 friend 함수 hash_value가 있습니다. http://boost.cowic.de//libs/functional/hash/examples/point.cpp. 그래프의

#include <string> 
#include <boost/functional/hash.hpp> 

class Vertex{ 
private: 
    std::string label; 
    int x; 
    int y; 
    int vertex_no; 
    bool visited; 
public: 
     Vertex(std::string _label, int coordinate_x, int coordinate_y); 
     void SetVertexNo(int n); 
     int GetPositionX(); 
     int GetPositionY(); 
     bool GetVisited(); 
     void SetVisitedTrue(); 
     bool IsVisited(); 
     std::string GetLabel(); 

friend std::size_t hash_value(Vertex const& v) { 
     std::size_t seed = 0; 
     boost::hash_combine(seed, v.x); 
     boost::hash_combine(seed, v.y); 

     return seed; 
    } 
}; 

그리고 헤더 : 그래프 클래스의 .cpp 파일에서

#include "Vertex.h" 
#include <vector> 
#include <unordered_map> 
#include <limits> 
#include <boost/functional/hash.hpp> 
#include <boost/unordered_set.hpp> 
#include <boost\unordered_map.hpp> 
class Graph{ 
    private: 
     const int VERTICES_MAX = 120; 
     const int VERTICES_MIN = 5; 

     std::vector<Vertex> vertices_list; 
     float cost_matrix[120][120]; 

     struct Edge { 
     std::string vertex1; std::string vertex2; float weight; }; 
     std::vector<Edge> edge_list; 

     boost::unordered_map<Vertex, float> KEY; 

    public: 
     Graph(int num_of_vertices); 
     float SetEdgeWeight(Vertex* v1, Vertex* v2); 
     void SetGraphEdgesWeight(); 
     void DisplayWeightMatrix(int num_of_vertices); 
     void DisplayVerticesData(); 
     void MatrixToEdgeList(); 
     void DisplayList(); 

     void Christofides(Graph& g); 
}; 

나는 벡터 vertices_list을 반복하고 실제로 객체

을 unordered_map도 할 수있는 열쇠로 반복자가 가리키는되는 추가 기능을 작성

Graph::Graph(int num_of_vertices){ 
    typedef boost::mt19937 RNGType; ///Mersenne twister generator 
    RNGType rng(time(0)); 

    boost::uniform_int<> zero_to_thousand(0, 1000); 
    boost::variate_generator< RNGType, boost::uniform_int<> > point(rng, zero_to_thousand); 
/*-----------------------------------------------------------------------------------*/ 
    for (int i = 0; i < num_of_vertices; ++i) { 
     std::string vertex_label; 
     std::cout << "Vertex name: " << std::endl; 
     std::cin >> vertex_label; 
     Vertex* V = new Vertex(vertex_label, point(), point()); 
     V->SetVertexNo(i); 
     vertices_list.push_back(*V); 

     SetGraphEdgesWeight(); 
     MatrixToEdgeList(); 
    } 
} 
float Graph::SetEdgeWeight(Vertex* v1, Vertex* v2) { 
    int absolute_x = (v1->GetPositionX() - v2->GetPositionX()); 
    int absolute_y = (v1->GetPositionY() - v2->GetPositionY()); 
    float edge_weight = (float)(sqrt(pow(absolute_x,2)+pow(absolute_y,2))); 
    return edge_weight; 
} 
void Graph::SetGraphEdgesWeight() { 
    int i = 0; 
    for (std::vector<Vertex>::iterator it = vertices_list.begin(); it != vertices_list.end(); ++it) { 
     Vertex* pointer = &*it; 
     int n = 0; 
     for (std::vector<Vertex>::iterator it2 = vertices_list.begin(); it2 != vertices_list.end(); ++it2) { 
      Vertex* pointee = &*it2; 
      //cost_matrix[i][n] = SetEdgeWeight(pointer, pointee); 
      if (pointee->IsVisited()==true) { 
       cost_matrix[i][n] = cost_matrix[n][i]; 
      } 
      else if(it == it2){ 
       cost_matrix[i][n] = 0; 
      } 
      else { 
       pointer->SetVisitedTrue(); 
       cost_matrix[i][n] = SetEdgeWeight(pointer, pointee); 
      } 
      ++n; 
     } 
     ++i; 
    } 
} 
void Graph::DisplayWeightMatrix(int num_of_vertices) { 
    for (int i = 0; i < num_of_vertices; ++i) { 
     for (int j = 0; j < num_of_vertices; ++j) { 
      std::cout << "*" << " " << cost_matrix[i][j] << " "; 
     } 
     std::cout << "*" << std::endl; 
    } 
} 
void Graph::DisplayVerticesData() { 
    int i = 1; 
    for (std::vector<Vertex>::iterator it = vertices_list.begin(); it != vertices_list.end(); ++it) { 
     std::cout << "Vertex no: " << i << " " << "x:" << it->GetPositionX() <<" "<< "y:" << it->GetPositionY() << std::endl; 
     ++i; 
    } 
} 
void Graph::MatrixToEdgeList() { 
    int i = 0; 
    for (std::vector<Vertex>::iterator it = vertices_list.begin(); it != vertices_list.end(); ++it) { 
     int n = 0; 
     for (std::vector<Vertex>::iterator it2 = vertices_list.begin(); it2 != vertices_list.end(); ++it2) { 
      //std::vector<Vertex>::iterator it3 = ++it2; 

      if (cost_matrix[i][n]==0) { 
       ++n; 
       break; 
      } 
      else { 
       struct Edge* e = new struct Edge; 
       e->vertex1 = it->GetLabel(); 
       e->vertex2 = it2->GetLabel(); 
       e->weight = cost_matrix[i][n]; 
       edge_list.push_back(*e); 
       ++n; 
      } 
     } 
     ++i; 
    } 
} 
void Graph::DisplayList() { 
    for (std::vector<Edge>::iterator it = edge_list.begin(); it != edge_list.end(); ++it) { 
     std::cout << "Starting vertex: " << it->vertex1 << " " << "Ending vertex: " << it->vertex2 << " " << "Edge's weight: " << it->weight<<"\n"; 
    } 
} 
void Graph::Christofides(Graph& g) { 
    for (std::vector<Vertex>::iterator it = vertices_list.begin(); it != vertices_list.end(); ++it) { 
     Vertex* pointer = &*it; 
     g.KEY.insert(std::pair<Vertex,float>(*pointer, std::numeric_limits<float>::max())); 
     //KEY.emplace(*pointer, std::numeric_limits<float>::max()); 
    } 


    /* 
    for (auto v : g.vertices_list) { 

     //KEY.insert(*v_pointer, std::numeric_limits<float>::max()); 
     //KEY.insert(std::make_pair(v, std::numeric_limits<float>::max())); 
     //KEY[v] = std::numeric_limits<float>::max(); 
    } 
    */ 
} 

그리고 여기에 문제가 있습니다. const & 매개 변수를 예상하므로 hash_value 함수의 매개 변수를 non-const로 변경할 수 없습니다. 또한 나중에 오류를 얻을 때 맵에 추가해야 할 때 사용할 수 없습니다.

바이너리 '==': 'const Vertex'유형의 왼쪽 피연산자를 사용하는 연산자가 없습니다 (또는 받아 들일만한 변환이 없다.)

나는 이것을 극복하기 위해 다른 soultion을 시도했지만 그렇게하기에는 충분하지 않다. 어떤 힌트라도 환영합니다.

Answer 1

정렬되지 않은 컨테이너의 경우 해시 함수와 동등 비교가 필요합니다. 예 : 표준 라이브러리에서 :

template< 
    class Key, 
    class T, 
    class Hash = std::hash<Key>, 
    class KeyEqual = std::equal_to<Key>, 
    class Allocator = std::allocator< std::pair<const Key, T> > 
> class unordered_map; 

당신은 operator==를 검색하는 std::equal_to<Vertex>에 그것을 기본값을 볼 수 있지만 당신은 구현하지 않은 것처럼. 가장 쉬운 방법은 그것을 추가하는 것입니다.

bool operator==(Vertex const& other) const { 
     return std::tie(x,y) == std::tie(other.x, other.y); 
    } 

평등과 해시 함수 (의미 : a==b는 b==a 및 hash(a)==hash(b)을 의미) "동의"해야합니다 또는 당신이 정의되지 않은 동작으로 끝낼.