boost::multi_index_container with random_access and ordered_unique

Question

Hi,

I have a problem getting boost::multi_index_container work with random-access and with orderd_unique at the same time. (I'm sorry for the lengthly question, but I think I should use an example..)

Here an example: Suppose I want to produce N objects in a factory and for each object I have a demand to fulfill (this demand is known at creation of the multi-index). Well, within my algorithm I get intermediate results, which I store in the following class:

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

The vector parts descibes, which objects are produced (its length is N and it is lexicographically smaller then my coresp demand-vector!) - for each such vector I know the used_time as well. Additionally I get a value for this vector of produced objects.

I got another constraint so that I can't produce every object - my algorithm needs to store several intermediate_result-objects in a data-structure. And here boost::multi_index_container is used, because the pair of parts and used_time describes a unique intermediate_result (and it should be unique in my data-structure) but the max_value is another index I'll have to consider, because my algorithm always needs the intermediate_result with the highest max_value.

So I tried to use boost::multi_index_container with ordered_unique<> for my "parts&used_time-pair" and ordered_non_unique<> for my max_value (different intermediate_result-objects may have the same value).

The problem is: the predicate, which is needed to decide which "parts&used_time-pair" is smaller, uses std::lexicographical_compare on my parts-vector and hence is very slow for many intermediate_result-objects. But there would be a solution: my demand for each object isn't that high, therefore I could store on each possible parts-vector the intermediate results uniquely by its used_time.

For example: if I have a demand-vector ( 2 , 3 , 1) then I need a data-structure which stores (2+1)*(3+1)*(1+1)=24 possible parts-vectors and on each such entry the different used_times, which have to be unique! (storing the smallest time is insufficient - for example: if my additional constraint is: to meet a given time exactly for production)

But how do I combine a random_access<>-index with an ordered_unique<>-index?
(Example11 didn't help me on this one..)

Answer 1

To use two indices you could write the following:

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

You could use composite_key for comparing used_time at first and vector only if necessary. Besides that, keep in mind that you could use member function as index.

Answer 2

Hi again. (I had to use an own answer to write code-blocks - sorry!)

The composite_key with used_time and parts (as Kirill V. Lyadvinsky suggested) is basically what I've already implemented. I want to get rid of the lexicographical compare of the parts-vector.

Suppose I've stored the needed_demand somehow then I could write a simple function, which returns the correct index within a random-access data-structure like that:

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

Obviously this can be implemented more efficiently and this is not the only possible index ordering for the needed demand. But let's suppose this function exists as a member-function of intermediate_result! Is it possible to write something like this to prevent 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>
    >
  >
>

If this is possible and I initialized the multi-index with all possible parts-vectors (i.e. in my comment above I would've pushed 24 empty maps in my data-structure), does this find the right entry for a given intermediate_result in constant time (after computing the correct index with get_index) ?
I have to ask this, because I don't quite see, how the random_access<> index is linked with the ordered_unique<> index..

But thank you for your answers so far!!