4
\$\begingroup\$

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<iostream>
#include<algorithm>
#include<unordered_map>
#include<array>
#include<list>

template < typename T1 >
std::unordered_map< int, int > count_frequency( T1 first, T1 last )
{
    std::unordered_map< int, int > 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->second );
        }
        ++first;
    }
    return temp_unordered_map;
}

template < typename T1, typename T2 >
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< int, int > first_map = count_frequency( first1, last1 );        
    std::unordered_map< int, int > second_map = count_frequency( first2, last2 );

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

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

int main()
{     
    const std::array< int, 5> array1 { { 1, 3, 2, 4, 5 } };
    const std::array<int,4> array2 { { 1, 2, 4, 3 } };

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

    const std::vector< int > vec1 { { 1, 3, 2, 4 } };
    const std::vector< int > vec2 { { 1, 2, 4, 3 } };

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

    const std::list< int > list1 { { 1, 3, 2, 4 } };
    const std::list< int > list2 { { 1, 2, 4, 3 } };

    if( ::is_permutation( std::begin( list1 ), std::end( list1 ), std::begin( list2 ), std::end( list2 ) ) )
    {
        std::cout<< " Elements are permutation of each other\n"; 
    }
    else
    {
        std::cout<< " Elements are not permutation of each other\n";
    }
    return 0;
}
\$\endgroup\$

2 Answers 2

3
\$\begingroup\$

I like to add my grain of salt, so here it is:

  • While const is interesting for pointer or references parameter, it tends to be less useful otherwise. I would use it only when it changes something for the user. Typically, when you pass parameters by copy (which is what is done for iterators), it is useless to const-qualify them, especially since you actually pass them by copy again to another function that takes non-const iterators and modifies them. I wouldn't even be surprised if it hindered performance and/or compiler optimizations at some point.

  • While a double pair of braces is necessary to initialize an std::array without getting a warning with Clang, I really consider it to be syntactic noise and I avoid it as much as possible. It isn't needed for std::list and std::vector, so I would use a simple pair of braces which in my opinion better conveys what you are doing (well, it's eventually subjective).

  • I agree with @rolfl about the redundant range-size equality check in is_permutation. Moreover, std::distance is \$O(n)\$ for most iterator types, so you are adding an actual runtime cost here.

    However, std::distance is \$O(1)\$ for random-access iterators, range size checking may indeed be faster for those. Therefore, you could make two versions of is_permutation: one that takes random-access iterators and one that only takes regular input iterators. Add a layer of tag dispatching and let the compiler pick the most well-suited function for you:

    template < typename T1, typename T2 >
    bool is_permutation_impl( const T1 first1, const T1 last1, const T2 first2, const T2 last2, std::input_iterator_tag )
    {
        return count_frequency( first1, last1 ) == count_frequency( first2, last2 );
    }
    
    template < typename T1, typename T2 >
    bool is_permutation_impl( const T1 first1, const T1 last1, const T2 first2, const T2 last2, std::random_access_iterator_tag )
    {
        if( std::distance( first1, last1 ) != std::distance( first2, last2 ) )
        {
            return false;  
        }
        return count_frequency( first1, last1 ) == count_frequency( first2, last2 );
    }
    
    template < typename T1, typename T2 >
    bool is_permutation( const T1 first1, const T1 last1, const T2 first2, const T2 last2 )
    {
        return is_permutation_impl(
            first1, last1,
            first2, last2,
            std::iterator_traits<T1>::iterator_category{}
        );
    }
    

    Note that my tag dispatching is not fully correct because it only checks whether the first range is a random-access range, while it should check whether both ranges are. You can implement the correct behaviour with a little bit more template stuff, but it will be left as an exercise to the reader (mostly be cause I am not motivated enough to do it myself right now).

\$\endgroup\$
3
\$\begingroup\$

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< int, int > first_map = count_frequency( first1, last1 );        
std::unordered_map< int, int > second_map = count_frequency( first2, last2 );

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

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

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

template < typename T1, typename T2 >
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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.