Extended Hashmaps

[FatalSleep]

Hello everyone!

How difficult would it be to program a hash-map system where each "key" can have multiple values under indexes?

For example: "Word" -> 45(index 0) , 67(index 1) , 12(index 2).
What could I start with to program this or where could I find a pre-made system that does this?

Thanks!
-FatalSleep

[JLBorges]

#include <iostream>
#include <string>
#include <vector>
#include <unordered_map>

int main()
{
    {
        std::unordered_map< std::string, std::vector<int> > hash_map ;

        std::pair< std::string, int > kv_pairs[] =
        {
            { "one", 1 }, { "two", 2 }, { "three", 3 }, { "one", 4 }, { "two", 5 },
            { "one", 6 }, { "three", 7 }, { "one", 8 }, { "two", 9 }, { "one", 10 }
        };

        for( const auto& p : kv_pairs ) hash_map[p.first].push_back(p.second) ;

        for( const auto& kv : hash_map )
        {
            std::cout << "key: '" << kv.first << "'  values: " ;
            for( int v : kv.second ) std::cout << v << ' ' ;
            std::cout << '\n' ;
        }
    }
}

http://coliru.stacked-crooked.com/a/f8bd9dd38678fa2d

[FatalSleep]

Oh wow! Thank you!

[FatalSleep]

Hmmm... I did a simple copy / paste just to try it out, but it doesn't work. The adding for the values on lines 13 and 14 fail.

[JLBorges]

C++98:

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

int main()
{
    {
        std::map< std::string, std::vector<int> > map ;

        const std::pair< std::string, int > kv_pairs[] =
        {
            std::make_pair( "one", 1 ), std::make_pair( "two", 2 ),
            std::make_pair( "three", 3 ), std::make_pair( "one", 4 ),
            std::make_pair( "two", 5 ), std::make_pair( "one", 6 ),
            std::make_pair( "three", 7 ), std::make_pair( "one", 8 ),
            std::make_pair( "two", 9 ), std::make_pair( "one", 10 )
        };

        const int N = sizeof(kv_pairs) / sizeof( kv_pairs[0] ) ;

        for( int i = 0 ; i < N ; ++i )
        {
            const std::string& key = kv_pairs[i].first ;
            const int value = kv_pairs[i].second ;
            map[key].push_back(value) ;
        }

        std::map< std::string, std::vector<int> >::iterator iter = map.begin() ;
        for(  ; iter != map.end() ; ++iter )
        {
            const std::string& key = iter->first ;
            std::cout << "key: '" << key << "'  values: " ;

            const std::vector<int>& values = iter->second ;
            for( std::size_t i = 0 ; i < values.size() ; ++i )
                std::cout << values[i] << ' ' ;
            std::cout << '\n' ;
        }
    }
}

http://coliru.stacked-crooked.com/a/0b792c0305ce837f

[Catfish666]

How difficult would it be to program a hash-map system where each "key" can have multiple values under indexes?

For example: "Word" -> 45(index 0) , 67(index 1) , 12(index 2).
What could I start with to program this or where could I find a pre-made system that does this?

There is std::multimap and std::unordered_multimap.
@ JLBorges: how come you didn't use these instead? Ah yes, the index issue.

http://www.cplusplus.com/reference/map/multimap/
http://www.cplusplus.com/reference/unordered_map/unordered_multimap/

Hmmm... I did a simple copy / paste just to try it out, but it doesn't work. The adding for the values on lines 13 and 14 fail.

I suggest you download Visual Studio 2013 Express, or enable C++11 support in GCC.

[JLBorges]

> There is std::multimap and std::unordered_multimap.
> @ JLBorges: how come you didn't use these instead?

Here, because of the requirement:

where each "key" can have multiple values under indexes

But also, if most keys are likely to have more than one associated value, I always prefer std::map and std::unordered_map with a std::vector as the mapped type over std::multimap and std::unordered_multimap.

The primary reason is clarity and simplicity - code with std::multimap and std::unordered_multimap tends to be less readable.

In many cases, there may also be a secondary reason of efficiency (if the average number of values mapped to a key is high) - simply don't want to carry redundant multiple copies of the key.

