abc@abc.com ("Florin") writes:

> Hello,
>
> I was wondering if anybody knows why the stlport implementation for rotate
> has three versions depending on the type of the iterator and why the
> implementation for _RandomAccesIter doesn't use swap? The Josuttis book says
> that rotate is implemented in terms of swap

It said that prematurely; see
http://anubis.dkuug.dk/jtc1/sc22/wg21/docs/lwg-active.html#226.

> and this is what I expected to do but instead I get calls to the
> copy constructor (the objects are copied around without using swap).

There's a lot more to this issue than there might at first appear to
be (like e.g. whether it is supposed to use std::swap or find the
version of swap in your namespace).

--
Dave Abrahams
Boost Consulting
www.boost-consulting.com

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

On Fri, 21 Feb 2003 22:12:15 +0000 (UTC), abc@abc.com ("Florin") wrote:

> I was wondering if anybody knows why the stlport implementation for rotate
> has three versions depending on the type of the iterator and why the
> implementation for _RandomAccesIter doesn't use swap? The Josuttis book says
> that rotate is implemented in terms of swap and this is what I expected to
> do but instead I get calls to the copy constructor (the objects are copied
> around without using swap).

The standard requires that no more than N swaps be performed.  Since the
random version does no swaps, it complies.

Consider the following simple rotates of length one.

template <class Fiter>
void rotateLeftOne (Fiter first, Fiter past) {
   if (first != past)
      for (Fiter pred(first ++); first != past; pred = first ++)
         swap(*pred, *first);  // iter_swap(pred, first) ?
   }

template <class Fiter>
rotateLeftOne (Fiter first, Fiter past) {
   if (first != past) {
      typename iterator_traits<Fiter>::value_type tmp(*first);
      for (Fiter pred(first ++); first != past; pred = first ++)
         *pred = *first;
      *pred = tmp;
      }
   }

If swap is the same as three assignments, the second is much faster.
If swap is faster than assignment, the first is faster.  It is a QoI
choice of which to implement.

Some testing that I did indicated that the cute gcd random version was
slower for fundamental types where swap is three assignments.  The swap
version has better locality of reference and cache changes all of the
expectations.  YMMV.

John

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

Hello,

I was wondering if anybody knows why the stlport implementation for rotate
has three versions depending on the type of the iterator and why the
implementation for _RandomAccesIter doesn't use swap? The Josuttis book says
that rotate is implemented in terms of swap and this is what I expected to
do but instead I get calls to the copy constructor (the objects are copied
around without using swap).

Thanks,

Florin.



---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]