Re: [Boost-users] [Multi-Index] Skip-Scan "virtual" ordered-non-unique index on top of composite ordered-unique index

Dominique Devienne writes:

We have BMIs of entries with complex composite "natural-keys". [...] After recently reading http://www.sqlite.org/draft/optoverview.html#skipscan and its Skip-Scan optimization, I wondered about changing my ByNKey unique index from hashed to ordered, and thought that in theory, I could perhaps avoid the maintenance and memory cost of the additional type+name+parent indexes, since all three are subsets of the ByNKey unique index, and using a similar skip-scan strategy, which might/would still provide reasonable performance, at least better than no index at all (i.e. a full scan).

This is an interesting idea! Without making any internal change to Boost.MultiIndex indices, a decent approximation to skip-scanning can be achieved. The code pasted at the bottom provides a function skip_scan that you can use like this // scan elements with keys *,1,2,3 skip_scan<1>( c,[](const element& v){std::cout<( c,[](const element& v){std::cout< #include #include <utility> // index_sequence code stolen from // http://stackoverflow.com/questions/19783205/ // why-sizeof-t-so-slow-implement-c14-make-index-sequence-without-sizeof template struct index_sequence{using type=index_sequence;}; template<typename T> using invoke=typename T::type; template struct concate; template struct concate,index_sequence>: index_sequence{}; template<int n> struct make_index_sequence_help : concate< invoke>, invoke< make_index_sequence_help>

{}; template<> struct make_index_sequence_help<0>:index_sequence<>{}; template<> struct make_index_sequence_help<1>:index_sequence<0>{}; template<int n> using make_index_sequence=invoke; template auto key(const CompositeKey& ck,const Value& v)->decltype( boost::tuples::get<N>(ck.key_extractors())(v)) { return boost::tuples::get<N>(ck.key_extractors())(v); } template void skip_scan_helper( const Container& c,F f,index_sequence,Args&&... args) { for(auto it=c.begin(),it_end=c.end();it!=it_end;){ for(auto rng=c.equal_range( boost::make_tuple( boost::cref(key<I>(c.key_extractor(),*it))..., std::forward<Args>(args)...)); rng.first!=rng.second;++rng.first){ f(*rng.first); } it=c.upper_bound( boost::make_tuple(boost::cref(key<I>(c.key_extractor(),*it))...)); } } template< int N,typename Container,typename F, typename... Args,typename Indices=make_index_sequence<N>

void skip_scan(const Container& c,F f,Args&&... args) { skip_scan_helper<N>(c,f,Indices(),std::forward<Args>(args)...); } // testing #include #include #include #include #include <iostream> using namespace boost::multi_index; struct element { int x0,x1,x2,x3,x4; }; std::ostream& operator<<(std::ostream& os,const element& v) { os<<"("<, member, member, member, member > >

multi_t;

int main() { multi_t c={ {0,1,2,3,4}, {0,1,2,3,5}, {0,1,3,4,0}, {1,0,0,0,0}, {1,1,2,3,0}, {1,1,2,3,0}, {2,1,2,1,0}, {2,2,2,3,0}, }; skip_scan<1>( c,[](const element& v){std::cout<( c,[](const element& v){std::cout<( c,[](const element& v){std::cout<