boost :: multi_index_container con random_access y ordered_unique

Question

Tengo un problema conseguir trabajo boost::multi_index_container con acceso aleatorio y con orderd_unique al mismo tiempo. (Lo siento por la pregunta lengthly, pero creo que debería utilizar un ejemplo ..)

A continuación, un ejemplo: Supongamos que yo quiero producir N objetos en una fábrica y para cada objeto que tengo una demanda para cumplir (esta demanda se conoce en la creación de la multi-índice). Bueno, dentro de mi algoritmo consigo resultados intermedios, que guardo en la clase siguiente:

class intermediate_result
{
private:
    std::vector<int>   parts;     // which parts are produced
    int                used_time; // how long did it take to produce

    ValueType          max_value; // how much is it worth
};

El vector de parts descibes, que los objetos se producen (su longitud es N y es más pequeño que mi lexicográfico coresp demanda del vector!) - para cada uno de estos vectores Sé que el used_time también. Además me da un valor para este vector de los objetos producidos.

Tengo otra limitación por lo que no puedo producir cada objeto - mi algoritmo necesita para almacenar varios intermediate_result-objetos en una estructura de datos. Y aquí se utiliza boost::multi_index_container, debido a que el par de parts y used_time describe un intermediate_result único (y debe ser único en mi estructura de datos) pero el max_value es otro índice que voy a tener en cuenta, porque mi algoritmo siempre necesita la intermediate_result con la más alta max_value.

Así que trató de usar boost::multi_index_container con ordered_unique<> para mis "partes y used_time-par" y ordered_non_unique<> para mi max_value (intermediate_result diferentes objetos pueden tener el mismo valor).

El problema es: el predicado, lo que se necesita para decidir qué "partes y used_time-par" es más pequeño, utiliza std::lexicographical_compare en mi parts-vector y por lo tanto es muy lento para muchos intermediate_result-objetos. Pero no habría una solución:. Mi demanda de cada objeto no es tan alto, por lo tanto, que podía almacenar en cada posible partes en vectores los resultados intermedios de forma única por su used_time

Por ejemplo: si tengo una ( 2 , 3 , 1) demanda-vector entonces necesitar una estructura de datos que almacena (2+1)*(3+1)*(1+1)=24 posibles piezas de vectores y en cada dicha entrada las diferentes used_times, que tienen que ser único! (Almacenar el menor tiempo es insuficiente - por ejemplo: si mi restricción adicional es: para encontrar un momento determinado con exactitud para la producción)

Pero ¿Cómo combino un random_access<>-índice con un índice ordered_unique<>?
( Ejemplo 11 no ayudó mí en este caso ..)

Answer 1

(tuve que usar una respuesta propia a escribir código de bloques - lo siento)

El composite_key con used_time y parts (como se sugiere Kirill V. Lyadvinsky) es básicamente lo que ya haya implementado. Quiero deshacerse del lexicográfico comparación de la parts-vectorial.

Supongamos que yo he guardado la needed_demand alguna manera entonces yo podría escribir una función simple, que devuelve el índice correcto dentro de una estructura de datos de acceso aleatorio así:

int get_index(intermediate_result &input_result) const
{
    int ret_value  = 0;
    int index_part = 1;
    for(int i=0;i<needed_demand.size();++i)
    {
        ret_value  += input_result.get_part(i) * index_part;
        index_part *= (needed_demand.get_part(i) + 1);
    }
}

Obviamente, esto puede llevarse a cabo de manera más eficiente y esto no es el único índice de pedidos posible para la demanda necesaria. Pero supongamos que existe esta función como miembro a la función de intermediate_result! ¿Es posible escribir algo como esto para evitar lexicographical_compare?

indexed_by<
  random_access< >,      
  ordered_unique< 
    composite_key< 
      intermediate_result,
      member<intermediate_result, int, &intermediate_result::used_time>,
      const_mem_fun<intermediate_result,int,&intermediate_result::get_index>
    >
  >
>

Si esto es posible y lo inicializa la multi-índice con todas las posibles parts-vectores (es decir, en mi comentario anterior me hubiera empujado a 24 mapas vacíos en mi estructura de datos), ¿esto encontrar la entrada correcta para una determinada intermediate_result en tiempo constante (después de calcular el índice correcto con get_index)?
Tengo que preguntar esto, porque no acabo de ver, cómo el índice de random_access<> está vinculada con el índice ordered_unique<> ..

Pero gracias por sus respuestas hasta el momento !!

Answer 2

Para utilizar dos índices se podría escribir lo siguiente:

indexed_by<
  random_access< >,      
  ordered_unique< 
    composite_key< 
      intermediate_result,
      member<intermediate_result, int, &intermediate_result::used_time>,
      member<intermediate_result, std::vector<int>, &intermediate_result::parts>
    >
  >
>

Se puede usar para comparar composite_key used_time al principio y vector sólo si es necesario. Además de eso, tenga en cuenta que se puede utilizar la función miembro como índice.