Construct a map<int, list<int>> out of an array

[Claudius7]

Hi, here is the problem:

suppose I have an array, say A[]=(1,4,7,3,3,5). Now I want to construct a map m, which does the following job:

1) sort the array (ok, this is easy) to (1,3,3,4,5,7)
2) the key values of the map should be the sorted values, taken only once if repeated, i.e. in this case, the values 1,3,4,5,7.
3) to each key value, I want the map m associates the list (or vector, whatever) composed by the indices from where the values come from.

In other words, I want to construct the following map:

 m[1] = {0},
 m[3] = {3,4},
 m[4] = {1},
 m[5] = {5},
 m[7] = {2}.

I have absolutely no idea of what should be done. Thank you for your help!

[JLBorges]

#include <iostream>
#include <map>
#include <vector>
#include <string>

template < typename T, std::size_t N >
std::map< T, std::vector<std::size_t> > map_indices( const T(&array)[N] )
{
    std::map< T, std::vector<std::size_t> > result ;
    for( std::size_t i = 0 ; i < N ; ++i ) result[ array[i] ].push_back(i) ;
    return result ;
}

template < typename T > void print( const std::map< T, std::vector<std::size_t> >& map )
{
    for( const auto& pair : map )
    {
        std::cout << pair.first << "  => { " ;
        for( std::size_t v : pair.second ) std::cout << v << ' ' ;
        std::cout << "}\n" ;
    }
}

int main()
{
    const int a[] { 1, 4, 7, 3, 3, 5, 3, 1, 7, 8, 3, 1, 7 } ;
    const auto map = map_indices(a) ;
    print(map) ;

    std::cout << "\n-----------------------------\n" ;
    const std::string b[] { "how", "now", "brown", "cow", "now", "brown", "how", "brown", "how" } ;
    print( map_indices(b) ) ;
}

http://coliru.stacked-crooked.com/a/5245c2e6c5871a2d

[Claudius7]

Hi JLBorges, thank you a lot for your excellent answer. I have only one possibly stupid question: what is the type "auto" that you use several times? I should be able to change it to something else, because my compiler does not support it. How can I do to change it? Thanks for your suggestion

[JLBorges]

auto : deduce the type from an initializer http://www.stroustrup.com/C++11FAQ.html#auto

range-based loop : http://www.stroustrup.com/C++11FAQ.html#for

Both came with C++11.

Legacy C++:

#include <iostream>
#include <map>
#include <vector>
#include <string>

template < typename T, std::size_t N >
std::map< T, std::vector<std::size_t> > map_indices( const T(&array)[N] )
{
    std::map< T, std::vector<std::size_t> > result ;
    for( std::size_t i = 0 ; i < N ; ++i ) result[ array[i] ].push_back(i) ;
    return result ;
}

template < typename T > void print( const std::map< T, std::vector<std::size_t> >& map )
{
    for( typename std::map< T, std::vector<std::size_t> >::const_iterator iter = map.begin() ;
         iter != map.end() ; ++iter )
    {
        std::cout << iter->first << "  => { " ;
        for( std::size_t i = 0 ; i < iter->second.size() ; ++i )
            std::cout << iter->second[i] << ' ' ;
        std::cout << "}\n" ;
    }
}

int main()
{
    const int a[] = { 1, 4, 7, 3, 3, 5, 3, 1, 7, 8, 3, 1, 7 } ;
    const std::map< int, std::vector<std::size_t> > map = map_indices(a) ;
    print(map) ;

    std::cout << "\n-----------------------------\n" ;
    const std::string b[] = { "how", "now", "brown", "cow", "now", "brown", "how", "brown", "how" } ;
    print( map_indices(b) ) ;
}

http://coliru.stacked-crooked.com/a/9c6c49c74421f35c

[Claudius7]

Thank you very much for your clear and thorough explanation, Jorge Luis!
I have not implemented C++ 11 myself, so in fact I am still a bit uncomfortable with that.

I like your solution because it uses very simple concepts, instead of more fancy multimaps, etc.

Thanks again!

PS Just one more question: the code

map_indices( const T(&array)[N] )

means "an array of objects of type T, of length N"? I have not yet found this syntax in my study.

[JLBorges]

const T(&array)[N]
The type const T(&)[N] is 'reference to array of objects of type const T, of length N'