key-value pairs: key consists of 3 ints

[Markus Dehmann]

I have key-value pairs where the key consists of 3 integers, the value
is a double. I am wondering what's the best way to store them
(preferrably in an STL container). A fast lookup should be possible. The
integers are not consecutive, but very sparse, so a 3-dim array is not
s solution.

I tried this:

#include <iostream>
#include <map>
using namespace std;
int main(){
map<pair<pair<int,int>,int>,double> m;
m[make_pair(make_pair(2323,121),452)] = 1.2;
cout << m[make_pair(make_pair(2323,121),452)] << endl;
return 0;
}

But I wonder if that's the best / most efficient way to do it. Maybe use
an stl_map? Do I have to define my own hash function, then? Could
someone post a mini example of that?

Thanks!
Markus

 

[Chris Theis]

I have key-value pairs where the key consists of 3 integers, the value
is a double. I am wondering what's the best way to store them
(preferrably in an STL container). A fast lookup should be possible. The
integers are not consecutive, but very sparse, so a 3-dim array is not
s solution.

I tried this:

#include <iostream>
#include <map>
using namespace std;
int main(){
map<pair<pair<int,int>,int>,double> m;
m[make_pair(make_pair(2323,121),452)] = 1.2;
cout << m[make_pair(make_pair(2323,121),452)] << endl;
return 0;
}

But I wonder if that's the best / most efficient way to do it. Maybe use
an stl_map? Do I have to define my own hash function, then? Could
someone post a mini example of that?

Thanks!
Markus

As usual with these type of questions it depends how best is defined.
However, IMHO the syntax implied by the nested pairs is rather quirky.
Personally I'd suggest to create a key class that stores your three integers
and supplies a sort operator < as well as a comparator. This is quickly done
and you can test its performance in comparison to the nested pairs, but as a
first guess I think it shouldn't be worse.

What exactly do you mean by stl_map? I only know this as an internal header
file and it is certainly not a standard container. Probably you meant a hash
map, which (at least until now) is an extension to the standard library
supplied by SGI. If the standard map is not sufficient you might try that
one.

HTH
Chris

 

[TB]

Markus Dehmann sade:

I have key-value pairs where the key consists of 3 integers, the value
is a double. I am wondering what's the best way to store them
(preferrably in an STL container). A fast lookup should be possible. The
integers are not consecutive, but very sparse, so a 3-dim array is not
s solution.

Aren't you worrying a tad to much now

I tried this:

#include <iostream>
#include <map>
using namespace std;
int main(){
map<pair<pair<int,int>,int>,double> m;
m[make_pair(make_pair(2323,121),452)] = 1.2;
cout << m[make_pair(make_pair(2323,121),452)] << endl;
return 0;
}

But I wonder if that's the best / most efficient way to do it. Maybe use
an stl_map? Do I have to define my own hash function, then? Could
someone post a mini example of that?

If you can guarantee that the sum of the three int's don't cause overflow:
(Not Tested)

class SumKey {
private:
int const d_a;
int const d_b;
int const d_c;
int const d_s;
public:
SumKey(int const a, int const b, int const c) :
d_a(a),d_b(b),d_c(c),d_s(a + b + c) {}
SumKey(SumKey const & sk) :
d_a(sk.d_a),d_b(sk.d_b),d_c(sk.d_c),d_s(sk.d_a + sk.d_b + sk.d_c) {}

friend bool operator < (SumKey const & sk1, SumKey const & sk);
};

bool operator < (SumKey const & sk1, SumKey const & sk2) {
if(sk1.d_s < sk2.d_s) return true;
if(sk1.d_s > sk2.d_s) return false;

if(sk1.d_a < sk2.d_a) return true;
else if(sk1.d_a == sk2.d_a)
if(sk1.d_b < sk2.d_b) return true;
else if(sk1.d_b == sk2.d_b)
if(sk1.d_c < sk2.d_c) return true;
return false;
}

int main(int argc, char** argv) {
std::map<SumKey,double> m;
m[SumKey(3,3,3)] = 9.;
m[SumKey(1,2,3)] = 6.;
m[SumKey(2,3,1)] = 6.;
m[SumKey(5,5,5)] = 15.;
if(m.find(SumKey(1,2,3)) != m.end()) {
std::cout<<"Key found"<<std::endl;
}
return 0;
}

TB

 

[Bob Hairgrove]

I have key-value pairs where the key consists of 3 integers, the value
is a double. I am wondering what's the best way to store them
(preferrably in an STL container). A fast lookup should be possible. The
integers are not consecutive, but very sparse, so a 3-dim array is not
s solution.

I tried this:

#include <iostream>
#include <map>
using namespace std;
int main(){
map<pair<pair<int,int>,int>,double> m;
m[make_pair(make_pair(2323,121),452)] = 1.2;
cout << m[make_pair(make_pair(2323,121),452)] << endl;
return 0;
}

But I wonder if that's the best / most efficient way to do it. Maybe use
an stl_map? Do I have to define my own hash function, then? Could
someone post a mini example of that?

