Data structure similar to a 2-argument map

Question

Is there a data structure (readily available in STL or boost), that accepts two arguments and maps it to a certain value?

Examples would be for returning certain information in a coordinate grid or getting the weight of an edge in a graph:

coordinate_quadrant(-1,-1) = 3

weight_of(u,v) = 10

The quadrant example could be done in a simple function with four if statements. I'm mainly looking for an example that would suit the weight example. I'm trying to avoid having to create an edge class and pass that into the weight_of(Edge edge) function.

Answer 1

You could use std::map< std::pair<Type1,Type2>, Type3 >.

Answer 2

Use an object that is a pair of integers on the back end. In other words, implement map, but for this pair object. You can't override operator [] to accept multiple arguments, but you can override operator () on a custom map class, so you can get some syntactical sugar e.g. my_map[row](col) = whatever

Answer 3

I would consider the following choices:

Option 1

std::map with std::pair< Type1, Type2 > as the key and Type3 as the value

std::map< std::pair< Type1, Type2 >, Type3 > data;

Option 2

2-dimensional std::vector

In case that the Type1 and Type2 are integers, as you might find when modeling a graph or Cartesian space: std::vector< std::vector< Type3 > > data;

Option 3

user-defined class containing Type1 and Type2, which can be mapped to Type3

In case you might ever want to decorate your two types with more values, you could define a class that contains both of your types, and use a std::map to map it to the third type:

public:
    MyClass( Type1 x, Type2 y ) : x_( x ), y_( y )

    Type1 x() const {
        return x_;
    }

    Type2 y() const {
        return y_;
    }


private:
    Type1 x_;
    Type2 y_;
};


std::map< MyClass, Type3 > data;

The benefit of Option 1 is that it's really fast and easy to code, and should make sense to anyone who knows C++. Option 2 is likely a small bit faster, and has the added benefit that it can easily be modified to have more dimensions. The downside of Option 2 is that your values need to be integer indices into the 2-dimensional vector.

In my opinion Option 3 is the best choice to me because it's readable, places no requirements on the type of Type1 and Type2, and can be extended to contain more data in a very reasonable way. The downside to Option 3 is that you need to define a StrictWeakOrdering for comparing MyClass objects to each other, but that's fairly straightforward:

bool operator<(const MyClass & rhs) const {
    return ( rhs.x() <= x() && rhs.y() <= y() );
}

Make that a member function of your class, and you should be ready to go.

Like many things in programming, there's not an obvious right answer until you consider the specifics of what you're doing and how much time you're willing to invest. Don't forget to check for key existence and out-of-bounds errors. :)