CODEWITHSUNDEEP
c++c++11stlcontainersstdmap
Xaser
Xaser

Reputation: 2146

std::map-like type without compare / hash on key

I just ran into a minor problem and wondered which of the many solution is the best / proper one.

I have a std::map that has a custom class for key and value each (so swapping them won't fix anything).

struct FooStruct
{
    bool testOne;
    bool testTwo;
};

struct BarStruct
{
    // some data
};

const std::map<FooStruct, BarStruct>
{
    { { true, false }, BarStruct(someValues) },
    { { false, true }, BarStruct(someOtherValues) }
};

so now, FooStruct cannot be "compared" in any sensible way neither can BarStruct for that matter. Using unordered_map isn't a help either, because that requires a hashing function, which I of course implement many ways but I doubt that this is the easiest way to get a really unsorted map.

I don't care for performance either, as there are only 4 elements in the map. May be a few thousand another time though.

To address the comments: This is an abstract example. The problem is that a collection of boolean test results in a struct can easily be compared if there are a few tests but as the number of permutation grows very fast with n, I'm looking for a scalable solution.

Maybe there is an alternative to std::map types overall, e.g. std::vector of std::pair but that has other drawbacks as well.

Upvotes: 1

Views: 1045

Answers (3)

Nicolas
Nicolas

Reputation: 393

Another "scalable" solution :

using FooStruct = std::vector<bool>;
std::map<FooStruct, BarStruct> foobarite
{
    { { true, false }, {} },
    { { false, true }, {} },
};

And, if you want to keep the named attribute in FooStruct, yet another one :

#include <unordered_map>
#include <functional>
#include <algorithm>

template <class T>
inline void hash_combine(std::size_t & seed, const T & v)
{
  std::hash<T> hasher;
  seed ^= hasher(v) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
}

template <typename Struct>
struct hash {
    inline std::size_t operator()(const Struct& obj ) const
    {
        const unsigned char* p = reinterpret_cast<const unsigned char*>( &obj );
        std::size_t seed = std::hash<unsigned char>{}(p[0]);
        for (unsigned int i = 1; i < sizeof(obj); ++i) {
            hash_combine(seed, p[i]);
        }
        return seed;
    }
};

template <typename Struct>
struct equal {
    bool operator()(const Struct& a, const Struct& b) const
    {
        const unsigned char* pa = reinterpret_cast<const unsigned char*>( &a );
        const unsigned char* pb = reinterpret_cast<const unsigned char*>( &b );
        return std::equal(pa, pa+sizeof(Struct), pb);
    }
};

struct FooStruct {
    bool testOne;
    bool testTwo;
};

std::unordered_map<FooStruct, BarStruct, hash<FooStruct>, equal<FooStruct>> foobarite
{
    { { true, false }, {} },
    { { false, true }, {} }
};

Upvotes: 0

Danvil
Danvil

Reputation: 23001

If your struct FooStruct has many test results, you have different structs like this, and the number of tests varies, than you do not have a scaleable solution.

Write a scaleable version using bitset (ref). Then you can can for example compare using bitset::to_ulong (ref) (given you have less than 64 test results).

struct FooStruct
{
    std::bitset<5> result; // can hold 5 results
    friend bool operator<(const FooStruct& a, const FooStruct& b) {
        return a.result.to_ulong() < b.result.to_ulong();
    }
};

Otherwise you have to aggregate manually. For example:

struct FooStruct
{
    bool testOne;
    bool testTwo;
    bool testThree;
    unsigned long key() const {
        return testOne + (testTwo << 1) + (testThree << 2);
    }
    friend bool operator<(const FooStruct& a, const FooStruct& b) {
        return a.key() < b.key();
    }
};

Upvotes: 2

juanchopanza
juanchopanza

Reputation: 227418

It doesn't matter if the comparison is "sensible", all that matters is that it implement a strict weak ordering. This is easy enough to implement.

#include <tuple>

bool comp(const FooStruct& lhs, const FooStruct& rhs)
{
  return std::tie(lhs.testOne, lhs.testTwo) < 
         std::tie(rhs.testOne, rhs.testTwo);
}

As for unordered_map, it is a hash table, so you need to provide a hash function and an equality comparison. There's no way getting around that.

Upvotes: 2

Related Questions