Re: [Boost-users] [multi_index] range selection over composit_key problem
Hi Oliver, "Kowalke Oliver (QD IT PA AS)" ha escrito:
Hello, I want to do an range selection over an composit key but I get compiler errors like:
[...]
std::pair< idx_type::iterator, idx_type::iterator > p( idx.range( boost::make_tuple( mi::unbounded, true), boost::make_tuple( boost::lambda::_1 >= 0., true) ) );
I think there's a misunderstanding here about the usage of composite keys with range(): note that the composite key-based index sorts the elements of p according to a lexicographical order on (descending function, descending active); for instance, the values you insert in your example get sorted as follows: (1.1,false),(1,true),(0,true),(-1,true),(-1,false),(-1.1,true). Now, a fundamental limitation (or chararacteristic, if you wish) of range() is that it can only retrieve *contiguous* ranges, no matter whether the key used is simple, composite, custom or whatever . Your (syntactically incorrect) invocation to idx.range() suggests that you're trying to get the values with function>=0 and active==true, but the set of matching values is not contiguous (it is so by chance with the particular set of values you're using in oyur example, but it wouldn't be if for instance you inserted an additional (1,false) ). In order to do that you'd need to retrieve some larger range and filter out the "undesirable" elements, for example like this: // get all elements with function>=0 and arbitrary active: these do always form // a range. std::pair< idx_type::iterator, idx_type::iterator
p( idx.begin(), idx.upper_bound( boost::make_tuple(0.0) ) );
// filter out the elements with !active for ( ; p.first != p.second; ++p.first) if(p.first->active) std::cout << p.first->function << " " << std::boolalpha << p.first->active << std::endl; Hope this helps, please come back if something's still not clear. Joaquín M López Muñoz Telefónica, Investigación y Desarrollo
Hi Joaquín,
Hi Oliver, I think there's a misunderstanding here about the usage of composite keys with range(): note that the composite key-based index sorts the elements of p according to a lexicographical order on (descending function, descending active); for instance, the values you insert in your example get sorted as follows:
(1.1,false),(1,true),(0,true),(-1,true),(-1,false),(-1.1,true).
Yes - I didn't noticed this. Thank you!
// get all elements with function>=0 and arbitrary active: these do always form // a range. std::pair< idx_type::iterator, idx_type::iterator
p( idx.begin(), idx.upper_bound( boost::make_tuple(0.0) ) );
// filter out the elements with !active for ( ; p.first != p.second; ++p.first) if(p.first->active) std::cout << p.first->function << " " << std::boolalpha << p.first->active << std::endl;
Would this result in an algorithm complexity of ( n lg n) in the worst case (function >= 0 and active == false for all elements)? kind regards, Oliver
"Kowalke Oliver (QD IT PA AS)" ha escrito:
Hi Joaquín,
[...]
// get all elements with function>=0 and arbitrary active: these do always form // a range. std::pair< idx_type::iterator, idx_type::iterator
p( idx.begin(), idx.upper_bound( boost::make_tuple(0.0) ) );
// filter out the elements with !active for ( ; p.first != p.second; ++p.first) if(p.first->active) std::cout << p.first->function << " " << std::boolalpha << p.first->active << std::endl;
Would this result in an algorithm complexity of ( n lg n) in the worst case (function >= 0 and active == false for all elements)?
AFAICS in the worst case the resulting complexity would be O((log n) + n): log n to retrieve the initial range and n to traverse it. Joaquín M López Muñoz Telefónica, Investigación y Desarrollo
participants (2)
-
Joaquín Mª López Muñoz
-
Kowalke Oliver (QD IT PA AS)