Каков самый быстрый способ проверить, существует ли значение в std::map?

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

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

Что касается значений, map на самом деле не отличается от списка или вектора. Таким образом, исчерпывающий (линейный) поиск — самый быстрый способ.

Если у вас нет очень больших наборов данных (более 100 000 или около того), время доступа к картам не должно вас беспокоить, поскольку в любом случае оно будет очень незначительным, потому что у вас уже есть int в качестве ключа. Чтобы проверить, существует ли value на карте или нет, вы должны просто использовать итераторы или, может быть, std::find_if. Неважно, какой способ вы выберете, он все равно будет линейным (O (n)).

// both examples assume you using c++ 17 standart
// simple cycle variant
bool is_value_exists(auto const &map, int val) {
  for (auto const &[key, value] : map) {
    if (value == val) return true;
  }
  return false;
}
// find if version
#include <algorithm>
bool is_value_exists2(auto const &map, int val) {
  return std::find_if (
    map.begin(), 
    map.end(),
    [val](auto const &kv) { return kv.second == val; }
  ) != map.end();
}

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

Если вам нужно искать значение, используйте другую структуру данных (или отдельную карту).

Единственный способ поиска значения на карте — линейный (O(N)), но из-за накладных расходов на кеширование при итерации по структуре данных карты он будет даже медленнее, чем итерация, например. вектор.

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

myVec[value]=myMap.find(key); // at time of inserting a new key

Таким образом, вы можете просто использовать значение в качестве ключа (индекса) в векторе и напрямую обращаться к содержимому карты с помощью этого указателя после сравнения с nullptr.

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

Вы также можете использовать map-iteration-search в качестве резервного хранилища кэша с прямым отображением (который работает быстрее всего для целочисленных ключей (значения здесь)). Все попадания в кеш будут обслуживаться за счет побитовой операции & с некоторым значением, например 8191, 4095 и т. д. (O(1)). Все промахи кеша по-прежнему потребуют полной итерации элементов карты, которая выполняется медленно (O(N)).

Таким образом, если коэффициент попаданий в кэш близок к 100%, он может приближаться к O(1), в противном случае это будет O(N), что будет медленным.