What is the most effective way to move items within a vector?

Question

I've seen some special cases where std::rotate could be used or a combination with one of the search algorithms but generally: when one has a vector of N items and wants to code function like:

void move( int from, int count, int to, std::vector<int>& numbers );

I've been thinking about creation of a new vector + std::copy or combination of insert/erase but I can't say I ended up with some nice and elegant solution.

Answer 1

It's always important to profile before jumping to any conclusions. The contiguity of vector's data memory may offer significant caching benefits that node-based containers don't. So, perhaps you could give the direct approach a try:

void move_range(size_t start, size_t length, size_t dst, std::vector<T> & v)
{
  const size_t final_dst = dst > start ? dst - length : dst;

  std::vector<T> tmp(v.begin() + start, v.begin() + start + length);
  v.erase(v.begin() + start, v.begin() + start + length);
  v.insert(v.begin() + final_dst, tmp.begin(), tmp.end());
}

In C++11, you'd wrap the iterators in the first and third line into std::make_move_iterator.

(The requirement is that dst not lie within [start, start + length), or otherwise the problem is not well-defined.)

Answer 2

Depending on the size of the vector and the ranges involved, this might be less expensive than performing copy/erase/insert.

template <typename T>
void move_range(size_t start, size_t length, size_t dst, std::vector<T> & v)
{
    typename std::vector<T>::iterator first, middle, last;
    if (start < dst)
    {
        first  = v.begin() + start;
        middle = first + length;
        last   = v.begin() + dst;
    }
    else
    {
        first  = v.begin() + dst;
        middle = v.begin() + start;
        last   = middle + length;
    }
    std::rotate(first, middle, last);
}

(This assumes the ranges are valid and they don't overlap.)