1

For learning purposes, I'm creating a container, based from an array with map-like functionality. Every time I insert a key, I want to keep the array ordered. I have already implemented functions to find where the key should go in the arrays index, the only issue I have currently is efficiently shifting the array elements.

I have a simple loop to do this:

for (size_t i = mSize; i > n; i--)
{
    mCont[i] = mCont[i - 1];
}

However, I'd like to possibly use something such as memmove to be able to do this quicker -but I'm not sure how to use it- when the container grows in size.

Thanks for your time.

Peter Cordes
  • 328,167
  • 45
  • 605
  • 847
BoyUnderTheMoon
  • 741
  • 1
  • 11
  • 27
  • 1
    To do it quicker you should use move semantics – Slava Nov 10 '15 at 21:01
  • 3
    `memmove` is a C function. Thus is only useful for POD types. You should use `std::copy()` (or if you move semantics `std::move`) which will use the most efficient method for the type being moved (ie if the most efficient method is memmove it will use it). – Martin York Nov 10 '15 at 21:03
  • This is why memmove cannot be used with non-POD types: http://stackoverflow.com/questions/12135769/will-memcpy-or-memmove-cause-problems-copying-classes – bolov Nov 10 '15 at 21:04
  • 1
    @LokiAstari: Since he's copying to the right I think [`std::copy_backward`](http://en.cppreference.com/w/cpp/algorithm/copy_backward) makes more sense. – Blastfurnace Nov 10 '15 at 21:05
  • @Blastfurnace: Sure. – Martin York Nov 10 '15 at 21:05
  • 2
    Just because there's a standard function for it doesn't mean it will be *much* more efficient. All the memory to the right of the insert position has to be read and rewritten, which is is going to take `O(n)` time no matter what you do. Lowering the constant factor helps, but it still won't make such a container usable (compared to a tree) for very large `n`. However, you're right that if `mCont` is an array of bytes, a compiler might emit code that operates one byte at a time, in which case `memmove` might beat it by a factor of ~16 or even ~32 on an x86 CPU (if it's in L1 cache). – Peter Cordes Nov 10 '15 at 21:17
  • consider using a tree structure for your container, then insertion does not involve a bunch of copying – M.M Nov 10 '15 at 21:25

1 Answers1

6

You can use std::move_backward :

std::move_backward( std::next( std::begin( mCont ), n ), 
                    std::next( std::begin( mCont ), mSize - 1 ),
                    std::next( std::begin( mCont ), mSize ) );
Slava
  • 43,454
  • 1
  • 47
  • 90