如何在嵌套映射（C++）中有效地搜索键？

Question

我有一个嵌套的多图 - 地图结构如下：

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，但似乎我必须逐个元素地循环直到我找到内键。

Answer 1

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

通常，在 std::map 中搜索键最有效的方法是使用 find 成员函数：

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

如何在嵌套映射（C++）中有效地搜索键？

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

c++

nested

multimap