Is_permutation() on sequence containers in O(n) complexity - follow-up This question is a continuation of my previous question:

Check is_permutation on a pair of same sized arrays.

I improved the implementation to generalize for all sequence containers. Please let me know how I can improve this implementation again.

#include&lt;iostream&gt;
#include&lt;algorithm&gt;
#include&lt;unordered_map&gt;
#include&lt;array&gt;
#include&lt;list&gt;

template &lt; typename T1 &gt;
std::unordered_map&lt; int, int &gt; count_frequency( T1 first, T1 last )
{
    std::unordered_map&lt; int, int &gt; temp_unordered_map;
    auto temp_unordered_map_end = std::end( temp_unordered_map );
    while( first != last )
    {
        auto it_temp_unordered_map = temp_unordered_map.find( *first );
        if( it_temp_unordered_map == temp_unordered_map_end )
        {
            temp_unordered_map.emplace( *first, 1 );                       
        }
        else
        {
            ++( it_temp_unordered_map-&gt;second );
        }
        ++first;
    }
    return temp_unordered_map;
}

template &lt; typename T1, typename T2 &gt;
bool is_permutation( const T1 first1, const T1 last1, const T2 first2, const T2 last2 )
{   
    if( std::distance( first1, last1 ) != std::distance( first2, last2 ) )
    {
        return false;  
    }
    std::unordered_map&lt; int, int &gt; first_map = count_frequency( first1, last1 );        
    std::unordered_map&lt; int, int &gt; second_map = count_frequency( first2, last2 );

    std::pair&lt;std::unordered_map&lt; int, int &gt;::iterator,std::unordered_map&lt; int, int &gt;::iterator &gt; myPair=
        std::mismatch( std::begin( first_map ), std::end( first_map ), std::begin( second_map ), 
        []( std::pair&lt; const int, int &gt;&amp; seed1, std::pair&lt; const int, int &gt; &amp; seed2) 
        { return seed1.second == seed2.second; }
        );

    return  myPair.first == first_map.end() &amp;&amp; myPair.second == second_map.end(); 
}

int main()
{     
    const std::array&lt; int, 5&gt; array1 { { 1, 3, 2, 4, 5 } };
    const std::array&lt;int,4&gt; array2 { { 1, 2, 4, 3 } };

    if( ::is_permutation( std::begin( array1 ), std::end( array1 ), std::begin( array2 ), std::end( array2 ) ) )
    {
        std::cout&lt;&lt; " Elements are permutation of each other\n"; 
    }
    else
    {
        std::cout&lt;&lt; " Elements are not permutation of each other\n";
    }

    const std::vector&lt; int &gt; vec1 { { 1, 3, 2, 4 } };
    const std::vector&lt; int &gt; vec2 { { 1, 2, 4, 3 } };

    if( ::is_permutation( std::begin( vec1 ), std::end( vec1 ), std::begin( vec2 ), std::end( vec2 ) ) )
    {
        std::cout&lt;&lt; " Elements are permutation of each other\n"; 
    }
    else
    {
        std::cout&lt;&lt; " Elements are not permutation of each other\n";
    }

    const std::list&lt; int &gt; list1 { { 1, 3, 2, 4 } };
    const std::list&lt; int &gt; list2 { { 1, 2, 4, 3 } };

    if( ::is_permutation( std::begin( list1 ), std::end( list1 ), std::begin( list2 ), std::end( list2 ) ) )
    {
        std::cout&lt;&lt; " Elements are permutation of each other\n"; 
    }
    else
    {
        std::cout&lt;&lt; " Elements are not permutation of each other\n";
    }
    return 0;
}
I would initially agree that the complexity of your solution is O(n), though, there are extreme cases where the performance of your count_frequency could be greater - unordered_map.emplace() is 'average case constant time, worst case linear', I don't believe a worst-case situation would happen for you.

Note that you have a very complicated equality-check comparing your two frequency-maps.... you have:


if( std::distance( first1, last1 ) != std::distance( first2, last2 ) )
{
    return false;  
}
std::unordered_map&lt; int, int &gt; first_map = count_frequency( first1, last1 );        
std::unordered_map&lt; int, int &gt; second_map = count_frequency( first2, last2 );

std::pair&lt;std::unordered_map&lt; int, int &gt;::iterator,std::unordered_map&lt; int, int &gt;::iterator &gt; myPair=
    std::mismatch( std::begin( first_map ), std::end( first_map ), std::begin( second_map ), 
    []( std::pair&lt; const int, int &gt;&amp; seed1, std::pair&lt; const int, int &gt; &amp; seed2) 
    { return seed1.second == seed2.second; }
    );

return  myPair.first == first_map.end() &amp;&amp; myPair.second == second_map.end();



as far as I can tell, the size-check is redundant, and the rest can be simply:

template &lt; typename T1, typename T2 &gt;
bool is_permutation( const T1 first1, const T1 last1, const T2 first2, const T2 last2 )
{   
    return count_frequency( first1, last1 ) == count_frequency( first2, last2 );
}


I put your code in this ideone, and the replacement code in this ideone here.