Как эффективно искать ключ во вложенной карте (C ++)? - PullRequest
Новая
       15

Как эффективно искать ключ во вложенной карте (C ++)?

0 голосов
/ 24 октября 2019

У меня есть вложенная структура с несколькими картами, например: 

typedef std::vector< struct > dataVector_t;
typedef std::map< int, dataVector_t > intMap_t;    
typedef std::multimap< int1, intMap_t > intMultiMap_t

Какой самый эффективный способ поиска innerKey во внутренней карте?

Вот мой нынешний подход. Это работает, но это занимает слишком много времени. 

    intMap_t getInnerMap( const intMultiMap_t & outerMap, const int outerKey )
    {
    intMap_t returnMap; 

    if ( !outerMap.empty() )
    {
        for ( auto outerIt= outerMap.lower_bound( outerKey ); outerIt!= outerMap.upper_bound( outerKey ); outerIt++ )
        {
            auto innerMap= outerIt->second;

            if ( !innerMap.empty() )
            {
                for ( auto innerIt= innerMap.begin(); innerIt!= innerMap.end(); innerIt++ )
                {
                    returnMap.emplace( innerIt->first, innerIt->second);
                }
            }
        }
    }

    return returnMap;
}

dataVector_t MapData::getDataVector( const intMultiMap_t & outerMap, const int outerKey, const int innerKey ) 
{
    dataVector_t returnValue {};

    auto innerMap = getInnerMap( outerMap, outerKey );

    if ( innerMap.size() > 0 )
    {
        auto innerIter = innerMap.find( innerKey);
        if ( innerIter == innerMap.end() ) // innerKey not found
        {
            innerIter = innerMap.lower_bound( innerKey); //so find key just after innerKey
            if ( innerIter != innerMap.begin() )
            {
                --innerIter ; //find key just before innerKey
            }
        }

        returnValue = innerIter->second; 

    }

    return returnValue;
}

Я также смотрел на использование equal_range для определения диапазона моего innerMap, затем использовал lower_bound для нахождения innerKey, но мне кажется, что я должен проходить по элементам, пока не найду innerKey.

1 Ответ

0 голосов
/ 24 октября 2019

Какой самый эффективный способ поиска innerKey на внутренней карте?

Как правило, наиболее эффективный способ поиска ключа в std::map заключается в использовании функции-члена find: 

auto innerIt = outerIt->second.find(innerKey);
...