Не удается вставить различные значения структуры в карту

#c #dictionary

Вопрос:

Я использую узел для удержания (x, y) координатора и пытаюсь вставить 4 узла в карту. Следующий код печатает только 2 узла, почему?

 {0,0}, 0
{1,2}, 3

Если я изменю код оператора перегрузки ‘

 bool operator<(const Node amp;ob) const
{
    return x < ob.x or y < ob.y;
}

Он печатает все 4 узла. Мое понимание оператора

код

 #include <iostream>
#include <map>

template<typename T1, typename T2>
struct Node
{
    T1 x;
    T2 y;

    Node(T1 x, T2 y): x(x), y(y) {}

    bool operator<(const Node amp;ob) const
    {
        return x < ob.x and y < ob.y;
    }
    
    bool operator==(const Node amp;ob) const
    {
        return x == ob.x and y == ob.y;
    }
    
};

int main()
{
    std::map<Node<int, int>, int> map =
    {
        {{0, 0}, 0},
        {{0, 1}, 1},
        {{1, 0}, 2},
        {{1, 2}, 3}
    };

    for (const auto amp;entry: map)
    {
        auto key = entry.first;
        std::cout << "{" << key.x << "," << key.y << "}, " << entry.second << std::endl;
    }

    return 0;
}

1.std::сопоставьте требования, которые operator< создают отношения «строгого слабого порядка», которых у вас нет. Простое исправление состоит в том, чтобы заменить содержимое operator< на return std::tie(x, y) < std:;tie(ob.x, ob.y); std::map также синтезирует тест на равенство из !operator<(a, b) amp;amp; !operator<(b, a). см. en.cppreference.com/w/cpp/container/map

2. @RichardCritten разве это не сделало бы то же самое, что делает его текущая перегрузка?

3. @smac89 std::tie проводит return x < ob.x || (x == ob.x amp;amp; y < ob.y); лексикографическое сравнение. см. (3) здесь — en.cppreference.com/w/cpp/utility/tuple/operator_cmp

4. Я думаю, что лучше задать вопрос: «Куда делся мой контент?» Если карта просто игнорирует определенные записи, это совершенно другая проблема, но, возможно, то, что не было напечатано, просто никогда не попадало на карту. Вам следует расследовать это

5. @smac89 Недостающие записи, вероятно, никогда не попадали на карту в первую очередь потому, что неисправный компаратор заставил карту поверить, что некоторые из этих записей были дубликатами.

Ответ №1:

std::map считает два элемента равными , если для двух ключей a и b компаратор (в вашем случае по умолчанию std::less ) выполняет

 !comp(a, b) amp;amp; !comp(b, a)

Давайте проверим ваше дело:

Сначала вы вставляете ключ Node<int, int>(0, 0) , затем ключ Node<int, int>(0, 1) . Для этих элементов (и ваших operator< ) выполняется следующее:

 !std::less(Node<int, int>(0, 0), Node<int, int>(0, 1))
amp;amp; !std::less(Node<int, int>(0, 0), Node<int, int>(0, 1)) 
=>
!(Node<int, int>(0, 0) < Node<int, int>(0, 1))
amp;amp; !(Node<int, int>(0, 1) < Node<int, int>(0, 0))
=>
!(0 < 0 amp;amp; 0 < 1) amp;amp; !(0 < 0 amp;amp; 1 < 0)
=>
!(false amp;amp; true) amp;amp; !(false amp;amp; false)
=> !false amp;amp; !false
=> true

Таким образом, оба узла считаются равными, и вставка не происходит. То же самое относится и к Node<int, int>(1, 0) .

Вставка Node<int, int>(1, 2) работ, потому что

 !(0 < 1 amp;amp; 0 < 2) amp;amp; !(1 < 0 amp;amp; 2 < 0)
=>
!(true amp;amp; true) amp;amp; !(false amp;amp; false)
=>
!true amp;amp; !false
=>
false amp;amp; true
=>
false

Вы можете устранить проблему с помощью другого operator< , например, как сказано в комментариях, с помощью std::tie .

1. Спасибо, дтелл. Я нашел решение, как это исправить, но просто не понимаю. Я верю, что вы объясните первопричину. Просто любопытно, почему он изначально определяет равенство, !comp(a, b) amp;amp; !comp(b, a) вместо того чтобы просить реализовать оператор ‘==’?

2. @user1256475, потому std::map что требуется строгий Слабый порядок .

3. @user1256475 std::map требует operator< , чтобы он соответствовал требованиям к сложности и порядку. Учитывая, что operator== это может быть синтезировано из operator< , нет необходимости std::map требовать этого или использовать это. Это также гарантирует, что тест на равенство и тест «меньше, чем» проверяют одни и те же данные и дадут одинаковые результаты.