std :: map уникальная функция std :: less <> для 2D-точки в качестве ключа - PullRequest
Новая
       20

std :: map уникальная функция std :: less <> для 2D-точки в качестве ключа

4 голосов
/ 01 декабря 2011

Что ж, после четырех часов отладки, запутавшись, насколько я мог, я выяснил причину проблемы ...

Я делаю какую-то программу, которая сохраняет некоторую точку в std :: map ивизуализировать их в моем окне.Но странно, некоторые точки не смогли попасть в карту. 

std::map<Point2, Prop*> m_Props_m;

void AddProp(std::pair<Point2, Prop*> p)
{
    m_Props_m.insert(p);
}

struct Point2
{
unsigned int Point2::x;
unsigned int Point2::y;
//--------
Point2::Point2()
    :x(0)
    ,y(0)
{}

bool Point2::operator< (const Point2& b) const
{
    return ( x+y < b.x+b.y );
}

bool Point2::operator> (const Point2& b) const
{
    return ( x+y > b.x+b.y );
}
};

Слава богу, у меня есть некоторый опыт работы с бинарными деревьями, чтобы я мог выяснить причину моей проблемы.

Представьте, что мыесть 2 Point2. 

Point2 a(0,1);
Point2 b(1,0);

Как вы можете видеть, с оператором <метод, который я написал, он вернул бы false, а оператор> также вернул бы false.Таким образом, если a уже есть на карте, а b вставлено, вставка завершится неудачей.

Теперь все хорошо, но как я могу это исправить?Можно ли как-нибудь использовать оператор «меньше» для 2D-точки, который позволил бы мне сохранять каждую уникальную точку на карте?

Ответы [ 3 ]

11 голосов
/ 01 декабря 2011

std::map вообще не использует operator>, поэтому вам не нужно об этом беспокоиться.

Для сортировки по нескольким полям (в данном случае два) используйте так:называется "лексикографическим порядком", что означает, что первое поле является наиболее важным, а второе разрывает связи: 

bool operator<(const Point2 &lhs, const Point2 &rhs) {
    return (lhs.x < rhs.x) || ((lhs.x == rhs.x) && (lhs.y < rhs.y));
}
2 голосов
/ 01 декабря 2011

Ваша функция сравнения считает точки эквивалентными, если сумма их координат равна. Например, (2, 5) эквивалентно (3, 4), потому что 2 + 5 = 3 + 4. Точки, которые уже имеют свой эквивалент на карте, этого не сделают.

Лучше было бы сравнить сначала по x, а затем по y, если значение x в обеих точках равно. 

bool operator< (const Point2 &lhs, const Point2 &rhs) {
    return (lhs.x < rhs.x) || ((lhs.x == rhs.x) && (lhs.y < rhs.y));
}
1 голос
/ 01 декабря 2011

Это должно сработать: 

bool Point2::operator< (const Point2& b) const
{
    if (x<b.x) return true;
    else if (!(b.x<x) && y<b.y) return true;
    else return false;
}

std::map использует только operator<. Если !(a<b) && !(b<a), a и b эквивалентны (не совпадают с одинаковыми), и, следовательно, на карте будет храниться только один из них. operator> не используется.

Может не иметь смысла сравнивать Point2 в других случаях, поэтому, чтобы избежать недоразумений, я бы предложил вам предоставить функцию сравнения для вашей карты и удалить operator< из вашего класса. 

bool mapLessPoint2(const Point2& a, const Point2& b);
std::map<Point2, Prop*, &mapLessPoint2> m_Props_m;

По моему мнению, перегрузка оператора должна использоваться только тогда, когда это имеет смысл для данного типа, и что одна точка в 2D-пространстве больше, чем другая точка в 2D-пространстве, не является интуитивной.

...