c++ - 将 unsigned int 的三元组映射到 double——这是最优化/最有效的方法吗？

Question

我面临以下任务: 将无符号整数的三元组映射到一个值，该值要么是零要么是正数( double )；并且能够为给定的三胞胎获得双倍或说它实际上为零；

我有以下简化: 第一个(我们称之为 I)和第二个(我们称之为 J)整数在已知范围内(从零到 IMAX 和 JMAX)。 对于第三个索引(K)，我知道三胞胎的估计(第三个索引是分散的)，说 ESTIMATE； 在计算三元组数量增长时，更准确地说，对于给定的 I 和 K，第三个指标的数量可以增加。

到目前为止，我看到了以下解决方案:

保留 map vector 的 vector :

vector< vector < map <unsinged int, unsigned int>>>  tri_map_;
//^I    ^J            ^K            ^index

如果 'index' 不为零，则从补充 vector 中获取值:

vector< double> values;
values[index];

整个事情要初始化为:

tri_map_.resize(IMAX);
for (int i=0;i<IMAX;++i) tri_map_[i].resize(JMAX);

您如何看待该解决方案？有更好的方法吗？

我不喜欢的是，我似乎不能为 map 。有没有办法尝试分配足够的内存(因为我估计了第三个索引)并检查是否有足够的内存？除此之外，我对此很满意。

编辑1: IMAX ~ 百人 JMAX ~ 10^5

编辑2: 试图合并 sehe 的解决方案，但对于 unordered_set 和 for pair； 所以，这就是我遇到问题的地方 specialization of ‘template<class _Tp> struct std::tr1::hash’ in different namespace : ... EDIT3:以下作品，将调查其速度。 感谢大家的建议和建议!

#include <tr1/functional>
#include <vector>
#include <map>
#include <tr1/unordered_set>
#include <list>
#include <set>
#include <tr1/array>
#include <iostream>

struct pair_int {
    unsigned int first;
    unsigned int second;

    bool operator< (pair_int const& o) const {
        if ( first < o.first )
        return true;
        if ( first > o.first )
          return false;
        return second < o.second;
   }
   bool operator==(pair_int const& o) const {
        return ( (first==o.first)&&(second==o.second) );
   }
};

namespace std {
namespace tr1 {
    template<> struct hash<pair_int> {
        unsigned int operator()(pair_int const& key) const {
            return  ~key.first + 17u*key.second;
        }
    };
}
}

class pair_storage {
public:
    pair_storage() {};  
    ~pair_storage();
    ....
private:
    pair_int pair_ij_;
    std::map<pair_int,double>::iterator  pairMapIterator_;
    std::vector< std::map<pair_int,double> >  pairMapVector_;
    std::vector< std::tr1::unordered_set< pair_int > > pairMapVectorZero_;
};

无法用 -std=c++0x 编译它因为我在大代码的某些部分有一些问题...

Answer 1

我觉得你在找

• std::map
• std::multimap
• std::unordered_map
• std::unordered_multimap

这是一个使用 std::unordered_multimap 的简单示例(这需要将 std::hash<> 专门化为您的 key 类型，因此是一种稍微复杂的编写方式):

#include <tuple>
#include <unordered_map>
#include <cassert>
#include <iostream>

struct triplet 
{ 
    unsigned a,b,c;
    bool operator< (triplet const& o) const { return std::tie(a,b,c) < std::tie(o.a,o.b,o.c); }
    bool operator==(triplet const& o) const { return std::tie(a,b,c) ==std::tie(o.a,o.b,o.c); }
};

namespace std {
    template<> struct hash<triplet> {
        unsigned int operator()(triplet const& key) const { 
            return  ~key.a + 17u*key.b + 17u*key.c; // totally made that up, could be better, I suppose
        }
    };
}

static std::ostream& operator<<(std::ostream& os, triplet const& key) {
    return os << '[' << key.a << ',' << key.b << ',' << key.c << ']';
}

int main()
{
    std::unordered_multimap<triplet, double> map;

    // insert items dynamically
    map.insert({ triplet{ /*I*/ 1, /*J*/ 2, /*K*/ 3 },  0.1 } );
    map.insert({ triplet{ /*I*/ 4, /*J*/ 5, /*K*/ 6 },  0.2 } );
    map.insert({ triplet{ /*I*/ 7, /*J*/ 8, /*K*/ 9 },  0.3 } );
    map.insert({ triplet{ /*I*/ 1, /*J*/ 2, /*K*/ 0 },  0.4 } ); // duplicate (I,J) ok

    map.insert({ triplet{ /*I*/ 1, /*J*/ 2, /*K*/ 0 }, 0.5 } );

    assert(0 == map.count(triplet {1,5,6}));
    assert(1 == map.count(triplet {4,5,6}));

    auto range = map.equal_range(triplet { 1,2,0 });
    for (auto it=range.first; it!=range.second; ++it)
        std::cout << it->first << ": " << it->second << "\n";
}

输出(如 http://ideone.com/pm8Oz 所示):

[1,2,0]: 0.4
[1,2,0]: 0.5