Поиск по паре ключ-значение

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

Пример:

#include <algorithm>
#include <iostream>
#include <map>
int main()
{
    std::multimap<int, char> dict {
        {1, 'A'},
        {2, 'B'},
        {2, 'C'},
        {2, 'D'},
        {4, 'E'},
        {3, 'F'},
    };
    // Производится поиск пары {2, 'C'}
    auto range = dict.equal_range(2);
    auto pair = std::find_if(range.first, range.second,
                             [](auto& el){ return el.second == 'C'; });
    if (pair != range.second) {
        std::cout << "Найденo!" << std::endl;
    } else {
        std::cout << "Нету подходящих элементов" << std::endl;
    }
}