STL Map Use

What’s wrong with the following code?

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:

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:

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)
        );
}

About Steven Engelhardt, CFA, AIF
Adjunct Professor of Software Engineering at DePaul University • Software Engineering, Data & Analytics in FinTech • Lives in Chicago, IL

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s