Manel Manel - 9 days ago 6
Python Question

Shift array elements in C++ without loop

Is there a way to shift array elements in C++ without using any loop like the below Python code which shifts the elements of the list just by manipulating list indices

def rotate(lst, n):
n = n % len(lst)
return lst[n:] + lst[:n]

> rotate([1,2,3,4,5], 1) # rotate forward
[2, 3, 4, 5, 1]

Answer

C++ standard algorithms also work with arrays, so you can just use std::rotate or std::rotate_copy.

The functions' interfaces are a bit more complex than rotation in your Python example, though. You have to provide, as a second argument, an iterator to the element which will become the first element in the resulting array.

For an array { 1, 2, 3, 4, 5 } and a forward rotation by one element, that would be the second element (the "2"). You get an iterator to that element by adding 1 to an iterator to the array's first element, for example array.begin() + 1, assuming that you use std::array, or array + 1 if it's a raw array.

#include <iostream>
#include <algorithm>
#include <array>

int main()
{
    std::array<int, 5> array = { 1, 2, 3, 4, 5 };
    std::rotate(
        array.begin(),
        array.begin() + 1,
        array.end()
    );    

    for (auto&& element : array)
    {
        std::cout << element << "\n";
    }
}

If you want an interface like in your Python code, then you can wrap std::rotate in a function of your own and provide an int parameter. This is also a nice opportunity to make the whole thing more reusable by creating a generic function which can be used with any suitable container:

#include <iostream>
#include <algorithm>
#include <array>
#include <vector>
#include <list>

template <class Container>
void rotate(Container& container, int n)
{
    using std::begin;
    using std::end;

    auto new_begin = begin(container);
    std::advance(new_begin, n);

    std::rotate(
        begin(container),
        new_begin,
        end(container)
    );    
}

int main()
{
    std::array<int, 5> array = { 1, 2, 3, 4, 5 };
    rotate(array, 1);

    std::vector<int> vector = { 1, 2, 3, 4, 5 };
    rotate(vector, 3);

    std::list<int> list = { 1, 2, 3, 4, 5 };
    rotate(list, 2);

    int raw_array[] = { 1, 2, 3, 4, 5 };
    rotate(raw_array, 3);

    // test output goes here...
}

Note how std::begin and std::end make sure that raw arrays (with their begin + N syntax) and container classes (with their c.begin() + N syntax) are both supported, and std::advance makes the function work for containers with non-random-access iterators like std::list (where you must increment iterators repeatedly to advance them by more than one element).


By the way, if you want to support n arguments greater than or equal to the container's size, then you can use the C++17 function std::size or just create your own. And perhaps use assert to catch accidental negative arguments:

assert(n >= 0);
using std::size;
n = n % size(container);
Comments