how to implement c++ table lookup?

[sdcode]

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

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.

[JohnW@Wessex]

You could try...

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

[sdcode]

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?

[JohnW@Wessex]

What are the ranges of the indexes?

[sdcode]

indexes are 0 to 100

[JohnW@Wessex]

You could maybe do something like this..

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

[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:

#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:

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.

[sdcode]

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

I got this code to compile:
The .h

 #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

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?

[sdcode]

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:

#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:

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.

[ltcmelo]

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.

[HighCommander4]

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:

#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

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.

[Lindley]

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.

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

Would look something like:

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

[sdcode]

...

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?

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

Lindley, I am not allowed to use boost.

[sdcode]

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?