Re: Recommendation for moving / shifting vector members?

[Oleg Endo <oleg dot endo at t-online dot de>]

On Thu, 2014-07-17 at 15:37 -0700, Linda A. Walsh wrote:
> Oleg Endo wrote:
> > The generic version is probably std::rotate
> > http://en.cppreference.com/w/cpp/algorithm/rotate
> ---
> Ahhh... with random shuffling and  partition in the C++
> book... hmmm...  not the first place I would have thought.
> 
> I would have thought rotate woudl be treated like shift.
> (i.e. both supported or not).
> 
>   It's not real clear why rotate is provided but not shift,
> other than the "organizational hint" being that rotate can't
> (or doesn't) use movmem like primitives, but by touching
> each element via the algorithm along the lines of random
> shuffling or partitioning(?).
> 
> Isn't it just a matter of moving something off one end vs.
> to the other end of the list?

Yes... for lists that's the case.  It can be done with
http://en.cppreference.com/w/cpp/container/list/splice

However, since a vector has to do its contiguous memory layout thing,
the only option is to move the elements around one by one or something
like that.  I've just quickly tried compiling:

void rotate_test (std::vector<int>& v)
{
  std::rotate (v.begin(), v.begin() + 1, v.end());
}

with -O2 and in fact I do see a memmove in the output code.  However,
there's also lots of other stuff around it (e.g. integer divisions ...),
but my guess is that most of the code would just fall through to the
memmove in this case.  You could also check the implementation of
std::rotate in the libstdc++ source to see what it does exactly.

> > 
> >> I'm not sure if memmove on the members is supported or not?
> >> Are they supposed to be contiguous in memory and memmove is
> >> 'fine' -- and I'm overthinking this, or is there better
> >> solution?
> > 
> > The elements stored in a vector are in contiguous memory.  That's one
> > key property of the container.  See also the description in
> > http://en.cppreference.com/w/cpp/container/vector
> ---
> I thought I remember reading that, but wasn't sure if locations
> (beginning of 'extra capacity' or such) in the vector were stored
> somewhere, such that my moving the memory directly might not corrupt
> the container.

It should be OK to modify the memory contents of the elements between
begin () and end ().  Assuming that there's something behind end () in
the vector's element array is not a good idea, though.

> 
> Good to know.  In my use case I'd hoped to use
> memmove if shift wasn't available. Though the is_trivial
> has me a bit worried now that you mention it, since
> a single data point is actually a
> struct{ Timespec x; valarray<uint64_t> D;}.
> Not sure if the valarray is considered trivial ..
> am *guessing* yes, but will have to try it out.

Before doing that, I'd recommend measuring the performance of
std::rotate first.  If you have lots of elements that need to be rotated
std::list and splicing might be the better alternative.  If you don't
like the free store allocations of std::list you can use a custom block
allocator for the list, e.g. http://warp.povusers.org/FSBAllocator/

> > If the std::vector class itself is a custom made specialization, things
> > could be a bit difficult to handle in a generic way from outside the std
> > lib implementation.
> ---
> 	Understandable if an object requires non trivial initialization,
> but even a valarray of 'ints' requires a length and could be
> viewed as non-trivial in that case.  Is there a better way of
> knowing if something is trivial than writing a test program?

Not that I know of.

Cheers,
Oleg