how to implement c++ table lookup?

[HighCommander4]

Not sure I can live with the crud :/

If data1, data2, etc. happen to be the same size, you can use a 2D array instead. Beyond that, I don't think there's much you can do, except use Speedo's solution, which is admittedly much cleaner.

One question, where can i find documentation that shows the map constructor for the following code?

 const map<int, map<int, int> > some_class::table(data, data + N);

Take a look at http://www.sgi.com/tech/stl/Map.html

The constructor in question is this one:

template <class InputIterator>
map(InputIterator f, InputIterator l)

InputIterator can be any iterator (including a pointer into an array) whose value type is the map's value_type (the value type of map<T, U> is pair<T, U>).

[HighCommander4]

I like this idea. Would it be possible to get [][] to work somehow?

Everything is possible.
The question is, how much work does it take?

To get [][] to work, you'd have to overload your class's operator[] and have it return a proxy object which in turn overloads operator[] and returns the desired integer.

[HighCommander4]

Something like this:

#include <map>
using namespace std;

class Table
{
    typedef map<int, map<int, int> > TableMap;
    TableMap m_table;

    class proxy
    {
        const map<int, int>& m_map;
        
    public:
        proxy(const map<int, int>& m) : m_map(m) {}

        int operator[](int x) const
        {
            return m_map.find(x)->second;
        }
    };        
public:
    Table()
    {
        // initialize table
    }

    proxy operator[](int x) const
    {
        return proxy(m_table.find(x)->second);
    }
};

[sdcode]

This solution uses map<int, map<int, int> >, and as a result initializing the table is more messy than in Speedo's example (which is why I left out the initialization code ). You can also get this to work with map<pair<int, int>, int> if you want cleaner initialization code. I'll leave it up to you to figure out how to implement the proxy class in that case.

Actually, the initializer is simpler. it's just table[0][0] = 8; etc...

I think I'll stick to the speedos () idea with map< int, map<int,int> >. Maybe i'll go the [][] route if I notice my code isn't as pretty as I'd like. Thanks all for your help!!!

[Lindley]

[][] should word automatically with a map< int, map<int,int> >.....

Although, there is one thing to be careful of. Using [] on a map *will* add that key to the map if it isn't there already (with a default-constructed value, in this case 0).

If you want to be able to test whether or not a pair is in the map yet, you'll have to use find() instead.

[sdcode]

[][] should word automatically with a map< int, map<int,int> >.....

Although, there is one thing to be careful of. Using [] on a map *will* add that key to the map if it isn't there already (with a default-constructed value, in this case 0).

If you want to be able to test whether or not a pair is in the map yet, you'll have to use find() instead.

thanks for the warning.

my code looks like this:

 
int GetValueAt(int x,int y)
{
return table[x][y]; 
}

If I try some random x and y where table[x][y] doesn't exist, it will make one? And then return 0 ?

[HighCommander4]

[][] should word automatically with a map< int, map<int,int> >.....

Although, there is one thing to be careful of. Using [] on a map *will* add that key to the map if it isn't there already (with a default-constructed value, in this case 0).

If you want to be able to test whether or not a pair is in the map yet, you'll have to use find() instead.

Right. I was too lazy to write the error-checking part of the operator[]'s, but looking at it again I now see that it wasn't clear why I had the proxy class. Let me try again:

#include <map>
using namespace std;

class Table
{
    typedef map<int, map<int, int> > TableMap;
    TableMap m_table;

    class proxy
    {
        const map<int, int>& m_map;
        
    public:
        proxy(const map<int, int>& m) : m_map(m) {}

        int operator[](int x) const
        {
            map<int, int>::const_iterator iter = m_map.find(x);
            if (iter == m_map.end())
                // throw exception or something
            else
                return iter->second;
        }
    };        
public:
    Table()
    {
        // initialize table
    }

    proxy operator[](int x) const
    {
        map<int, map<int, int> >::const_iterator iter = m_table.find(x);
        if (iter == m_table.end())
            // throw exception or something
        else
            return proxy(iter->second);
    }
};

If I try some random x and y where table[x][y] doesn't exist, it will make one? And then return 0 ?

Yup. That's the point of the proxy class. Otherwise you could just do this:

#include <map>
using namespace std;

class Table
{
    typedef map<int, map<int, int> > TableMap;
    TableMap m_table;

public:
    Table()
    {
        // initialize table
    }

    const map<int, int>& operator[](int x) const
    {
        return m_table[x];
    }
};

(or even just a conversion operator to const map<int, map<int, int> >&).

[sdcode]

Right. I was too lazy to write the error-checking part of the operator[]'s, but looking at it again I now see that it wasn't clear why I had the proxy class. Let me try again:

(or even just a conversion operator to const map<int, int>&).

hmmm I don't want the proxy class. So that means I need to do it spedos way as map<pair<int,int>, int> ??

I tried to get it to work without the proxy class and here is what i came up with that hasn't been tested. Prepare for ugly code...

std::map<int, std::map<int,int> >::const_iterator iter;
std::map<int, int>::const_iterator iter2;

iter = table.find(x);

//check if the row exists
if (iter == table.end())
{   
	//return 0 if it doesn't exist
	return 0;
}
else
{
	//otherwise check if the column exists
	iter2 = iter->second.find(y);
	
	if(iter2 != iter->second.end())
	{
		return iter2->second;
	}
}

Assuming it works, how can i make it pretty?

[HighCommander4]

hmmm I don't want the proxy class.

What's wrong with having a proxy class under the hood? It's completely transparent to users of the Table class.

So that means I need to do it spedos way as map<pair<int,int>, int> ??

If you want the [][] syntax, and you want to give an error instead of inserting a new value into the table when you try to lookup something that isn't already in the table, you pretty much need a proxy class.

I tried to get it to work without the proxy class and here is what i came up with that hasn't been tested. Prepare for ugly code...

std::map<int, std::map<int,int> >::const_iterator iter;
std::map<int, int>::const_iterator iter2;

iter = table.find(x);

//check if the row exists
if (iter == table.end())
{   
	//return 0 if it doesn't exist
	return 0;
}
else
{
	//otherwise check if the column exists
	iter2 = iter->second.find(y);
	
	if(iter2 != iter->second.end())
	{
		return iter2->second;
	}
}

Assuming it works, how can i make it pretty?

OK, now you've confused me. What behaviour do you want if someone tries to look up something that's not in the table?

If you want to return 0, then don't bother with proxy classes and overloaded operators, since this is map's default behaviour. Just define a conversion operator to map<int, map<int, int> >& in your Table class and use map's operator[]. (Yes, this will insert the value 0 into the table under the given indices, but there's no difference between returning 0 on subsequent lookups because the value in the table is 0 versus because the value cannot be found).

If, on the other hand, you want to produce an error, then you need a proxy class with overloaded operator[] (or if you don't want a proxy class and you're OK with the table(x, y) syntax, then just an overloaded operator()) - but that's not what you're doing in the code above, you're returning 0.

So which is it?