David Abrahams ha escrito:
I suggest we all review:
http://home.twcny.rr.com/hinnant/cpp_extensions/On_list_size.html#boost%20su...
It reveals efficiency bugs in
[...]
boost/multi_index/detail/seq_index_ops.hpp
template <typename SequencedIndex,typename Compare> void sequenced_index_merge(SequencedIndex& x,SequencedIndex& y,Compare comp) { typedef typename SequencedIndex::iterator iterator; if(x!=y){ iterator first0=x.begin(),last0=x.end(); iterator first1=y.begin(),last1=y.end(); while(first0!=last0&&first1!=last1){ if(comp(*first1,*first0))x.splice(first0,y,first1++); else ++first0; } x.splice(last0,y,first1,last1); // Howard's comment: distance(first1,last1) can easily be // computed by client if list::size is O(1). } } The splice() referred to in the snippet is not std::list::splice but the homonym member function of sequenced indices, which is acknowledgedly O(N) in the unfavorable cases and cannot be made O(1), not even with Howard's proposal --basically, ranges of elements cannot be transferred in one fell swoop between different multi_index_containers as each element must be validated against unique-constrained indices. So I wouldn't mark this as a bug nor as an opportunity for improvement. Joaquín M López Muñoz Telefónica, Investigaición y Desarrollo