how to implement c++ table lookup?

I have a two dimensional array for a table lookup in some old C code. What would be the nicer c++ way?

I may be totally off, but I was thinking of using a

Code:

---

std::map<std::pair<int,int>,int>

---

But how would I initialize the constant table so its done only once?

I could use arrays again, but the indexes aren't ordered. For example, the table looks like: array[0][0] = 1; Then the next valid value is: array[0][8] =3. In other words array[0][1-7] are unused.

You could try...

Code:

---

std::map<int, std::map<int, int>>

---

not sure I follow. But I think I do. Still, how would I initialize a constant static map class variable such as you suggest so its done only once?

What are the ranges of the indexes?

indexes are 0 to 100

You could maybe do something like this..

Code:

---

#include <map>

struct Item
{
    Item(int x, int y, int value)
        : x(x),
          y(y),
          value(value)
    {
    }

    int x;
    int y;
    int value;
};

const Item items[] =
{
    Item(0, 0, 1),
    Item(0, 8, 3),
    // + more...
    Item(-1, -1, -1) // Terminator.
};

int main()
{
    typedef std::map<int, std::map<int, int>> Lookup;

    Lookup lookup;

    for (int i = 0; items[i].x != -1; ++i)
    {
        lookup[items[i].x][items[i].y] = items[i].value;
    }
}

---

You can also go with your original idea of using map<pair<int, int>, int>, in which case you can initialize the map itself at compile time:

Code:

---

#include <map>
using namespace std;

pair<pair<int, int>, int> data[] =
{
    make_pair(make_pair(0, 5), 2),
    make_pair(make_pair(2, 100), 8),
    make_pair(make_pair(70, 30), 56)
};

const int N = sizeof(data) / sizeof(data[0]);

class some_class
{
private:
    static const map<pair<int, int>, int> lookup_table;
};

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

---

The only disadvantage is that to access the lookup table, you need the cumbersome make_pair() notation:

Code:

---

int val = lookup_table[make_pair(0, 5)];

---

You could write a wrapper class that overloads operator [] if you want the cleaner lookup_table[0][5] syntax.

I didn't explain myself correctly, I don't want to use any C code.

I got this code to compile:
The .h

Code:

---

#include <map>

class A {
private:
typedef std::map<int, std::map<int, int> > maptype_t;

static const maptype_t mapconst;
static maptype_t init_mapconst();
}

inline A::maptype_t *
A::init_mapconst()
{
maptype_t m;
m[0][0] = 23;
m[0][8] = 42;
return &m;
}

---

the .cpp

Code:

---

const A::maptype_t
A::mapconst =
A::init_mapconst();

---

But I have the following issues with this code:
1) It's too complicated. For example, it doesn't compile unless I inline the init_mapconst function.
2) I am unsure of the speed of accessing this table

I wonder if I should just stick to a two dimensional array. C wins for table lookups?

Quote:

---

Originally Posted by HighCommander4

You can also go with your original idea of using map<pair<int, int>, int>, in which case you can initialize the map itself at compile time:

Code:

---

#include <map>
using namespace std;

pair<pair<int, int>, int> data[] =
{
    make_pair(make_pair(0, 5), 2),
    make_pair(make_pair(2, 100), 8),
    make_pair(make_pair(70, 30), 56)
};

const int N = sizeof(data) / sizeof(data[0]);

class some_class
{
private:
    static const map<pair<int, int>, int> lookup_table;
};

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

---

The only disadvantage is that to access the lookup table, you need the cumbersome make_pair() notation:

Code:

---

int val = lookup_table[make_pair(0, 5)];

---

You could write a wrapper class that overloads operator [] if you want the cleaner lookup_table[0][5] syntax.

EDIT: You can also use this technique to initialize a map<int, map<int, int> > at compile time if you really want to, it would just be more cumbersome and less intuitive.

---

this is interesting. I didn't know about the make_pair function. I think your suggestion will still work for std::map< int, std::map<int,int> > . I just need to figure out the syntax. That way I eliminate having to have a static inline function to initialize the map.

If you have such a small range (0 to 100) directly mapped to integers and you don't need ordering you can also use std::vector<std::vector<int> >.

