Итерация по std :: map с пользовательской реализацией оператора less дает меньше элементов, которые она содержит - PullRequest
Новая
       8

Итерация по std :: map с пользовательской реализацией оператора less дает меньше элементов, которые она содержит

2 голосов
/ 18 марта 2020

Предполагается, что у меня есть следующая простая программа (http://cpp.sh/5sygh): 

#include <map>
#include <iostream>

using Key = std::pair<unsigned long, unsigned long long>;

struct KeyLess {
  bool operator()(const Key& lhs, const Key& rhs) {
      if (lhs.first < rhs.first) {
        return  true;
      }

      if (lhs.second < rhs.second) {
        return true;
      }

      return false;
  }
};

int main() {
    std::map< Key , int, KeyLess> m;
    m[Key{2, 169}] = 1;
    m[Key{1, 255}] = 2;
    m[Key{1, 391}] = 3;
    m[Key{1, 475}] = 4;

    std::cout << "Elements in map: " << m.size() << std::endl;     
    for(const auto &x: m) {
        std::cout <<"Value: "<< x.second << std::endl;
    }
}

Вывод содержит только 2 элемента вместо 4 на карте: 

Elements in map: 4
Value: 2
Value: 1

Что мне здесь не хватает?

Ответы [ 5 ]

8 голосов
/ 18 марта 2020

Ваш оператор less должен быть: 

struct KeyLess {
  bool operator()(const Key& lhs, const Key& rhs) {
      if (lhs.first < rhs.first) {
        return  true;
      }

      if (lhs.first == rhs.first && lhs.second < rhs.second) {
        return true;
      }

      return false;
  }
};

Когда вы сравниваете структуры с несколькими элементами, это может помочь воспринимать структуры как слова, а элементы как символы.

В этой модификации Оператор less работает лексикографически, как вы сравниваете два слова одинаковой длины при их сортировке: вы продолжаете сравнение на следующей позиции, в то время как слова имеют одинаковый символ в текущей позиции, и решаете, когда символы в текущей позиции различаются. Если вы дойдете до конца обоих слов, слова будут равны.

7 голосов
/ 18 марта 2020

Вы можете скрыть тонкости компаратора и устранить ошибку (уже объясненную @ MarkoMahnič), используя std::tie. 

bool operator()(const Key& lhs, const Key& rhs)
{
   return std::tie(lhs.first, lhs.second) < std::tie(rhs.first, rhs.second);
}
7 голосов
/ 18 марта 2020

Ваша функция сравнения не соответствует требованиям строгого слабого порядка .

В SWO, если A (!(a<b) && !(b<a)), то a == b. Две клавиши не должны быть меньше друг друга.

Для ваших клавиш и использования функции сравнения 

Key{2, 169} < Key{1, 255} // this is true because 169 < 255
Key{1, 255} < Key{2, 169} // this is also true because 1 < 2

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

Мое предлагаемое решение: поскольку ваши ключи std::pair s, вам не нужно определять новый компаратор. std::pair по умолчанию уже использует лексикографическое сравнение.

4 голосов
/ 18 марта 2020

Ваш компаратор не соответствует требованиям std::map, он должен обеспечить строго слабый порядок . К счастью, std::tuple реализует это для вас, если вам нужно сравнить несколько значений: 

struct KeyLess {
  bool operator()(const Key& lhs, const Key& rhs) {
      return std::tie(lhs.first, lhs.second) < std::tie(rhs.first, rhs.second);
  }
};

В вашем случае вам вообще не нужен пользовательский компаратор, так как оператор std::pair * < уже имеет такое же поведение.

0 голосов
/ 18 марта 2020

Ваш код KeyLess приводит к некорректному сравнению: 

KeyLess cmp;
std::cout << cmp(Key{2, 169},Key{1, 391})<< std::endl;  // yields true
std::cout << cmp(Key{1, 391},Key{2, 169})<< std::endl;  // yields true

Когда оба сравнения дают ложь, это означает, что ключи равны, и когда они дают истину, поведение итератора карты не определено. Это связано с тем, что map сортирует свои элементы.

Обратите внимание, что operator() должно быть const, иначе программа может не скомпилироваться со стандартом C ++ 17 и более поздними версиями. Как возможный вариант: 

#include <map>
#include <iostream>

using Key = std::pair<unsigned long, unsigned long long>;

struct KeyLess {
  bool operator()(const Key& lhs, const Key& rhs) const {
      if (lhs.first < rhs.first) {
        return  true;
      }
      else  if (lhs.first > rhs.first)
          return  false;

      if (lhs.second < rhs.second) {
        return true;
      }

      return false;
  }
};


int main() 
{
    std::map< Key , int, KeyLess > m;
    m[Key{2, 169}] = 1;
    m[Key{1, 255}] = 2;
    m[Key{1, 391}] = 3;
    m[Key{1, 475}] = 4;

    std::cout << "Elements in map: " << m.size() << std::endl;     
    for(const auto &[key, value]: m) {
        std::cout << "Key: " << key.first << ", " << key.second << " Value: "<< value << std::endl;
    }
}
...