[FatalSleep]

Ohh... I had VCS2013 but I haven't been using it because it's ugly as hell. Anyways though, switching to it helped solve my problem. Thanks guys! :D

I'll probably post again if I need any more help though. ;)

[FatalSleep]

I've been searching all around, but might it be possible to use both strings or real values for the keys / values in the unordered maps?

[Catfish666]

I've been searching all around, but might it be possible to use both strings or real values for the keys / values in the unordered maps?

You can't alternatively use different types for keys. You can, however, use more types at once, combined to form a single key.

So you could put your string and real value in an std::pair.
http://www.cplusplus.com/reference/utility/pair/

Then you could use the pair as key in ordinary maps (because std::pair already overloads operator<).

However for unordered maps (aka hash maps) you need to provide your own hashing function (because hash maps will not merely order the keys via operator< they will hash the keys).

http://www.cplusplus.com/reference/functional/hash/

If you use more than two values, you should look into std::tuple, and it only gets harder from there.
http://www.cplusplus.com/reference/tuple/

I am waiting to see what JLBorges has to add.

[JLBorges]

> Use real values for the keys / values

There is no issue using real numbers as the mapped type in std::map<> / std::unordered_map<>

But using them as the key type? There are nasty issues to deal with if these 'real values' are floating point values (float, double or long double).

To start with, we will have to ensure that NaN never gets a direct look in - comparisons with NaN (even comparisons with itself) yield an unordered result.

The problem that floating point is an inexact representation of a real number remains, and can become insurmountable one if the range of values is large.

For instance, if we use a tolerance of delta, with a, b = a+delta, c = b+delta,
a may compare equal to b, b may compare equal to c, but a may compare less than c.

In short, comparing two floating-point numbers is harder than it looks if your goal is to meet the C++ order-relation requirements. - Andrew Koenig in Dr. Dobb's
http://www.drdobbs.com/cpp/its-hard-to-compare-floating-point-numbe/240149806

As far as possible, avoid using floating point values as keys. A user defined fixed-point or a rational number type is one viable possibility; converting the floating point values to a string representation (with a fixed number of digits after the decimal) is another.

[FatalSleep]

Hmm... this can get complicated. I never planned on using floating points, I never needed anything that specific for values. For what I am going for, strings and integers shall do.

[JLBorges]

> For what I am going for, strings and integers shall do.

To be unambiguous: do you want the same hash table to contain both strings and integers as keys?

That is: a key could be either a string or an integer?
Or is it: a key is a pair consisting of of a string and an integer?

[FatalSleep]

Ah sorry. I actually tried, but failed. However, I'd like to know how to have both keys AND values that can be either a string or integer. E.g. like so:

Example:
key: "hey" --> value: 55
key: 55 --> value: "hey"
key: 55 --> value: 55
key: "hey" --> value: "hey"

However, I've been starting to think hat hashmaps are beyond my programming expertise in C++.

[JLBorges]

> I'd like to know how to have both keys AND values that can be either a string or integer

We would need to create a user defined type, an object of which can be either a string or an int. And we would need to keep track of what it is - string or int - at every point in time, and manage the operations on the objects correctly based on that knowledge. (Essentially, implement type-safe dynamic typing in a statically typed language.) Such a type is called a 'union-like class' (aka discriminated union or tagged union).
http://www.stroustrup.com/C++11FAQ.html#unions

Finally, in order to be able to have these as keys in a hash table, we would have to provide a hash function and an equality comparator.

In practice, we would adapt a discriminated union type from a library - for instance boost::variant<>. That would save us the trouble of writing a lot of boiler-plate code. However, if we want to understand what is going on behind the scenes, we need to write a home-grown version. Here is one such (written off the cuff, untested and so on). It should give you an idea of how such a type could be implemented.

#include <iostream>
#include <string>
#include <stdexcept>
#include <functional>
#include <memory>
#include <unordered_map>
#include <vector>

struct variant
{
    using string = std::string ;

    bool is_string() const noexcept { return type == STRING ; }
    bool is_int() const noexcept { return type == INT ; }

    std::string to_string() const
    {
        if( !is_string() ) throw std::logic_error( "not string" ) ;
        return str ;
    }

