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<i nt,int>,int>,do uble> 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 2352
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<i nt,int>,int>,do uble> 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(SumKe y(1,2,3)) != m.end()) {
std::cout<<"Key found"<<std::en dl;
}
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<i nt,int>,int>,do uble> 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**********@Ho me.com
"Markus Dehmann" <ma************ @gmail.com> wrote in message
news:42******** *****@individua l.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<i nt,int>,int>,do uble> 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<i nt,int>,int>,do uble> 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******** *****@individua l.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 (preferrabl y 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<i nt,int>,int>,do uble> 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,i nt>.
--
Pete Becker
Dinkumware, Ltd. ( http://www.dinkumware.com)
"Pete Becker" <pe********@acm .org> wrote in message
news:S9******** *************** *******@giganew s.com... Markus Dehmann wrote: map<pair<pair<i nt,int>,int>,do uble> 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,i nt>.
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<i nt,int>,int>,do uble> 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,i nt>.
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). 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',
description varchar(50) NOT NULL default '',
color varchar(30) NOT NULL default '',
price decimal(3,2) NOT NULL default '0.00',
UNIQUE KEY (color)
);
|
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 the following =
MySQL
error:
INSERT INTO product_access_level (product_id,access_level_id) VALUES
|
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 versions:
mysqld-max-nt --console --transaction-isolation=SERIALIZABLE
In 4.0.15-win I can extract the following error after I run the table
creation script:
ERROR 1005: Can't create table '.\ibdata\#sql-a14_3.frm'
|
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 generate one key file for each assembly?
Perhaps, I should generate a key file per group of
related assemblies?
|
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 doesn't appear to be
any standardised keyboard event interface other than this DOM 3 Events
W3C Working Group Note . However, it is only a note and doesn't
appear to be implemented in any browser. Is there another standard that
I've missed?
The...
| |
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,
first_name VARCHAR(15) NOT NULL,
last_name VARCHAR(30) NOT NULL,
email VARCHAR(40) NULL,
password VARCHAR(16) 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), number (nu) {}
bool operator< (const Key &key) const; //my question is how to
|
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 end that they first statements bring up
in my mind...
a) Because two developers, unbeknownst to each other, can end up releaseing
different dll's with the same name, one should sign an assembly with a unique
tag. right?
|
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 -- it seems to be working fine -- I am able to
retrieve the connection string with no problem after it's been encrypted.
Let me show you the snippet of code that performs the encryption:
using System.Configuration;
|
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: marktang |
last post by:
ONU (Optical Network Unit) is one of the key components for providing high-speed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However, people are often confused as to whether an ONU can Work As a Router. In this blog post, we’ll explore What is ONU, What Is Router, ONU & Router’s main usage, and What is the difference between ONU and Router. Let’s take a closer look !
Part I. Meaning of...
| |
by: Hystou |
last post by:
Overview:
Windows 11 and 10 have less user interface control over operating system update behaviour than previous versions of Windows. In Windows 11 and 10, there is no way to turn off the Windows Update option using the Control Panel or Settings app; it automatically checks for updates and installs any it finds, whether you like it or not. For most users, this new feature is actually very convenient. If you want to control the update process,...
|
by: tracyyun |
last post by:
Dear forum friends,
With the development of smart home technology, a variety of wireless communication protocols have appeared on the market, such as Zigbee, Z-Wave, Wi-Fi, Bluetooth, etc. Each protocol has its own unique characteristics and advantages, but as a user who is planning to build a smart home system, I am a bit confused by the choice of these technologies. I'm particularly interested in Zigbee because I've heard it does some...
|
by: agi2029 |
last post by:
Let's talk about the concept of autonomous AI software engineers and no-code agents. These AIs are designed to manage the entire lifecycle of a software development project—planning, coding, testing, and deployment—without human intervention. Imagine an AI that can take a project description, break it down, write the code, debug it, and then launch it, all on its own....
Now, this would greatly impact the work of software developers. The idea...
|
by: isladogs |
last post by:
The next Access Europe User Group meeting will be on Wednesday 1 May 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM).
In this session, we are pleased to welcome a new presenter, Adolph Dupré who will be discussing some powerful techniques for using class modules.
He will explain when you may want to use classes instead of User Defined Types (UDT). For example, to manage the data in unbound forms.
Adolph will...
|
by: conductexam |
last post by:
I have .net C# application in which I am extracting data from word file and save it in database particularly. To store word all data as it is I am converting the whole word file firstly in HTML and then checking html paragraph one by one.
At the time of converting from word file to html my equations which are in the word document file was convert into image.
Globals.ThisAddIn.Application.ActiveDocument.Select();...
|
by: adsilva |
last post by:
A Windows Forms form does not have the event Unload, like VB6. What one acts like?
| |
by: 6302768590 |
last post by:
Hai team
i want code for transfer the data from one system to another through IP address by using C# our system has to for every 5mins then we have to update the data what the data is updated we have to send another system
|
by: muto222 |
last post by:
How can i add a mobile payment intergratation into php mysql website.
| |