Boost logo

Boost :

From: Aleksey Gurtovoy (agurtovoy_at_[hidden])
Date: 2002-07-19 19:31:04


Giovanni Bajo wrote:
> > That's not a bug - 'list' does not support 'push_back',
> > because it's not possible to implement it in the way
> > that would satisfy the algorithm's
> > complexity requirements - see
> > http://www.mywikinet.com/mpl/ref/Reference/push_back.html and
> > http://www.mywikinet.com/mpl/ref/Reference/list.html.
>
> The problem is that this breaks the orthogonality between
> algorithms and containers. That is, I can't write an algorithm
> that works with both vectors and lists (or I have to specialize it
> so that it uses different codepaths).

It is a problem. Actually, you can, using 'insert', but it would be
inefficient on one or another type of sequence. An interesting thing is that
we have the same situation in STL (there is no unified efficient way to
insert something into container), but it's not a problem there because most
of STL algorithms work "in place" by modifying the sequence elements, and in
compile-time world we need to put the results somewhere else - i.e. push
into a new sequence. Anyway, I guess a right solution for this is to declare
one of the sequence insert operations mandatory for any Extensible Sequence;
'push_front' seems to be the only reasonable candidate for this, since it's
implementable for pretty much everything. I'll think a little bit more about
it, but if you need a uniform way to copy a sequence right away :), consider
'copy_backward' + 'push_front' to be it.

Thank you for your comments,
Aleksey


Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk