键值对：键由3个整数组成 [英] key-value pairs: key consists of 3 ints
问题描述
我有键值对，其中键由3个整数组成，值
是双精度值。我想知道什么是存储它们的最佳方式
（最好是在STL容器中）。应该可以快速查找。
整数不是连续的，但非常稀疏，所以3-dim数组不是
s解决方案。
我尝试过这个：
#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）]<<结束;
返回0;
}
但我想知道这是否是最佳/最有效的方法它。也许使用
一个stl_map？我必须定义自己的哈希函数吗？可以
有人张贴了一个小例子吗？
谢谢！
Markus
Markus Dehmann sade：我有键值对，其中键由3个整数组成，值
是双精度值。我想知道什么是最好的存储方式
（最好是在STL容器中）。应该可以快速查找。
整数不是连续的，但非常稀疏，所以3-Dim数组不是解决方案。
你不用担心一点点现在很多;）
我试过这个：
#include< iostream>
#include< map>
使用命名空间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;
返回0;
}
但我想知道这是否是最佳/最有效的方式。也许使用
一个stl_map？我必须定义自己的哈希函数吗？可以
有人发布一个小例子吗？
如果你可以保证三个int的总和不会导致溢出：
（未经测试）
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）{}
朋友布尔运算符< （SumKey const& sk1，SumKey const& sk）;
};
bool运算符< （SumKey const& sk1，SumKey const& sk2）{
if（sk1.d_s< sk2.d_s）返回true;
if（sk1.d_s> ; sk2.d_s）返回false;
if（sk1.d_a< sk2.d_a）返回true;
else if（sk1.d_a == sk2.d_a）
if（sk1.d_b< sk2.d_b）返回true;
else if（sk1.d_b == sk2.d_b）
if（sk1.d_c< sk2.d_c）返回true;
返回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 ;
}
返回0;
}
TB
On Sun，2006年1月15日12:12:32 -0500，Markus Dehmann
< ma ************ @ gmail。 COM>写道：
我有键值对，其中键由3个整数组成，值
是双精度值。我想知道什么是最好的存储方式
（最好是在STL容器中）。应该可以快速查找。
整数不是连续的，但非常稀疏，所以3-Dim数组不是解决方案。
我试过这个：
＃包括< iostream>
#include< map>
使用命名空间std;
int main（）{
map< pair< pair< int，int>，int>，双> m;
m [make_pair（make_pair（2323,121），452）] = 1.2;
cout<< m [make_pair（make_pair（2323,121），452）]<< endl;
返回0;
}
但我想知道这是否是最佳/最有效的方式。也许使用
一个stl_map？我必须定义自己的哈希函数吗？可以
某人发布一个迷你的例子吗？
根据三个整数允许的值范围，你
晚上可以将它们打包成很长的长（或__int64，如果你的
编译器长时间不支持）。上面的提议没问题，但处理嵌套对<>所需的
语法是必需的。类型使我的头发坚持
结束。如果范围足够小，你可能想要将它们打包成一个无符号整数（例如，使用位字段）。
我想std： ：map< double，double>将是一个有点可行的
替代方案。无论如何，你会想要在一些独立的功能中封装密钥创建和
解释，以使它对客户透明，除非你能逃脱使用命名位
字段。
如果需要生成密钥，可能需要哈希函数。
如果key是自然键。仅仅结合
三个给定的整数，我会尝试按原样使用它们。
-
Bob Hairgrove
No**********@Home.com
" Markus Dehmann" <毫安************ @ gmail.com>在消息中写道
news：42 ************* @ individual.net ...我有键值对，其中key由3个整数组成，值
为double。我想知道什么是最好的存储方式
（最好是在STL容器中）。应该可以快速查找。
整数不是连续的，但非常稀疏，所以3-Dim数组不是解决方案。
我试过这个：
＃包括< iostream>
#include< map>
使用命名空间std;
int main（）{
map< pair< pair< int，int>，int>，双> m;
m [make_pair（make_pair（2323,121），452）] = 1.2;
cout<< m [make_pair（make_pair（2323,121），452）]<< endl;
返回0;
}
但我想知道这是否是最佳/最有效的方式。也许使用
一个stl_map？我必须定义自己的哈希函数吗？可以
有人发布一个小例子吗？
谢谢！
Markus
和往常一样这些类型的问题取决于最好的定义。
但是，恕我直言，嵌套对隐含的语法相当古怪。
我个人建议创建一个关键类存储你的三个整数
并提供一个排序运算符<以及比较器。这很快就完成了
你可以测试它与嵌套对相比的性能，但是作为一个猜测，我认为它应该不会更糟。
stl_map究竟是什么意思？我只知道这是一个内部标题
文件，它肯定不是标准容器。可能你的意思是哈希
地图，它（至少到现在为止）是SGI提供的标准库
的扩展。如果标准地图不够，你可以试试
一个。
HTH
Chris
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
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
这篇关于键值对：键由3个整数组成的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
