🚀 go-pugleaf

khan@xraylith.wisc.edu (Mumit Khan) wrote:
>
>2 people have already mentioned that they're dismayed by the fact
>that some algorithms explicitly exclude certain containers; eg., Cay
>Hosrtmann asks why the sort algorithm does not work with lists. 

    The reasons is that the performance guarrantees would not
be met. I personally find that a bit weak: often performance
is less an issue than utility. However, there is no point
at all having separate iteratotr categories for forward, bidirectional
and random iterators otherwise, since mathematically
they're entirely equivalent.

    There is a simple and general way to fix the problem .....

>Would the following (or some more efficient rendition of thereof) be 
>something that is a candidate for an "extended" STL library?
>template <class BidirectionalIterator, class T>
>inline void __generalized_sort (
>    BidirectionalIterator first, 
>    BidirectionalIterator last,
>    bidirectional_iterator_tag,
>    T*

   but while it may be more efficient, this technique isn't
general.

   A general way is to use a bidirectional to random access
iterator range adaptor. Basically, some simple delegation
can be used to convert any iterator kind into any other.
The most useful case is converting input iterators into
forward iterators. [It took me about a day to get that
working]

   Note that such adapted iterators can be very slow:
however random acess on a singly linked list container (for example)
is possible by simply running down the whole list every time.



-- 
John Max Skaller               voice: 61-2-566-2189
81 Glebe Point Rd              fax:   61-2-660-0850
GLEBE NSW 2037                 email: maxtal@suphys.physics.oz.au
AUSTRALIA                      email: skaller@maxtal.com.au




---
[ comp.std.c++ is moderated.  Submission address: std-c++@ncar.ucar.edu.
  Contact address: std-c++-request@ncar.ucar.edu.  The moderation policy
  is summarized in http://dogbert.lbl.gov/~matt/std-c++/policy.html. ]