Depending on the range of values allowed for the three integers, you
night be able to pack them into a long long (or __int64 if your
compiler doesn't support long long). The above proposal is OK, but the
syntax necessary to deal with nested pair<> types makes my hair stand
on end. If the ranges are small enough, you might want to pack them
into a single unsigned integer (e.g., using bit fields).

I suppose std::map<double, double> would be a somewhat workable
alternative. At any rate, you'll want to encapsulate key creation and
interpretation in some stand-alone function in order to make it
transparent to clients unless you can get away with using named bit
fields.

A hash function might be desirable if you need to generate the keys.
If the key is a "natural key" which results from merely combining
three given integers, I would try to use them as is.

 

[TB]

TB sade:

Markus Dehmann sade:

I have key-value pairs where the key consists of 3 integers, the value
is a double. I am wondering what's the best way to store them
(preferrably in an STL container). A fast lookup should be possible.
The integers are not consecutive, but very sparse, so a 3-dim array
is not s solution.

Aren't you worrying a tad to much now

I tried this:

#include <iostream>
#include <map>
using namespace std;
int main(){
map<pair<pair<int,int>,int>,double> m;
m[make_pair(make_pair(2323,121),452)] = 1.2;
cout << m[make_pair(make_pair(2323,121),452)] << endl;
return 0;
}

But I wonder if that's the best / most efficient way to do it. Maybe
use an stl_map? Do I have to define my own hash function, then? Could
someone post a mini example of that?

If you can guarantee that the sum of the three int's don't cause overflow:
(Not Tested)

class SumKey {
private:
int const d_a;
int const d_b;
int const d_c;
int const d_s;
public:
SumKey(int const a, int const b, int const c) :
d_a(a),d_b(b),d_c(c),d_s(a + b + c) {}
SumKey(SumKey const & sk) :
d_a(sk.d_a),d_b(sk.d_b),d_c(sk.d_c),d_s(sk.d_a + sk.d_b + sk.d_c) {}

friend bool operator < (SumKey const & sk1, SumKey const & sk);
};

bool operator < (SumKey const & sk1, SumKey const & sk2) {
if(sk1.d_s < sk2.d_s) return true;
if(sk1.d_s > sk2.d_s) return false;

if(sk1.d_a < sk2.d_a) return true;
else if(sk1.d_a == sk2.d_a)
if(sk1.d_b < sk2.d_b) return true;
else if(sk1.d_b == sk2.d_b)
if(sk1.d_c < sk2.d_c) return true;
return false;
}

Actually you could simplify it to:

bool operator < (SumKey const & sk1, SumKey const & sk2) {
if(sk1.d_a < sk2.d_a) return true;
else if(sk1.d_a == sk2.d_a)
if(sk1.d_b < sk2.d_b) return true;
else if(sk1.d_b == sk2.d_b)
if(sk1.d_c < sk2.d_c) return true;
return false;
}

And skip 'd_s' completely.

 

[Markus Dehmann]

I have key-value pairs where the key consists of 3 integers, the value
is a double. I am wondering what's the best way to store them
(preferrably in an STL container). A fast lookup should be possible. The
integers are not consecutive, but very sparse, so a 3-dim array is not
s solution.

I tried this:

#include <iostream>
#include <map>
>> [...]
But I wonder if that's the best / most efficient way to do it. Maybe use
an stl_map? Do I have to define my own hash function, then? Could
someone post a mini example of that?

As usual with these type of questions it depends how best is defined.
However, IMHO the syntax implied by the nested pairs is rather quirky.
Personally I'd suggest to create a key class that stores your three integers
and supplies a sort operator < as well as a comparator. This is quickly done
and you can test its performance in comparison to the nested pairs, but as a
first guess I think it shouldn't be worse.

Thanks for the suggestions!

What exactly do you mean by stl_map? I only know this as an internal header
file and it is certainly not a standard container. Probably you meant a hash
map, which (at least until now) is an extension to the standard library
supplied by SGI. If the standard map is not sufficient you might try that
one.

Yes, I meant the hash map.

Markus

 

[Pete Becker]

map<pair<pair<int,int>,int>,double> m;

struct three_ints
{
int first;
int second;
int third;
};

You aren't required to use pair just because it's there.

Of course, if you have an implementation of TR1 you can use
tuple<int,int,int>.

 

[Chris Theis]

struct three_ints
{
int first;
int second;
int third;
};

You aren't required to use pair just because it's there.

Of course, if you have an implementation of TR1 you can use
tuple<int,int,int>.

Hi Pete,

is there any compiler that already ships with that? It would be interesting
to know.

Cheers
Chris

 

[Pete Becker]

is there any compiler that already ships with that? It would be interesting
to know.

Not yet. While you're waiting, www.boost.org has an implementation of tuple.

 

[Earl Purple]

struct three_ints
{
int first;
int second;
int third;
};

You aren't required to use pair just because it's there.

Of course, if you have an implementation of TR1 you can use
tuple<int,int,int>.

but does tuple implement operator< (I don't think pair does by the
way), because unless it does it can't be a key in a map (not a regular
map anyway) unless you also provide your own predicate.

hash_map would seem an ideal implementation here because a hashing
algorithm should be fairly straightforward( first ^ second ^ third
perhaps?) and a straightforward < could involve as many as 5
comparisons (when first and second match).

 

[Pete Becker]

but does tuple implement operator< (I don't think pair does by the
way), because unless it does it can't be a key in a map (not a regular
map anyway) unless you also provide your own predicate.

Yes, you have to provide your own predicate.

 

[Pete Becker]

Yes, you have to provide your own predicate.

Whoops, wrong: tuple provides operator< which does a lexicigraphical
comparison.

 

[Fabio Fracassi]

is there any compiler that already ships with that? It would be
interesting to know.

Cheers
Chris

Gcc 4.x provides at least partial tr1 support. "tupel" should be in there.
(see "http://gcc.gnu.org/gcc-4.0/changes.html" section "Runtime Library
(libstdc++)")

HTH

Fabio

 

[Richard Herring]

see below...

Whoops, wrong: tuple provides operator< which does a lexicigraphical
comparison.

As, to answer the implied question above, does std:air.