2

我在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，并且它在字典上比我的 coresp 需求向量小！） - 对于每个这样的向量，我也知道 used_time。此外，我得到了这个生成对象向量的值。

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

所以我尝试将boost::multi_index_containerwithordered_unique<>用于我的“parts&used_time-pair”和ordered_non_unique<>我的max_value（不同intermediate_result的对象可能具有相同的值）。

问题是：决定哪个“parts&used_time-pair”更小所需的谓词std::lexicographical_compare在 my -vector 上使用，因此对于许多-objectsparts来说非常慢。intermediate_result但是会有一个解决方案：我对每个对象的需求不是那么高，因此我可以在每个可能的部分向量上存储中间结果唯一的used_time.

例如：如果我有一个需求向量( 2 , 3 , 1)，那么我需要一个数据结构来存储(2+1)*(3+1)*(1+1)=24可能的部分向量，并且在每个这样的条目上都有不同的 used_times，它们必须是唯一的！（存储最小的时间是不够的——例如：如果我的额外限制是：满足给定的生产时间）

但是如何将random_access<>-index 与ordered_unique<>-index 结合使用？
（Example11在这方面没有帮助我..）

4

2 回答 2

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仅在必要时使用。除此之外，请记住，您可以使用成员函数作为索引。

于 2009-11-09T11:26:48.010 回答
0

（我不得不使用自己的答案来编写代码块 - 抱歉！）

composite_keywith used_timeand （正如 Kirill V. Lyadvinsky 建议的parts那样）基本上是我已经实现的。我想摆脱parts-vector 的字典比较。

假设我已经以某种方式存储了所需的需求，那么我可以编写一个简单的函数，它在这样的随机访问数据结构中返回正确的索引： 

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

如果这是可能的，并且我用所有可能的 -vectors 初始化了多索引parts（即在我上面的评论中，我会在我的数据结构中推送 24 个空映射），这是否会intermediate_result在恒定时间内找到给定的正确条目（在用 ) 计算正确的索引之后get_index？
我不得不问这个，因为我不太清楚，random_access<>索引是如何与索引链接的ordered_unique<>。。

但是谢谢你到目前为止的回答！！

于 2009-11-09T13:10:31.733 回答