Я разработал какой-то алгоритм линейного поиска (который я обнаружил позже) и не был удовлетворен скоростью функции. Поэтому я искал более быструю функцию и нашел собственную функцию карты: map::find.
Это было невероятно быстрее, чем линейный алгоритм, который я использовал.
std::map предназначен для сортировки данных при их вставке в контейнер. Это одна из его основных работ. Это также причина, по которой вы должны определить какой-то частичный порядок для данных, которые вы помещаете в std::map.
Это означает, что каждая вставка занимает немного больше времени, чем вставка в другие контейнеры (вставка в std::list - если у вас есть точка вставки - например, O (1), как добавление к std::vector или добавление / добавление к std::deque). Но при поиске гарантированно используется бинарный поиск (или, скорее, для навигации по красно-черному дереву за std::map (в разделе «Преждевременная или разумная оптимизация»)).
В другом примере функция поиска STL также была намного быстрее, чем другая линейная функция, которую я использую.
Но как это возможно? Если вы используете алгоритм двоичного поиска, вам нужно сначала отсортировать карту, что займет (гипотетически) больше времени, чем больше ваша карта.
В этом нет ничего гипотетического. Сортировка данных занимает много времени, и всегда больше времени занимает больше элементов данных.
std::find может обрабатывать несортированные данные, поэтому он должен быть реализован как линейный поиск (сравните std::binary_search / std::lower_bound). Но std::find разрешено быть скрытным и развернуть циклы, сравнивать более одного элемента за раз (если элементы маленькие, и особенно, если они являются примитивными типами, которые поддаются низкоуровневой обработке битов) и т. Д.
Кроме того, как узнать алгоритмы этих основных функций? Есть ли список или какая-то база данных, чтобы это выяснить?
Лично я выучил много алгоритмов, прочитав то, что было доступно в STL и некоторых других языках. Сначала мне было легче изучить контейнеры.