Почему map.find использует <оператор, а не == оператор? - PullRequest
Новая
       28

Почему map.find использует <оператор, а не == оператор?

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

Пытаясь выяснить, почему моя программа глючила, я обнаружил, что:

В std::map ключи сравниваются с использованием значения, меньшего operator <, при выполнении поиска.

(из std :: map find не работает в C ++ ).

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

Ответы [ 2 ]

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

Поскольку std::map отсортировано, вы можете воспользоваться тем, что все элементы, которые меньше x, расположены до x, а все элементы, которые больше, расположены после x. Это означает, что вы можете выполнить бинарный поиск , чтобы найти элемент, который гораздо более эффективен, чем линейный поиск (т. Е. Просто просматриваете каждый элемент в последовательности).

Например, эффективный поиск число 55 в коллекции может выглядеть примерно так: 

 1 1 2 3 5 8 13 21 34 55 89 144
[          ^                   ]  8 is too low

 1 1 2 3 5 8 13 21 34 55 89 144
            [      ^           ]  34 is too low

 1 1 2 3 5 8 13 21 34 55 89 144
                     [   ^     ]  89 is too high

 1 1 2 3 5 8 13 21 34 55 89 144
                     [^ ]         55 is a match!

Это имеет сложность O (log n) , тогда как просто сравнение с == имеет сложность O ( п) . Другими словами, для поиска элемента на карте из миллиона элементов требуется только около log 2 (10 6 ) ≈ 20 сравнений, тогда как если бы мы сравнивали с ==, это нужно около 10 6 сравнений, огромная разница для больших коллекций.

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

Что вас больше всего удивляет, так это утверждение в ссылке, на которую вы ссылались:

Я создал карту ха sh

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

Теперь ваш вопрос в основном обращается к проблеме со структурой данных.

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

  • левый сын узла меньше текущего узла
  • правый сын узла больше текущего узла

Обратите внимание, что я использовал "меньше" или "больше" только для того, чтобы вы поняли. Более ценно, учитывая двоичный предикат p, используемый для организации дерева, которое удовлетворяет требованиям строгого слабого упорядочения, мы предполагаем, что текущий узел равен N, тогда:

  • p(N, N->left) - это истина
  • p(N, N->right) ложно

Итак, теперь вы находитесь на вершине дерева, чтобы найти правильный узел, вам нужно продолжать сравнивать имеющееся у вас значение с текущим узлом и принять решение в каком направлении вам следует go.

И вы можете спросить, почему == не требуется, потому что когда предикат p удовлетворяет требованию строгого слабого упорядочения, следующие два выражения эквивалентны (не точно, но при аренде интересующая нас часть эквивалентна):

A. !(p(A, B) || p(B, A))

B. A == B

Вы можете спросить себя, когда A не меньше B, а B не меньше A, какова связь между A и B?

...