CODEWITHSUNDEEP
c++dictionarycomparatorpredicatestdmap
AMM
AMM

Reputation: 17930

efficient comparator for an std::map with a struct key

I have a struct of following type which I am planning use as a key in a map. Hence I write a comparator like below. I would like to know if there is a more elegant yet efficient way of doing this.
May be using std::pair or something.

struct T 
{
  int a, b, c, d;

  bool operator< (const T& r) {
    if (a < r.a)
       return true
    else if (a == r.a)
       if (b < r.b)
          return true;
       else if (b == r.b)
            if (c < r.c) 
                return true;
            else if (c == r.c)
                if (d < r.d)
                   return true;
    return false;
  }
}

Upvotes: 3

Views: 1047

Answers (3)

Tony Delroy
Tony Delroy

Reputation: 106244

You can use...

bool operator<(const T& r)
{
    return a < r.a ||
           a == r.a && (b < r.b || 
                        b == r.b && (c < r.c || 
                                     c == r.c && d < r.d));
}

Or...

    return a != r.a ? a < r.a :
           b != r.b ? b < r.b :
           c != r.c ? c < r.c :
                      d < r.d;

You've said you're not using C++11, and Barry has a good illustration of a tuple approach, but for future reference and other interested parties, with a little reusable support code...

bool less_by_pairs()
{
    return false;
}

template <typename T, typename U, typename ...Args>
bool less_by_pairs(const T& v1, const U& v2, Args... args)
{
    return v1 != v2 ? v1 < v2 : less_by_pairs(args...);
}

...you can implement such operators more easily...

bool operator<(const T& r)
{
    return less_by_pairs(a, r.a, b, r.b, c, r.c, d, r.d);
}

You could do something similar providing a list of members to compare, but the notation for that's actually a little verbose anyway.

Upvotes: 0

gibertoni
gibertoni

Reputation: 1378

You could use another field to store a key. This key value could be generated through a formula, that takes as input (a,b,c,d)

Like so:

void hash()
{
    key = (a ^ b ^ c ^ d);
}

As result, you would need to only compare this key to know if the contents are the same.

Upvotes: -1

Barry
Barry

Reputation: 304132

Can you use C++11? If so:

struct T {
    int a, b, c, d;

    bool operator<(const T& rhs) const {
        return tied() < rhs.tied();
    }

private:
    std::tuple<int, int, int, int> tied() const {
        return std::make_tuple(a, b, c, d);
    }
};

Alternatively, I would prefer returning at each possible opportunity to avoid the error-prone awkward nesting approach:

bool operator<(const T& rhs) const {
    if (a != rhs.a) return a < rhs.a;
    if (b != rhs.b) return b < rhs.b;
    if (c != rhs.c) return c < rhs.c;
    return d < rhs.d;
}

Upvotes: 2

Related Questions