Boost logo

Boost :

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:
> 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;
    iterator first0=x.begin(),last0=x.end();
    iterator first1=y.begin(),last1=y.end();
      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

Boost list run by bdawes at, gregod at, cpdaniel at, john at