Итерация над вектором и добавление объекта, на самом деле указываемого итератором как ключ на карте

Question

В классе Graph я создал неупорядоченную карту объектов класса Vertex как ключ и float как отображаемое значение. В классе вершин есть функция 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; 
    } 
}; 

И заголовок графика:

#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); 
}; 

В .cpp файле класса Graph Я создал функцию, которая перебирает вектор 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(); 
    } 
    */ 
} 

И вот проблема. Я не могу изменить параметр функции hash_value на не-const, поскольку он ожидает параметр const &. Также он не может быть использован позже, когда я должен добавить его в карту по мере получения ошибки:

двоичный '==': оператор не найден, который принимает левый операнд типа 'const Vertex' (или нет приемлемой конверсии)

Я пробовал разные души, чтобы преодолеть это, но я недостаточно экспрессирован, чтобы сделать это. Любые подсказки приветствуются.

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; 

Как вы можете видеть, что по умолчанию в std::equal_to<Vertex>, который ищет operator==, но вы не выполнили это. Самое простое - добавить его.

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)) или вы в конечном итоге с неопределенным поведением.