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 13 2329
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
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
"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
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
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
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)
"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
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)
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).
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)
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)
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
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 This thread has been closed and replies have been disabled. Please start a new discussion. Similar topics
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',...
|
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...
|
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...
|
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...
|
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...
|
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,...
|
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),...
|
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...
|
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...
|
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?
|
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...
|
by: ryjfgjl |
last post by:
ExcelToDatabase: batch import excel into database automatically...
|
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...
|
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...
|
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...
|
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...
|
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...
|
by: Defcon1945 |
last post by:
I'm trying to learn Python using Pycharm but import shutil doesn't work
|
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
| |