CODEWITHSUNDEEP
c++stdmapstd-pair
Sadık
Sadık

Reputation: 4419

map comparator for pair of objects in c++

I want to use a map to count pairs of objects based on member input vectors. If there is a better data structure for this purpose, please tell me. My program returns a list of int vectors. Each int vector is the output of a comparison between two int vectors ( a pair of int vectors). It is, however, possible, that the output of the comparison differs, though the two int vectors are the same (maybe in different order). I want to store how many different outputs (int vectors) each pair of int vectors has produced.

Assuming that I can access the int vector of my object with .inp()

Two pairs (a1,b1) and (a2,b2) should be considered equal, when (a1.inp() == a2.inp() && b2.inp() == b1.inp()) or (a1.inp() == b2.inp() and b1.inp() == a2.inp()).

This answer says:

The keys in a map a and b are equivalent by definition when neither a < b nor b < a is true.

class SomeClass
{
    vector <int> m_inputs;
public:
    //constructor, setter...
    vector<int> inp() {return m_inputs};
}

typedef pair < SomeClass, SomeClass > InputsPair;
typedef map < InputsPair, size_t, MyPairComparator > InputsPairCounter;

So the question is, how can I define equivalency of two pairs with a map comparator. I tried to concatenate the two vectors of a pair, but that leads to (010,1) == (01,01), which is not what I want.

struct MyPairComparator
{
    bool operator() (const InputsPair & pair1, const InputsPair pair2) const
    {
        vector<int> itrc1 = pair1.first->inp();
        vector<int> itrc2 = pair1.second->inp();
        vector<int> itrc3 = pair2.first->inp();
        vector<int> itrc4 = pair2.second->inp();
        // ?
        return itrc1 < itrc3;
    }
};

Upvotes: 0

Views: 1468

Answers (2)

Slava
Slava

Reputation: 44268

I want to use a map to count pairs of input vectors. If there is a better data structure for this purpose, please tell me.

Using std::unordered_map can be considered instead due to 2 reasons:

  • if hash implemented properly it could be faster than std::map

  • you only need to implement hash and operator== instead of operator<, and operator== is trivial in this case

Details on how implement hash for std::vector can be found here. In your case possible solution could be to join both vectors into one, sort it and then use that method to calculate the hash. This is straightforward solution, but can produce to many hash collisions and lead to worse performance. To suggest better alternative would require knowledge of the data used.

Upvotes: 1

Jarod42
Jarod42

Reputation: 217940

As I understand, you want:

struct MyPairComparator
{
    bool operator() (const InputsPair& lhs, const InputsPair pair2) const
    {
        return std::minmax(std::get<0>(lhs), std::get<1>(lhs))
            < std::minmax(std::get<0>(rhs), std::get<1>(rhs));
    }
};

we order the pair {a, b} so that a < b, then we use regular comparison.

Upvotes: 0

Related Questions