-
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.
-
Re: how to implement c++ table lookup?
You could try...
Code:
std::map<int, std::map<int, int>>
-
Re: how to implement c++ table lookup?
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?
-
Re: how to implement c++ table lookup?
What are the ranges of the indexes?
-
Re: how to implement c++ table lookup?
-
Re: how to implement c++ table lookup?
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;
}
}
-
Re: how to implement c++ table lookup?
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.
-
Re: how to implement c++ table lookup?
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?
-
Re: how to implement c++ table lookup?
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.
-
Re: how to implement c++ table lookup?
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.
-
Re: how to implement c++ table lookup?
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.
-
Re: how to implement c++ table lookup?
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.
-
Re: how to implement c++ table lookup?
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;
}
-
Re: how to implement c++ table lookup?
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.
-
Re: how to implement c++ table lookup?
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?
-
Re: how to implement c++ table lookup?
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>).
-
Re: how to implement c++ table lookup?
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.
-
Re: how to implement c++ table lookup?
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);
}
};
-
Re: how to implement c++ table lookup?
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!!!
-
Re: how to implement c++ table lookup?
[][] 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.
-
Re: how to implement c++ table lookup?
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 ?
-
Re: how to implement c++ table lookup?
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> >&).
-
Re: how to implement c++ table lookup?
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?
-
Re: how to implement c++ table lookup?
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?