Re: std::map question

On Dec 27 2009, 3:40 am, "Jack" <j...@knight.com> wrote:


You can get a std::map to use a type as a key type, however getting it
to run as desired may be more difficult. The difficulty is that you
have to come up with a "strict weak ordering" for the key type. For
some simple types, like int, the library provides one for you. For
custom data types you will need to define your own.
A strict weak ordering has a complicated technical meaning (http://
www.sgi.com/tech/stl/StrictWeakOrdering.html or
http://en.wikipedia.org/wiki/Strict_weak_ordering). Basically what we
are trying to do is give a way for the std::map to tell if one key is
less than another.

Take your D3DXVECTOR3 as an example. How do we say if one vector is
less than another? Perhaps if the x, y, and z components are less
than the other vectors respective components? Perhaps the magnitude
of the vector? Let's try one.

struct D3DXVECTOR3
{
    float x;
    float y;
    float z;
};

// Write a functor that we can give to std::map to compare
D3DXVECTOR3s:
struct D3DXVECTOR3_LessThan
{
    bool operator()(D3DXVECTOR3 lhs, D3DXVECTOR3 rhs) const
    {
        return lhs.x<rhs.x && lhs.y<rhs.y && lhs.z<rhs.z;
    }
};

int main()
{
    D3DXVECTOR3 const v1 = {1, 2, 3};
    D3DXVECTOR3 const v2 = {10, 1, 3};
    D3DXVECTOR3 const v3 = {0, 0, 0};
    D3DXVECTOR3 const v4 = {1, 3, 10};

    std::map<D3DXVECTOR3, int, D3DXVECTOR3_LessThan> map;
    map[v1] = 1;
    map[v2] = 2;
    map[v3] = 3;
    map[v4] = 4;

    std::cout << map[v1] << std::endl; // 4
    std::cout << map[v2] << std::endl; // 4
    std::cout << map[v3] << std::endl; // 3
    std::cout << map[v4] << std::endl; // 4

    return 0;
}

As you can see, it compiled and ran without problems, but the results
were probably not what we wanted. The problem is the less than
function doesn't meet all the requirements of a strict weak ordering.
Consider the points {1, 2, 3} and {3, 2, 1}: neither point is less
than (or equal to) the other. Let's extend the LessThan operator a
little, to make x the "most significant" component, y the next most
significant, and z the least:

struct D3DXVECTOR3_LessThan
{
    bool operator()(D3DXVECTOR3 lhs, D3DXVECTOR3 rhs) const
    {
        return lhs.x < rhs.x ||
               (lhs.x==rhs.x && lhs.y<rhs.y) ||
               (lhs.x==rhs.x && lhs.y==rhs.y && lhs.z<rhs.z);
    }
};

Now when we run, we get the expected behavior.

If you are having trouble coming up with a "strict weak ordering" for
your key type, another class you might look at is std::unordered_map
(aka std::tr1:unordered_map or hash_map depending on the state of your
compiler). Here "all" you have to do is come up with a hashing
function and an equality operator.