CODEWITHSUNDEEP
c++dictionaryunions
Anne Quinn
Anne Quinn

Reputation: 13000

How to compare two unions for ordering

I have a class that's to act as a map key, which contains two members

struct Key{
    unsigned int type;
    union{
        Enumerator thing1;
        int32 thing2;
        struct{int16 a; bool b;} thing3;
        ... etc...
    }data;

    bool operator<(const Key & rh) const{
        if(type == rh.type){
            ???
        }else{
            return type < rh.type;
        }
    }
}

The second member data is a union, and I'm unsure how to compare it against another of it's type in a way that's agnostic of what union member was last assigned (a switch in the lessthan operator would be too costly)

It's not important the ordering, all that matters is that different values are seen as different by the map. Is there a way to do a fast bit compare on two unions?

Upvotes: 1

Views: 1405

Answers (2)

sameerkn
sameerkn

Reputation: 2259

This solution requires modification to union as well as the places condition on values which can be taken by the members of union. Please Note: This might not be the required answer but a possible way to compare that's agnostic of what union member was last assigned.

Make every member of union of same size. Since anyways, max size of member will be considered so it doesn't matter having same size. Now decide the domain of values for the members. Let's say:

  • domain of thing1 is {A,B,C....}
  • domain of thing2 is {P,Q,R....}
  • domain of thing3 is {X,Y,Z....}

Now if you can ensure A,P,X are of logically equal weight/priority/value w.r.t comparison then 2 instances of union this->data and rh.data can be compared using normal relational operators in same way as you have compared this->type and rh.type Similarly, B,Q,Y should be of logically equal weight/priority/value w.r.t comparison. Same applies to other corresponding values of things1, thing2 and thing3.

Upvotes: 1

Steve Jessop
Steve Jessop

Reputation: 279285

No, there can't be a single type-agnostic bytewise comparison. thing2 and thing3 have different numbers of bytes participating in their values (that is, different amounts of padding), so you can't use std::memcmp or any other comparison of the raw memory.

If the types run consecutively from 0 (or anyway, are reasonably small numbers), then you could perhaps look up a size to compare from an array indexed by type, provided that all the padding in all the union members is at the end, such that all bytes participating in the value are at the start. thing3 already might fail this test, if bool is bigger than int16, and we don't know what's in Enumerator and ... etc ...

In theory you could avoid a switch using an array of function pointers, indexed by type. But there's no particular reason to expect that to be any faster than a switch once the optimizer has done its work. Generally speaking, function pointers are death to inlining and so they cripple the optimizer and the CPU's own speculative instruction fetching/execution.

By the way, if you don't care about the order then std::unordered_map will generally perform better than std::map, but you'll still have this issue of needing to write a hash function that only hashes the bytes that participate in the value.

Upvotes: 1

Related Questions