boost::multi_index_container с random_access и ordered_unique

Question

У меня проблема с получением boost::multi_index_container работайте с произвольным доступом и с orderd_unique одновременно.(Прошу прощения за длинный вопрос, но я думаю, мне следует привести пример ..)

Вот пример:Предположим, я хочу создать N объектов на фабрике, и для каждого объекта у меня есть требование, которое я должен выполнить (это требование известно при создании мультииндекса).Что ж, в рамках моего алгоритма я получаю промежуточные результаты, которые я сохраняю в следующем классе:

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

Вектор parts описывает, какие объекты создаются (его длина равна N и лексикографически меньше, чем у моего основного вектора спроса!) - для каждого такого вектора я также знаю used_time.Кроме того, я получаю значение для этого вектора созданных объектов.

У меня есть еще одно ограничение, так что я не могу создать каждый объект - мой алгоритм должен хранить несколько intermediate_result-объекты в структуре данных.И здесь boost::multi_index_container используется, поскольку пара parts и used_time описывает уникальный intermediate_result (и это должно быть уникальным в моей структуре данных), но max_value это еще один индекс, который я должен буду рассмотреть, потому что моему алгоритму всегда нужен intermediate_result с самым высоким max_value.

Поэтому я попытался использовать boost::multi_index_container с ordered_unique<> для моей "пары частей и использованного времени" и ordered_non_unique<> для моего max_value (разные intermediate_result-объекты могут иметь одинаковое значение).

Проблема в том, что:предикат, который необходим, чтобы решить, какие "части иused_time-pair" меньше, использует std::lexicographical_compare на моем parts-вектор и, следовательно, очень медленный для многих intermediate_result-объекты.Но решение было бы найдено:мой спрос на каждый объект не так уж высок, поэтому я мог бы хранить на каждом возможный parts-векторизировать промежуточные результаты однозначно по их used_time.

Например:если у меня есть вектор спроса ( 2 , 3 , 1) тогда мне нужна структура данных, которая хранит (2+1)*(3+1)*(1+1)=24 возможные части-векторы и для каждой такой записи разные used_times, которые должны быть уникальными!(сохранение наименьшего времени недостаточно - например:если моим дополнительным ограничением является:точно уложиться в заданное время для производства)

Но как мне совместить random_access<>-индекс с ordered_unique<>-индекс?
(Пример11 в этом деле мне это не помогло ..)

Answer 1

(Мне пришлось использовать собственный ответ для написания блоков кода - извините!)

Тот Самый composite_key с used_time и parts (в роли Кирилла В.Предложил Лядвинский) - это в основном то, что я уже реализовал.Я хочу избавиться от лексикографического сравнения parts-вектор.

Предположим, я каким-то образом сохранил needed_demand, тогда я мог бы написать простую функцию, которая возвращает правильный индекс в структуре данных с произвольным доступом, подобной этой:

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

Очевидно, что это может быть реализовано более эффективно, и это не единственный возможный порядок упорядочения индексов для необходимого спроса.Но давайте предположим, что эта функция существует как функция-член intermediate_result!Можно ли написать что-то подобное, чтобы предотвратить 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>
    >
  >
>

Если это возможно, и я инициализировал мультииндекс со всеми возможными parts-векторы (т.е.в моем комментарии выше я бы поместил 24 пустых карты в мою структуру данных), находит ли это правильную запись для данного intermediate_result в постоянное время (после вычисления правильного индекса с помощью get_index) ?
Я должен спросить об этом, потому что я не совсем понимаю, как random_access<> индекс связан с ordered_unique<> Указатель..

Но пока спасибо вам за ваши ответы!!

Answer 2

Чтобы использовать два индекса, вы можете написать следующее:

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

Вы могли бы использовать composite_key для сравнения used_time сначала и vector только в случае необходимости.Кроме того, имейте в виду, что вы можете использовать функцию-член в качестве индекса.