473,320 Members | 1,861 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,320 software developers and data experts.

key-value pairs: key consists of 3 ints

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
Jan 15 '06 #1
13 2329
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
Jan 15 '06 #2
On Sun, 15 Jan 2006 12:12:32 -0500, Markus Dehmann
<ma************@gmail.com> wrote:
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.

--
Bob Hairgrove
No**********@Home.com
Jan 15 '06 #3

"Markus Dehmann" <ma************@gmail.com> wrote in message
news:42*************@individual.net...
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

Jan 15 '06 #4
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.

--
TB @ SWEDEN
Jan 15 '06 #5
Chris Theis wrote:
"Markus Dehmann" <ma************@gmail.com> wrote in message
news:42*************@individual.net...
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
Jan 15 '06 #6
Markus Dehmann wrote:
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>.

--

Pete Becker
Dinkumware, Ltd. (http://www.dinkumware.com)
Jan 16 '06 #7

"Pete Becker" <pe********@acm.org> wrote in message
news:S9******************************@giganews.com ...
Markus Dehmann wrote:
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>.


Hi Pete,

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

Cheers
Chris
Jan 16 '06 #8
Chris Theis wrote:

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.

--

Pete Becker
Dinkumware, Ltd. (http://www.dinkumware.com)
Jan 16 '06 #9

Pete Becker wrote:
Markus Dehmann wrote:
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>.

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

Jan 16 '06 #10
Earl Purple wrote:
Pete Becker wrote:
Markus Dehmann wrote:
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>.


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
Dinkumware, Ltd. (http://www.dinkumware.com)
Jan 16 '06 #11
Pete Becker wrote:
Earl Purple wrote:

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.


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

--

Pete Becker
Dinkumware, Ltd. (http://www.dinkumware.com)
Jan 16 '06 #12
Chris Theis wrote:
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

Jan 16 '06 #13
In message <ub********************@giganews.com>, Pete Becker
<pe********@acm.org> writes
Pete Becker wrote:
Earl Purple wrote:

but does tuple implement operator< (I don't think pair does by the
way),
see below...
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.


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

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

--
Richard Herring
Jan 23 '06 #14

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

5
by: Westcoast Sheri | last post by:
Which will be a faster lookup of an item by, "color" in the following mySQL tables: "unique key," "primary key," or just plain "key"?? CREATE TABLE myTable ( number int(11) NOT NULL default '0',...
0
by: Jeremiah Jacks | last post by:
I just upgraded to MySQL 4.0.14-standard for RedHat Linux and am using = the pre-compiled binaries. I have a database with INNODB tables. When I insert a row into one of the child tables, I get...
2
by: geoff | last post by:
The table creation script(at the end of this post) works fine on 4.0.1-alpha-win, but the foreign key constraints fail on 4.0.15-win. I am starting the server with the same command for both...
3
by: Joel Leong | last post by:
I wish to know the industrial practices for signing assemblies with key files. I genereted a key file to sign my assemblies. Should I sign all my assemblies with a single key files or I shall...
3
by: Lachlan Hunt | last post by:
Hi, I've been looking up lots of documentation and trying to work out a cross-platform method of capturing a keyboard event and working out which key was pressed. From what I can find, there...
3
by: Phil Latio | last post by:
I am following a book on PHP and MySQL and have come across the below SQL statement. CREATE TABLE users ( user_id MEDIUMINT(8) UNSIGNED NOT NULL AUTO_INCREMENT, username VARCHAR(20) NOT NULL,...
2
by: eastern_strider | last post by:
I'm running into problems about defining a comparison function for a map which has a user defined key. For example: class Key { public: string name; int number; Key (na, nu) : name (na),...
2
by: Sky | last post by:
Hello: I'm trying to make sense of snk files, when to use, under what conditions to regenerate new ones,...can someone take a look if these statemes make sense? And then the final questions at the...
2
by: Tom Baxter | last post by:
Hi everyone, I have a small block of code that encrypts a database connection string in a ..config file, but I'm not sure where the encryption key comes from. There is no problem with this code...
11
by: Dick Moores | last post by:
Windows XP Pro, Python 2.5.1 import msvcrt while True: if msvcrt.kbhit(): key = msvcrt.getch() if key == 'Enter' do something Is there a way to catch the pressing of the 'Enter' key?
0
by: DolphinDB | last post by:
Tired of spending countless mintues downsampling your data? Look no further! In this article, you’ll learn how to efficiently downsample 6.48 billion high-frequency records to 61 million...
0
by: ryjfgjl | last post by:
ExcelToDatabase: batch import excel into database automatically...
0
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
1
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
0
by: Vimpel783 | last post by:
Hello! Guys, I found this code on the Internet, but I need to modify it a little. It works well, the problem is this: Data is sent from only one cell, in this case B5, but it is necessary that data...
0
by: jfyes | last post by:
As a hardware engineer, after seeing that CEIWEI recently released a new tool for Modbus RTU Over TCP/UDP filtering and monitoring, I actively went to its official website to take a look. It turned...
0
by: ArrayDB | last post by:
The error message I've encountered is; ERROR:root:Error generating model response: exception: access violation writing 0x0000000000005140, which seems to be indicative of an access violation...
0
by: Defcon1945 | last post by:
I'm trying to learn Python using Pycharm but import shutil doesn't work
0
by: af34tf | last post by:
Hi Guys, I have a domain whose name is BytesLimited.com, and I want to sell it. Does anyone know about platforms that allow me to list my domain in auction for free. Thank you

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.