librerias - vector stl c++ ejemplos

std:: mapa de iteradores a sí mismo

Question

Mi objetivo es asignar elementos de un tipo a otros elementos del mismo tipo. Supongamos que son size_t por simplicidad.

std::map<size_t, size_t> myMapping;

Esto lo haría, pero si quiero seguir un montón de tales enlaces (todos son el mismo mapa), cada paso es una búsqueda de log(n) .

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

Quiero hacer uso del hecho de que los iteradores de mapas siguen siendo válidos y tienen un mapa que asigna size_t a los iteradores en sí mismo.

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

¿Cómo escribiría este tipo? Sé que copiar mantendría iteradores en el mapa antiguo y planearé encargarme de esto yo mismo.

Answer 1

Si entendí tu problema correctamente, creo que mantendría mis elementos en un vector y usaría un vector de índices en el primer vector para el tipo de direccionamiento indirecto que deseas. Si también necesita acceso ordenado, siempre puede incluir un mapa en los elementos del primer vector.

Answer 2

Entiendo tu pregunta que quieres hacer un mapa: key->map<key,>::iterator

Entonces, aquí está, una estructura con un iterador de mapa como valor:

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

Mapa definido con el uso de la estructura anterior:

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

Algunos métodos de inserción: para vincular la clave consigo mismo:

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

Y prueba simple:

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

con SALIDA:

1: 1
1: 1
2: 2

Enlace completo: http://ideone.com/gnEhw