std :: multimap obteniendo dos rangos

Estoy usando un C++ std::multimap y tengo que repetir dos claves diferentes. ¿Hay una forma eficiente de hacer esto que no sea la creación de dos rangos y el bucle sobre esos rangos por separado?std :: multimap obteniendo dos rangos

Esta es la forma en que estoy haciendo ahora:

std::pair<std::multimap<String, Object*>::iterator,std::multimap<String, Object*>::iterator> range; 
std::pair<std::multimap<String, Object*>::iterator,std::multimap<String, Object*>::iterator> range2; 

// get the range of String key 
range = multimap.equal_range(key1); 
range2 = multimap.equal_range(key2); 

for (std::multimap<String, Object*>::iterator it = range.first; it != range.second; ++it) 
{ 
    ... 
} 
for (std::multimap<String, Object*>::iterator it2 = range2.first; it2 != range2.second; ++it2) 
{ 
    ... 
}

Fuente

2011-09-07 Kaiser Wilhelm

¿por qué crees que no es eficiente? –

Esta es la primera vez que uso multimap, así que no estoy muy familiarizado con ellos. Haré mucho trabajo en esos bucles y me pregunto si hay otra operación en la que puedas obtener dos rangos al mismo tiempo o algo así. –

¿Puedes dar un ejemplo de teclas donde las teclas se superponen, pero no se igualan? Tal vez mi cerebro está empapado, pero parece que un simple control de igualdad en las teclas lo haría. Tiene más sentido para mí si tienes límites inferiores y superiores separados para cada consulta. –

El código que se inició con el más sencillo.

Si realmente desea iterar en dos rangos en el mismo bucle, puede crear un iterador personalizado que tome dos rangos de iteradores, iterar sobre el primero hasta que termine y luego cambie al segundo. Probablemente esto sea más problemático de lo que vale, ya que necesitaría implementar todos los miembros del iterador usted mismo.

Edit: Estaba pensando demasiado esto; es fácil simplemente modificar los dos bucles en uno solo.

for (std::multimap<String, Object*>::iterator it = range.first; it != range2.second; ++it) 
{ 
    if (it == range.second) 
    { 
     it = range2.first; 
     if (it == range2.second) 
      break; 
    } 
    ... 
}

Fuente

2011-09-07 15:27:06

Pensé en esto también. Sin embargo, ¿estas dos claves deben estar una al lado de la otra para que esto funcione? Por ejemplo, si tengo 3 teclas y quiero repetir el 1er y 3er, ¿incluye el 2do con ellas? ¿O esas declaraciones if corrigen eso? –

@Kaiser, las sentencias 'if' manejan la transición del primer rango al segundo. Incluso pueden estar fuera de servicio. Lo único que * no pueden * hacer es cruzarse; si 'range2' incluye' range.second' entonces obtendrá un ciclo infinito. –

Ahh ya veo. Mi range2 es estático y range1 siempre será diferente. Nunca deberían cruzarse correctamente? Dado que multimap lo ordena después de la inserción? –

Boost hace esto, por supuesto. Usando Boost.Range y su función join obtendrá lo que desea. Vea Boost Range Library: Traversing Two Ranges Sequentially para más detalles.

Fuente

2011-09-07 15:29:56

Gracias, Boost parece realmente poderoso Desafortunadamente, mi compañía es vieja y odia las cosas nuevas ... supongo que tendrán que conformarse con la ineficiencia –

esta vez no se trata de eficiencia, se trata de conveniencia –

Si tiene acceso a C++ - 11 (Visual Studio 10+, gcc-4.5 +) y está autorizado para utilizarla auto es una verdadera joya:

// get the range of String key 
auto range = multimap.equal_range(key1); 
auto range2 = multimap.equal_range(key2); 

for (auto it = range.first; it != range.second; ++it) 
{ 
    ... 
} 
for (auto it2 = range2.first; it2 != range2.second; ++it2) 
{ 
    ... 
}

De todos modos, me acaba de probar las llaves y solo haga el segundo ciclo si key2! = key1. Comprobar los iteradores cada vez en un ciclo tiene algún costo.

Una std :: set_difference del primer rango del segundo podría simplificar el código. ¿Tal vez std :: set_union los dos rangos e inserte a través de back_inserter en un conjunto para que solo obtenga una copia?

Algunos experimentos pueden estar en orden. No olvides poner tu primera suposición en la mezcla. Puede sorprenderte por estar bien en términos de velocidad. A menos que los rangos sean generalmente muy largos y/o el funcionamiento del bucle sea costoso, puede que no valga la pena el dolor de cabeza de una contabilidad adicional.

Fuente

2011-09-07 19:38:57 emsr

std :: multimap obteniendo dos rangos

Respuesta

Cuestiones relacionadas