How to lookup for a key in a std::map and iterate backwards

Question

I have a std::map which holds pointers to a class.

I need to lookup a key and iterate backwards until I get to the first item.

std::map::reverse_iterator does not support the std::map::find() method, so I have made a workaround, decreasing the direct iterator until the item just before begin() and then deal with the first item outside of the loop.

Is there another way? Is there an rfind() method?

Below is the code I am using:

if( MnbObj->ParNoMapa.IsEmpty() && MnbObj->TipoMan == "D" ) // Desligou, procurar à frente
{
    // Trocar por iterator
    itFind = MapFind.find( itManobra->first );
    if( itFind != MapFind.end() )
    {
        ++itFind;

        while( itFind != MapFind.end() )
        {
            MnbFind = itFind->second;

            if( MnbFind->EqpId->UndSig == Unidade &&
                MnbFind->EqpId->CodOper == Equipamento )
            {
                if( MnbFind->TipoMan == "D" )
                {
                    Logger->AddLogEntry("Manobra "+itManobra->first+
                                  " faltou religamento antes de "+
                                  MnbFind->DtHoraMan.FormatString("dd/mm/yyyy hh:nn:ss"), evsDontCare);
                    break;
                }
                else
                {
                    if( !MnbFind->Reconhece.IsEmpty() )
                        MnbObj->ParNoMapa = itFind->first;
                    break;
                }
            }

            ++itFind;
        }
    }
}
else if( MnbObj->ParNoMapa.IsEmpty() && MnbObj->TipoMan == "L" ) // Ligou, procurar para trás
{
    itFind = MapFind.find( itManobra->first );
    if( itFind != MapFind.begin() )
    {
        --itFind;

        while( itFind != MapFind.begin() )
        {
            MnbFind = itFind->second;

            if( MnbFind->EqpId->UndSig == Unidade &&
                MnbFind->EqpId->CodOper == Equipamento )
            {
                if( MnbFind->TipoMan == "L" )
                {
                    Logger->AddLogEntry("Manobra "+itManobra->first+
                                 " faltou desligamento após "+
                                 MnbFind->DtHoraMan.FormatString("dd/mm/yyyy hh:nn:ss"), evsDontCare);
                    break;
                }
                else
                {
                    if( !MnbFind->Reconhece.IsEmpty() )
                        MnbObj->ParNoMapa = itFind->first;
                    break;
                }
            }

            --itFind;
        }
        // resolver o primeiro
        itFind = MapFind.begin();

        MnbFind = itFind->second;

        if( MnbFind->EqpId->UndSig == Unidade &&
            MnbFind->EqpId->CodOper == Equipamento )
        {
            if( MnbFind->TipoMan == "L" )
            {
                Logger->AddLogEntry("Manobra "+itManobra->first+
                             " faltou desligamento após "+
                             MnbFind->DtHoraMan.FormatString("dd/mm/yyyy hh:nn:ss"), evsDontCare);
            }
            else
            {
                itManobra->second->ParNoMapa = itFind->first;
            }
        }

    }

Answer 1

The std::map class template does not allow duplicated keys. So, you can use the find() method to find the required key starting from the beginning of a map.

It seems you mean something like the following:

#include <iostream>
#include <map>
#include <iterator>

int main()
{
    std::map<int, char> m =
    {
        { 65, 'A' }, { 66, 'B'}, { 67, 'C' }, { 68, 'D' }, { 69, 'E' }, { 70, 'F' }
    };

    int key = 68;

    auto it = m.find( key );

    if (it != std::end( m ))
    {
        for (auto first = std::reverse_iterator( std::next( it ) ), last = std::rend( m );
            first != last; ++first)
        {
            std::cout << "( " << first->first << ", '" << first->second << "' ) ";
        }
        std::cout << '\n';
    }
}

The program output is:

( 68, 'D' ) ( 67, 'C' ) ( 66, 'B' ) ( 65, 'A' )

Or, the for loop can look like this:

for (auto first = std::reverse_iterator( std::next( it ) ), last = std::rend( m );
    first != last; ++first)
{
    const auto &[key, value] = *first;
    std::cout << "( " << key << ", '" << value << "' ) ";
}

If you are using the std::multimap class template then, instead of the find() method, you can use the upper_bound() method.

If you want to find a key based on a value, you should use the standard std::find_if() algorithm. With that algorithm, you can use reverse iterators.