4

我面临以下任务：将无符号整数的三元组映射到一个值，该值为零或正（双）；并且能够为给定的三元组获得双倍或说它实际上为零；

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

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

保持地图向量的向量：

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

如果 'index' 不为零，则从补充向量中获取值：

vector< double> values;
values[index];

整个东西被初始化为：

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

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

我不喜欢的是，我似乎无法为地图做“保留”之类的事情。有没有办法尝试分配足够的内存（因为我估计了第三个索引）并检查是否有足够的内存？除此之外我很满意。

EDIT1：IMAX ~ 数百 JMAX ~ 10^5

EDIT2：试图合并sehe的解决方案，但对于unordered_set和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因为我在大代码的某些部分有一些问题......

4

3 回答 3

3 
struct Triple
{
    unsigned int A;
    unsigned int B;
    unsigned int C;
};

map<Triple, double> mapping;
于 2012-06-11T14:11:42.340 回答
3

在我看来你正在寻找

这是一个使用 std::unordered_multimap 的简单示例（这将需要std::hash<>对您的键类型进行专门化，因此编写它的方式稍微复杂一些）：

#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
于 2012-06-11T14:32:46.557 回答
1

关于“这是最优化/最有效的方式吗？”的问题：

尝试使用hash_mapor unordered_map; 这可能比map（或可能不是，取决于您的用例）更快。

关于“有没有办法尝试分配足够的内存......？”这个问题：

您可以使用它unordered_map::max_load_factor来调整内存/性能权衡；这就像预分配一样。

哦，您还可以使用unordered_set来存储映射为零的元素。这可能会减少内存消耗而无需性能成本。

于 2012-06-11T13:54:00.757 回答