    int to_int() const
    {
        if( !is_int() ) throw std::logic_error( "not int" ) ;
        return i ;
    }

    variant( const std::string& s ) : type(STRING), str(s) {}
    variant( std::string&& s ) noexcept : type(STRING), str( std::move(s) ) {}
    variant( int v = 0 ) noexcept : type(INT), i(v) {}
    variant( const char* cstr ) : type(STRING), str(cstr) {}

    ~variant()  noexcept { if( type == STRING ) str.~string() ; }

    variant( const variant& that ) : type(that.type)
    {
        if( is_string() ) new ( std::addressof(str) ) std::string(that.str) ;
        else i = that.i ;
    }

    variant( variant&& that ) noexcept : type(that.type)
    {
        if( is_string() ) new ( std::addressof(str) ) std::string( std::move(that.str) ) ;
        else i = that.i ;
    }

    variant& operator= ( const variant& that )
    {
        if( this != std::addressof(that) )
        {
            if( is_string() )
            {
                if( that.is_string() ) str = that.str ;
                else { str.~string() ; type = INT ; i = that.i ; }
            }
            else
            {
                if( that.is_int() ) i = that.i ;
                else
                {
                    new ( std::addressof(str) ) std::string(that.str) ;
                    type = STRING ;
                }
            }
        }
        return *this ;
    }

    variant& operator= ( variant&& that ) noexcept
    {
        if( is_string() )
        {
            if( that.is_string() ) str = std::move(that.str) ;
            else { str.~string() ; type = INT ; i = that.i ; }
        }
        else
        {
            if( that.is_int() ) i = that.i ;
            else
            {
                new (&str) std::string( std::move(that.str) ) ;
                type = STRING ;
            }
        }

        return *this ;
    }

    //////////////// TODO /////////////////////////////

    variant& operator= ( const std::string& ) ;
    variant& operator= ( std::string&& ) noexcept ;
    variant& operator= ( int )  noexcept ;
    variant& operator= ( const char* ) ;

    ///////////////////////////////////////////////////

    struct hash
    {
        std::size_t operator() ( const variant& var ) const noexcept
        {
            static const std::hash<std::string> str_hash ;
            static const std::hash<int> int_hash ;
            return var.is_string() ? str_hash(var.str) : int_hash(var.i) ;
        }
    };

    struct equal_to
    {
        bool operator() ( const variant& a, const variant& b ) const noexcept
        {
            if( a.is_string() ) return b.is_string() && a.str == b.str ;
            else return b.is_int() && a.i == b.i ;
        }
    };

    private:

        enum type_t { STRING, INT };
        type_t type ;

        union
        {
            std::string str ;
            int i ;
        };

    friend inline std::ostream& operator<< ( std::ostream& stm, const variant& var )
    { return var.is_string() ? ( stm << '"' << var.str << '"' ) : ( stm << var.i ) ; }
};

int main()
{
    std::unordered_map< variant, std::vector<variant>,
                        variant::hash, variant::equal_to > hash_map ;

    std::pair< variant, variant > key_value_pairs[] =
    {
        { "abcd", "zero" }, { 123, 1 }, { "abcd", 2 }, { 123, 3 }, { "abcd", 4 },
        { 4567, 5 }, { "xyz", 6 }, { 4567, "seven" }, { "xyz", "eight" },
        { "abcd", "nine" }, { "xyz", 10 }, { 4567, 11 }, { 123, "twelve" },
        { "abcd", "thirteen" }, { "xyz", "fourteen" }, { 123, 15 },
        { 123, "sixteen" }, { "abcd", 17 }, { 123, 18 }, { 4567, 19 }, { 123, 20 }
    };

    for( const auto& p : key_value_pairs ) hash_map[p.first].push_back(p.second) ;

    for( const auto& key_value_pair : hash_map )
    {
        std::cout << "key: " << key_value_pair.first << "\n\tvalues: " ;
        for( const variant& v : key_value_pair.second ) std::cout << v << "  " ;
        std::cout << "\n\n" ;
    }
}

http://coliru.stacked-crooked.com/a/28e699d81cc04b5b