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