How to efficiently seach key in nested map (C++)?

Question

I have a nested multimap - map structure like:

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

What is the most efficient way to search for the innerKey in the inner map?

Here is my current approach. It works, but it takes too long.

    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;
}

I've also looked at using equal_range to identify the range of my innerMap, then use lower_bound to find the innerKey, but it seems I have to loop through element by element until I find the innerKey.

Answer 1

What is the most efficient way to search for the innerKey in the inner map?

Generally, the most efficient way to search for a key in std::map is to use the find member function:

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