Re: [boost] [graph, python, regex, serialization, thread, multi_index, wave] Efficiency bugs

From: Joaquín Mª López Muñoz (joaquin_at_[hidden])
Date: 2005-11-30 11:50:00

David Abrahams ha escrito:

> I suggest we all review:
>
>   http://home.twcny.rr.com/hinnant/cpp_extensions/On_list_size.html#boost%20survey
>
> 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