Ввод значений в карту со структурой в качестве ключа

Question

У меня есть карта со структурой в качестве ключа, я перегружен оператором <, но карта хранит каждую запись как отдельные ключи, даже если они одинаковые.Код выглядит следующим образом:

#include <iostream>
#include <vector>
#include <map>

using namespace std;

struct vertex 
{
    int color;
    vertex *pi;
    int index;

    bool operator<(const vertex & v ) const {
        return this->index < v.index;
    }
    bool operator==(const vertex & v) const {
        return this->index == v.index;
    }
};


int main()
{
    int x, y, num_edges;
    vector<vertex* > v;
    vertex *temp1, *temp2, *temp;
    map<vertex*, vector<vertex*> > m;
    map<vertex*, vector<vertex*> >::iterator it;

    cout << "\nEnter no. of edges: ";
    cin >> num_edges;

    for( int i = 0; i < num_edges; i++ )
    {
        cout << "\nEnter source: ";
        cin >> x;
        cout << "\nEnter dest: ";
        cin >> y;

        temp1 = new vertex;
        temp2 = new vertex;
        temp1->index = x;
        temp2->index = y;

        m[temp1].push_back(temp2);
        m[temp2].push_back(temp1);
    }

    temp1 = new vertex;
    temp2 = new vertex;

    cout << "\nPrinting map: " << endl;
    for( it = m.begin(); it != m.end(); it++ )
    {
        temp = (*it).first;

        cout << temp->index << "\t";

        v = (*it).second;
        for( int i = 0; i < v.size(); i++ )
        {
            temp1 = v[i];
            cout << temp1->index << "\t";
        }
        cout << "\n";
        v.clear();
    }
    for( it = m.begin(); it != m.end(); it++ )
    {
        temp = (*it).first;
        v.push_back(temp);
    }
    return 0;
}

Вывод, который я получаю сейчас:

Enter no. of edges: 4

Enter source: 1

Enter dest: 3

Enter source: 4

Enter dest: 3

Enter source: 4

Enter dest: 2

Enter source: 2

Enter dest: 1

Printing map: 
1   3   
3   1   
4   3   
3   4   
4   2   
2   4   
2   1   
1   2   

Но это должно быть:

1 3 2

2 4 1

3 1 4

4 3 2

Где яидет не так?

Answer 1

std :: map будет сравнивать тип, который вы даете ему как ключ (vertex*), но вы определяете оператор < для вершины.

Вы можете использовать структуру как ключи, или- если вам нужно использовать указатели - вы должны дать карте способ сравнить указатели.

Теперь std::map использует std::less в качестве предиката сравнения, который определен в термине < (поэтому, используя саму структуру, вы можете достичь результата, перегрузив <).

Вы можете либо:

o) определить себе предикат, который сравнивает вершину *: он можетбыть

template <class T> //assume T is a pointer or pointer-like class
struct redirected_less : public std::binary_function <T,T,bool> 
{
    bool operator() (const T& x, const T& y) const {return *x < *y;}
};

и затем определить вашу карту как

std::map<vertex*, vector<vertex*>,  redirected_less<vertex*> >

o) специализировать std :: less для вершины * как

namespace std
{
     template <> 
     struct less<vertex*> : binary_function <vertex*,vertex*,bool> 
     {
         bool operator() (vertex* x, vertex* y) const {return *x < *y; }
     };
}

и объявить вашу картукак

std::map<vertex*, vector<vertex*> >

как обычно.

Я лично предпочитаю первое (дает более локализованный код, меньше "загадочного" в будущих чтениях)

Answer 2

map<vertex*, vector<vertex*> > m;// its key type vertex*  

м использует

bool operator < (vertex * const, vertex* const) ;

при заказе

Так что вам нужно перегрузить

bool operator < (vertex * const, vertex* const); 

у нас тут проблема. мы не можем перегружать указатель. мы могли бы предоставить нашу собственную функцию сравнения, например:

struct cmp{ 
      bool operator ()(vertex * const first, vertex* const second)
      { return first.index < second->index;} 
 };
cmp _cmp;
map<vertex*, vector<vertex*>, cmp> m(_cmp);

Answer 3

Вы не можете использовать указатели в качестве ключей.Если вам нужны структуры, которые «одинаковы» в соответствии с вашими правилами, но они выделены из кучи с помощью new, тогда их указатели никогда не будут одинаковыми.

Используйте структуры, а не их указатели, как ключ.