Another option is a hash table implementation. You'll get faster lookup/access when compared to std::map. (This is in the case you dont't need traversal or selection of the n-th largest/smallest element.) Just notice that std::hash_map and similars are not standard. Most compilers have their own model. I also have one.

If you really want to get the [][] syntax without writing a wrapper class, you can also initialize a map<int, map<int, int> > at compile time, it's just more cumbersome:

Code:

---

#include <map>
using namespace std;

pair<int, int> data1[] = { make_pair(4, 5), make_pair(8, 9) };
pair<int, int> data2[] = { make_pair(1, 9), make_pair(7, 11) , make_pair(11, 15)};
const int data1N = sizeof(data1) / sizeof(data1[0]);
const int data2N = sizeof(data2) / sizeof(data2[0]);

pair<int, map<int, int> > data[] =
{
    make_pair(0, map<int, int>(data1, data1 + data1N)),
    make_pair(2, map<int, int>(data2, data2 + data2N)),
};

const int N = sizeof(data) / sizeof(data[0]);

class some_class
{
public:
    static const map<int, map<int, int> > table;
};

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

---

Now we have

Code:

---

table[0][4] = 5
table[0][8] = 9
table[2][1] = 0
table[2][7] = 11
table[2][11] = 15

---

Of course, in your actual code, you'll probably want all the crud (data1, data2, data1N, data2N etc.) to be private static members of your class as opposed to polluting the global namespace.

http://www.boost.org/doc/libs/1_39_0...doc/index.html

May have some easier syntax for compile-time initialization of the map.

Also, Boost.uBLAS contains several "sparse matrix" structures which may be useful.

The cleanest option from a usage POV is probably going to be to make a little wrapper class around your map that lets you access it with operator(). You could then use the singleton pattern to prevent the map from being duplicated, and simply use the constructor of the wrapper class to initialize the map.

Would look something like:

Code:

---

#include <map>
#include <sstream>
#include <iostream>
#include <stdexcept>

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

  Table( )
  {
    m_table[std::make_pair(0, 0)] = 1;
    m_table[std::make_pair(0, 8)] = 3;
  }

  Table(Table&);
  Table& operator=(Table&);

public:
  static Table& GetSingleton( )
  {
    static Table instance;
    return instance;
  }

  int operator()(int x, int y) const
  {
    TableMap::const_iterator it = m_table.find(std::make_pair(x, y));

    if (it == m_table.end( ))
    {
      std::stringstream ss;
      ss << "Value (" << x << "," << y << ") not in table";
      throw std::out_of_range(ss.str( ));
    }

    return it->second;
  }
};

int main( )
{
  try
  {
    std::cout << Table::GetSingleton( )(0, 0) << std::endl;
    std::cout << Table::GetSingleton( )(0, 1) << std::endl;
  }
  catch (const std::exception& e)
  {
    std::cout << e.what( ) << std::endl;
  }

  return 0;
}

---

Quote:

---

Originally Posted by HighCommander4

...

Of course, in your actual code, you'll probably want all the crud (data1, data2, data1N, data2N etc.) to be private static members of your class as opposed to polluting the global namespace.

---

Not sure I can live with the crud :/ One question, where can i find documentation that shows the map constructor for the following code?

Code:

---

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

---

Lindley, I am not allowed to use boost.

Quote:

---

Originally Posted by Speedo

The cleanest option from a usage POV is probably going to be to make a little wrapper class around your map that lets you access it with operator(). You could then use the singleton pattern to prevent the map from being duplicated, and simply use the constructor of the wrapper class to initialize the map.

---

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

Quote:

---

Originally Posted by sdcode

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.

Quote:

---

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

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:

Code:

---

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>).

Quote:

---

Originally Posted by sdcode

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.

Something like this:

Code:

---

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

---

Quote:

---

Originally Posted by HighCommander4

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 :D). 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!!!

[][] 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.

Quote:

---

Originally Posted by 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.

---

thanks for the warning.

my code looks like this:

Code:

---


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 ?

Quote:

---

Originally Posted by 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.

---

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:

Code:

---

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

---

Quote:

---

Originally Posted by sdcode

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:

Code:

---

#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> >&).

Quote:

---

Originally Posted by HighCommander4

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...

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?

Quote:

---

Originally Posted by sdcode

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.

Quote:

---

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.

Quote:

---

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...

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?