Какова сложность реализованного алгоритма?

Написал функцию, которая удаляет из массива строки, встречающиеся четное число раз. Мне нужно оценить ее временную сложность.

В ней два прохода по всем элементам входного массива, так что вроде как сложность равна O(N). Но там присутствует работа с std::map, операции с которым выполняются за O(logN). То есть, сложность должна быть O(N*LogN)? И возможно ли сделать ее в таком случае O(N)? Уточнение: порядок строк должен оставаться прежним, так что, сортировать нельзя.

std::vector<std::string> remove_even_strings(std::vector<std::string> & ref)
{
    std::vector<std::string> result;
    std::map<std::string, size_t> srch;
    
    for (auto & r : ref)
    {
        auto [f, s] = srch.insert(std::make_pair(r, 1));
        if (s == false)
        {
            srch.at(r) = srch.at(r) + 1;
        }
    }
    
    for (auto & r : ref)
    {
        if (srch.at(r) % 2 == 1)
        {
            result.push_back(r);
        }
    }
    
    return result;
}