boost :: multi_index_container with random_access和ordered_unique [英] boost::multi_index_container with random_access and ordered_unique

问题描述

我有一个问题获得 boost :: multi_index_container 使用随机访问和与orderd_unique同时。 （对不起问题的长期问题，但我想我应该使用一个例子..）

这里的例子：假设我想在一个工厂生产N个对象并且对于每个对象我有一个需求来满足（这个需求在创建多索引时是已知的）。
在我的算法中，我得到中间结果，我存储在以下类：

  class intermediate_result 
 {
 private：
 std :: vector< int>部分; //产生哪些部分
 int used_time; //生成
 
需要多长时间ValueType max_value; //多少是值
}; 
  

向量 parts 产生（它的长度是N，它是按字典顺序小于我的coresp需求矢量！） - 对于每个这样的向量，我知道used_time以及。另外，我得到一个这个生成对象的向量的值。

我有另一个约束，所以我不能生成每个对象 - 我的算法需要存储几个 intermediate_result - 在数据结构中的对象。这里使用 boost :: multi_index_container ，因为部分和 used_time 描述了一个独特的 intermediate_result （在我的数据结构中它应该是唯一的），但 max_value 是我必须考虑的另一个索引，因为我的算法总是需要具有最高 max_value 的 intermediate_result p>



所以我试着使用 boost :: multi_index_container 和 ordered_unique<> for myparts& used_time-pairand ordered_non_unique<> for my max_value c $ c> intermediate_result - 对象可以具有相同的值）。

问题是：谓词， parts& used_time-pair更小，在我的部分 - 矢量上使用 std :: lexicographical_compare ，因此非常慢对于许多 intermediate_result - 对象。
但是会有一个解决方案：我对每个对象的需求不是很高，因此我可以通过可能的部分向量中间结果> used_time 。

例如：如果我有一个需求向量（2,3,1） code>然后我需要一个数据结构存储（2 + 1）*（3 + 1）*（1 + 1）= 24 并且在每个这样的条目上不同的used_times，其必须是唯一的！ （存储最小时间不够 - 例如：如果我的附加约束是：满足给定的时间准确地为生产）

但是如何组合 random_access<> - 索引与 ordered_unique<> -index？

（ Example11 没有帮助我在这一个..）

解决方案

（我不得不使用自己的答案写代码块 - / p>

composite_key 与 used_time 和 parts （正如Kirill V. Lyadvinsky所说）基本上是我已经实现的。我想删除部分的字典比较 -vector。

假设我已经存储了needed_demand不知何故，我可以写一个简单的函数，它返回一个随机访问数据结构中正确的索引，如下：

  int get_index（intermediate_result& input_result）const 
 {
 int ret_value = 0; 
 int index_part = 1; 
 for（int i = 0; 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> 
> 
> 
> 
  

如果这是可能的，我用所有可能的零件初始化多索引 -vectors（即在我上面的评论中，我将在我的数据结构中推出24个空地图），这是找到正确的条目为给定 intermediate_result 在常量时间（在用 get_index 计算正确的索引后）？

我必须问这个，因为我不太明白，如何 random_access<> 索引与 ordered_unique<> 索引链接。

但是感谢您迄今为止的答案！

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

解决方案

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

这篇关于boost :: multi_index_container with random_access和ordered_unique的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！