10

私の目標は、ある型の要素を同じ型の他の要素にマップすることです。size_t簡単にするためだとします。

std::map<size_t, size_t> myMapping;

これで十分ですが、そのようなリンクの束をたどりたい場合 (それらはすべて同じマップです)、各ステップはlog(n)ルックアップです。

size_t k = /*whatever*/;
myMapping[myMapping[myMapping[k]]];   //3 * log(n)

マップ イテレータが有効なままであり、size_t をイテレータ自体にマップするマップがあるという事実を利用したいと考えています。

typedef /*myMapTemplate*/::iterator map_iter;
std::map<size_t, map_iter> myMapping;

size_t k = /*whatever*/
map_iter entryPoint = myMapping.find(k);
entryPoint->second->second->first;   //log(n) + 2 constant time operations

この型はどのように書けばよいでしょうか？コピーするとイテレータが古いマップに保持されることを知っており、これを自分で処理する予定です。

4

2 に答える 2

6

マップが欲しいというあなたの質問を理解しました：key->map<key,>::iterator

したがって、これは、値としてマップ反復子を持つ構造体です。

template <
    template <class K, class V, class C, class A> class mapImpl, 
   class K, 
   class V, 
   class C=std::less<K>, 
   class A=std::allocator<std::pair<const K, V> >
>
class value_with_iterator {
public:
   typedef typename mapImpl<const K,value_with_iterator,C,A>::iterator value_type;
   value_type value;
};

上記の構造体を使用して定義されたマップ: 

typedef std::map<size_t, value_with_iterator <std::map, size_t, size_t> > map_size_t_to_itself;

いくつかの挿入方法 - キーをそれ自体にリンクするには:

map_size_t_to_itself::iterator insert(map_size_t_to_itself& mapRef, size_t value)
{
   map_size_t_to_itself::value_type v(value, map_size_t_to_itself::mapped_type());
   std::pair<map_size_t_to_itself::iterator, bool> res = mapRef.insert(v);
   if (res.second) 
     res.first->second.value = res.first;
   return res.first;
}

そして簡単なテスト：

int main() {
   map_size_t_to_itself mapObj;
   map_size_t_to_itself::iterator i1 = insert(mapObj, 1);
   map_size_t_to_itself::iterator i2 = insert(mapObj, 1);
   map_size_t_to_itself::iterator i3 = insert(mapObj, 2);

   std::cout << i1->first << ": " << i1->second.value->first << std::endl;
   std::cout << i2->first << ": " << i2->second.value->first << std::endl;
   std::cout << i3->first << ": " << i3->second.value->first << std::endl;
}

出力付き:

1: 1
1: 1
2: 2

完全なリンク: http://ideone.com/gnEhw

于 2012-10-10T14:20:48.727 に答える
2

あなたの問題を正しく理解していれば、要素をベクトルに保持し、必要な種類の間接化のために最初のベクトルにインデックスのベクトルを使用すると思います。順序付けられたアクセスも必要な場合は、最初のベクターの要素へのマップをいつでもスローできます。

于 2012-10-10T10:41:53.277 に答える