boost :: multi_index_container com random_access e ordered_unique

Question

Eu tenho um problema começar o trabalho boost::multi_index_container com acesso aleatório e com orderd_unique ao mesmo tempo. (Eu sinto muito pela questão lengthly, mas eu acho que eu deveria usar um exemplo ..)

Aqui um exemplo: Suponha que eu queira produzir N objetos em uma fábrica e para cada objeto que eu tenho uma exigência para cumprir (a essa demanda é conhecida no momento da criação do multi-index). Bem, dentro do meu algoritmo eu obter resultados intermediários, que eu armazenados na seguinte classe:

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

Os descibes parts vetoriais, que os objetos são produzidos (seu comprimento é N e é lexicographically menor, então o meu coresp demanda do vetor!) - para cada um desses vector eu sei o used_time também. Além disso eu recebo um valor para este vetor de objetos produzidos.

Eu tenho outro constrangimento para que eu não pode produzir todos os objetos - meu algoritmo necessidades para armazenar vários intermediate_result-objetos em uma estrutura de dados. E aqui boost::multi_index_container é usado, porque o par de parts e used_time descreve um intermediate_result único (e deve ser único na minha data-estrutura), mas o max_value é outro índice que vou ter que considerar, porque o meu algoritmo precisa sempre o intermediate_result com a maior max_value.

Então, eu tentei usar boost::multi_index_container com ordered_unique<> para as minhas "partes e used_time-pair" e ordered_non_unique<> para o meu max_value (diferentes intermediate_result-objetos podem ter o mesmo valor).

O problema é: o predicado, que é necessário para decidir qual "peças e used_time-pair" é menor, usa std::lexicographical_compare no meu parts-vector e, portanto, é muito lento para muitos intermediate_result-objetos. Mas não haveria uma solução:. A minha demanda de cada objeto não é tão alta, portanto, eu poderia armazenar em cada possível peças-vetor os resultados intermediários exclusivamente por seu used_time

Por exemplo: se eu tiver uma ( 2 , 3 , 1) demanda do vetor, então eu preciso de uma estrutura de dados que armazena (2+1)*(3+1)*(1+1)=24 possíveis peças-vetores e em cada tal entrada diferentes used_times, que têm de ser único! (Armazenando o menor tempo é insuficiente - por exemplo: se a minha restrição adicional é: para atender um determinado momento exatamente para a produção)

Mas como posso combinar um random_access<>-index com um ordered_unique<>-index?
( Example11 não ajudou me sobre esta ..)

Answer 1

(Eu tive que usar uma resposta própria para escrever o código-blocos - sorry)

O composite_key com used_time e parts (como Kirill V. Lyadvinsky sugerido) é basicamente o que eu já implementadas. Eu quero me livrar do lexicographical comparar do parts-vector.

Suponha que eu tenha armazenado o needed_demand de alguma forma, então eu poderia escrever uma função simples, que retorna o índice correto dentro de um random-access data-estrutura assim:

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, isso pode ser implementado de forma mais eficiente e este não é o único possível ordenação de índice para a demanda necessária. Mas vamos supor que essa função existe como uma função de membro da intermediate_result! É possível escrever algo como isto 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>
    >
  >
>

Se isto é possível e eu inicializado o multi-índice com todas as parts-vetores possíveis (ou seja, no meu comentário acima Eu teria empurrado 24 mapas vazios na minha data-estrutura), isso encontrar a entrada certa para um determinado intermediate_result em tempo constante (após calcular o índice correto com get_index)?
Eu tenho que perguntar isso, porque eu não vejo, como o índice random_access<> está relacionada com o índice ordered_unique<> ..

Mas obrigado por suas respostas até agora !!

Answer 2

Para usar dois índices você poderia escrever o seguinte:

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

Você pode usar composite_key para comparar used_time, em primeira e vector somente se necessário. Além disso, tenha em mente que você pode usar a função de membro como índice.