5

次のプログラムでは、unordered_mapO（1）の検索/挿入時間を必要としたという理由だけで、現在使用しています。でも今は注文したかったです。毎回ソートするのは非常に非効率的です。私の選択肢は何ですか？私はそれhash_mapが仕事をすることを読みました、しかし私が読んだ記事は私が理解するのに非常に混乱するかかなり複雑です。挿入/検索の複雑さは何hash_mapですか？それは本当に順序付けられていますか？もしそうなら、それはC ++ 0xで定義されていますか？どうすればそれを実装できますか？そうでない場合、他に何を使用できますか？ありがとう。

include <iostream>
#include <iterator>
#include <set>
#include <vector>
#include <unordered_map>

using namespace std;


template <class T>
inline void hash_combine(std::size_t & seed, const T & v)
{
  std::hash<T> hasher;
  seed ^= hasher(v) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
}

template <typename C> struct ContainerHasher
{
  typedef typename C::value_type value_type;
  inline size_t operator()(const C & c) const
  {
    size_t seed = 0;
    for (typename C::const_iterator it = c.begin(), end = c.end(); it != end; ++it)
    {
      hash_combine<value_type>(seed, *it);
    }
    return seed;
  }
};


typedef std::set<int> my_set;
typedef std::vector<int> my_vector;
typedef std::unordered_map<my_set, my_vector, ContainerHasher<std::set<int>>> my_map;
typedef my_map::iterator m_it;

void print(my_map& data)
{
        for( m_it it(data.begin()) ; it!=data.end(); ++it)
        {
                cout << "Key : ";
                copy(it->first.begin(), it->first.end(), ostream_iterator<int>(cout, " "));
                cout << " => Value: ";
                copy (it->second.begin(),it->second.end(),ostream_iterator<int>(cout," "));
                cout << endl;
        }
        cout << "---------------------------------------------------------------\n";
}

int main()
{
   my_vector v1,v2,v3;
  for(int i = 1; i<=10; ++i)
   {
      v1.push_back(i);
      v2.push_back(i+10);
      v3.push_back(i+20);
   }

   my_set s1(v3.begin(),v3.begin()+3);
   my_set s2(v1.begin(),v1.begin()+3);
   my_set s3(v2.begin(),v2.begin()+3);

   my_map m1;

   m1.insert(make_pair(s1,v1));
   m1.insert(make_pair(s2,v2));
   m1.insert(make_pair(s3,v3));

   print(m1);
   my_set s4(v3.begin(),v3.begin()+3);

   m_it it = m1.find(s4);

   if(it != m1.end())
   {
      cout << endl << "found" << endl;
   }
   else
   {
      cout << endl << "Not found" << endl;
   }
}

編集：

以前使ってstd::mapいたのですが、アイテムがたくさんあります（百万単位）。それで、アイテムの数が非常に多い場合でも、map注文したい場合は、皆さんがお勧めしますか？

4

3 に答える 3

9

通常のを使用してstd::mapください。これは、ハッシュではなく順序付けが必要であることを意味することに注意してください。

ちなみに、あんunordered_map はhash_mapです。「Unordered」は、実装の違いではなく概念の違いを捉えているだけなので、より適切な名前です。

于 2011-08-05T01:00:29.570 に答える
1

ソートされた順序が頻繁に必要な場合mapは、順序付けされたコンテナーに切り替えることをお勧めします。挿入と検索の複雑さは対数になりましたが、コンテナーはデフォルトでソートされています。

于 2011-08-05T01:00:50.300 に答える
0

挿入中に要素の順序を維持するには、(順序付き) マップを使用する必要があります。これは、漸近的に log(N) 最悪の場合の挿入の複雑さで設計されており、比較ベースの順序付けアルゴリズムで最良の結果が得られます。

既存の要素への高速な (平均的な) アクセスを提供するには、順序付けされていない (ハッシュ) マップを使用することをお 勧めします。

両方のケースが重要な場合は、両方のマップを手動で使用するか、マップと順序付きマップを同時にカプセル化するラッパー コンテナー クラスを作成することができます。

ただし、この解決策は、読み取り操作が書き込み操作よりも (かなり!) 頻繁に行われ、メモリ消費の欠点がある場合にのみ有効です (キャッシュとページのスワッピングの問題によるパフォーマンスの低下につながる可能性があります)。とにかく、このソリューションにはいくつかの実験とプロファイリングが必要です。

また、順序付けにいくつかの詳細がある場合、たとえば、要素が小さなセット (たとえば、1、2、...10) からの「レート」値によって順序付けられている場合、特定の順序付けアルゴリズムはマップよりも優れている可能性があります (このため順序付けは比較ベースである必要はないかもしれません)

[編集] (厳密に言えば、狭い範囲の値による順序付けに関する私の最後の例は、 std::map の可能な使用と互換性がありません。大量の要素の場合、厳密な弱い順序が明らかに生成されないためです。私はそれを削除しません。一部のアプリケーションでは便利な場合もあります)

于 2011-08-05T08:47:15.620 に答える