4

私は次のタスクに直面しています。unsignedintのトリプレットをゼロまたは正（double）の値にマップします。そして、与えられたトリプレットがダブルを取得するか、実際にはゼロであると言うことができます。

私は次の単純化を持っています：最初（それをIと呼びましょう）と2番目（それをJと呼びましょう）intは既知の範囲（ゼロからIMAXとJMAXまで）にあります。3番目のインデックス（K）については、トリプレットの推定値（3番目のインデックスは分散している）を知っています。計算中、トリプレットの成長数、より正確には、特定のIとKについて、3番目のインデックスの数が増える可能性があります。

これまでのところ、次の解決策があります。

マップのベクトルのベクトルを保持します：

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);

その解決策についてどう思いますか？それを行うためのより良い方法はありますか？

私が嫌いなのは、マップの「予約」のようなことはできないようだということです。十分なメモリを割り当てて（3番目のインデックスの見積もりがあります）、そのための十分なメモリがあるかどうかを確認する方法はありますか？それを除けば、私はそれに満足しています。

編集1：IMAX〜数百のJMAX〜10 ^ 5

EDIT2：seheのソリューションを取り入れようとしていますが、unordered_setとペア用です。だから、それは私が問題を抱えているところです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_;
};

cosでコンパイルできません-std=c++0x大きなコードのいくつかの部分で問題があります...

4

3 に答える 3

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_mapまたはunordered_map;を使用してみてください。それはより速いかもしれませんmap（ユースケースによってはそうでないかもしれません）。

「十分なメモリを割り当てる方法はありますか...?」という質問について:

unordered_map::max_load_factorメモリとパフォーマンスのトレードオフを調整するために使用できます。これは事前割り当てのようなものです。

ああ、unordered_setゼロにマップする要素を格納するために使用することもできます。これにより、パフォーマンス コストなしでメモリ消費を削減できます。

于 2012-06-11T13:54:00.757 に答える