STL Map Use | Steven Engelhardt

What’s wrong with the following code?

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32


template<typename T1, typename T2>
struct my_pair
{
    typedef T1 first_type;
    typedef T2 second_type;

    my_pair() : first(T1()), second(T2()) {}
    my_pair(const T1& v1, const T2& v2) : first(v1), second(v2) {}

    T1 first;
    T2 second;
};

template<typename T1, typename T2>
inline bool operator<
    (
    const my_pair<T1, T2>& x,
    const my_pair<T1, T2>& y
    )
{
    return (x.first < y.first || x.second < y.second);
}

void f()
{
    typedef my_pair<..., ...> key_type;
    typedef ... value_type;
    typedef std::map<key_type, value_type> map_type;

    map_type map;
    // Use map
}

Answer: my_pair cannot be used as a key for a STL map because the operator< violates the rule of strict weak ordering. More specifically, the operator is not antisymmetric. Consider the following:

1
2
3


typedef my_pair<int, int> P;
P p1(3, 5);
P p2(2, 6);

Both p1 < p2 and p2 < p1 evaluate to true.

If you use my_pair as a key into a map you will not get any compiler errors or warnings but you will likely see some bizarre runtime behavior. For example, keys which were successfully insert()ed may not be able to be found using find().

A correct version of operator< (which places minimal burden on T1 and T2 — they are only required to implement operator<) is:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


template<typename T1, typename T2>
inline bool operator<
    (
    const my_pair<T1, T2>& x,
    const my_pair<T1, T2>& y
    )
{
    return
        (
        x.first < y.first ||
        (!(y.first < x.first) && x.second < y.second)
        );
}