Как я могу создать пользовательский неупорядоченный компаратор карт, который игнорирует определенные ключи при проверке равенства? - PullRequest
Новая
       17

Как я могу создать пользовательский неупорядоченный компаратор карт, который игнорирует определенные ключи при проверке равенства?

0 голосов
/ 26 апреля 2020

Я хотел бы создать пользовательскую функцию сравнения для отправки в find_if или другую функцию сравнения, которая для сравнения равенства требует, чтобы я игнорировал определенные ключи.

У меня есть набор, который содержит неупорядоченную карту. Давайте назовем это vecMap. vecMap выглядит как std::vector<std::unordered_map<std::pair<int, bool>, int>>.

В моем сценарии я хочу, чтобы два std::unordered_map<std::pair<int, bool>, int> были равны тогда и только тогда, когда ключи, второе значение которых не равно true, равны. Например,

Например,

Содержимое MapOne: 

Keys | Values
{1, false} | 10
{2, true}  | 15

Содержимое MapTwo: 

Keys | Values
{1, false} | 10

Эти две карты считаются равными, поскольку мы заботимся только о равенстве ключей, для которых key.second равно false.

Другой пример,

Содержимое MapOne: 

Keys | Values
{1, false} | 200
{2, true}  | 15

MapTwo Содержимое: 

Keys | Values
{1, false} | 10

Эти две карты считаются не равными, так как количество для единственного ключа что равно, то отличается.

Как я могу создать лямбда-выражение, которое реализует этот тип равенства?

Моя конечная цель - иметь std::vector<std::unordered_map<std::pair<int, bool>, int>>, который содержит неупорядоченные карты с ключами, которые истинны и находят соответствующую карту, которая равна другой карте, у которой никогда не будет ключа, который является истинным.

Например, 

using mapVec = std::vector<std::unordered_map<std::pair<int, bool>, int>>;

mapVec s{};

// Fill s with unordered maps
// g = std::unordered_map<std::pair<int, bool>, int>
// customEquality = [](){}; (some lambda)?

mapVec::iterator it = s.find(g, customEquality);

Мне нужен алгоритм find_if, который принимает мой std::unorderd_map<std::pair<int, bool>, int> и мой собственный лямбда-компаратор. Если есть еще более простой способ, я все уши.

1 Ответ

0 голосов
/ 26 апреля 2020

В таком случае, почему bool часть ключа?

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

Так что в этом случае было бы гораздо разумнее использовать std::vector<std::map<int, std::pair<int, int>>.

Учитывая, что используется карта, сравнительно легко сравнить две карты, используя std::lexicographical_compare и соответствующую функцию сравнения, поскольку содержимое карты отсортировано.

И эта функция сравнения будет сравнивать только первый элемент каждой пары (истинное число ).

Если key существует в одном орехе карты, а не в другом, а число true не равно 0, то это несоответствие.

Карта 1 тогда содержимое будет: 

1, 0, 10
2, 15, 0
  • Первое число эквивалентно вашему ключу. Первое
  • Второе число - это число true (ваше значение, когда ваш ключ . секунды - это правда)
  • третье число - верно с ount (ваше значение, когда значение key.second равно false)

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

  • Было бы более уместным поместить данные true и false в отдельные контейнеры?
    • Для каждого элемента в векторах?
    • Или с использованием различных векторов?
  • Используются ли данные в основном только для сопоставления?
    • Если это так, использование set из tuple может упростить написание некоторого алгоритма.
    • Кроме того, может быть возможно инвертировать порядок bool и int в ключе, чтобы поиск можно было применить к поддиапазону (часть true ), который можно легко найти, выполнив поиск lower_bound из {true, INT_MIN }.
...