Rotate elements in a vector and how to return a vector

Question

I have to rotate all the elements in a vector to the left one. So, for instance, the elements {1,2,3} should rotate to {2,3,1}.

I'm researching how to do it, and I saw the rotate() function, but I don't think that will work given my code. And then I saw a for loop that could do it, but I'm not sure how to translate that into a return statement. (i tried to adjust it and failed)

This is what I have so far, but it is very wrong (i haven't gotten a single result that hasn't ended in an error yet)

Edit: The vector size I have to deal with is just three, so it doesn't need to account for any sized vector

#include <vector>
using namespace std;

vector<int> rotate(const vector<int>& v)
{
   // PUT CODE BELOW THIS LINE. DON'T CHANGE ANYTHING ABOVE.
   vector<int> result;
   int size = 3;
   for (auto i = 0; i < size - 1; ++i)
   {
       v.at(i) = v.at(i + 1);
       result.at(i) = v.at(i);
   }
   return result;
   // PUT CODE ABOVE THIS LINE. DON'T CHANGE ANYTHING BELOW.
}

Could someone give me a few pointers?

Answer 1

Vector type allowing subrange of vector/element aligned storage type to be rotated with rotated<pos,count,dst = pos,size = N>(amount):

#include <array>
#include <bit>
#include <algorithm>

template<typename T>
concept scalar = std::integral<T> || std::floating_point<T>;
namespace vec {
namespace storage {
   template<scalar T, size_t N, size_t POW2 = std::bit_ceil<size_t>(N)>
   using vector_aligned __attribute__((vector_size(POW2 * sizeof(T)))) = T;

   template<scalar T, size_t N>
   using element_aligned = std::array<T,N>;
};

template<scalar T, size_t N, size_t POW2 = std::bit_ceil<size_t>(N)>
struct type
{
    using storage_type = std::conditional_t<N==POW2, storage::vector_aligned<T,N>, storage::element_aligned<T,N>>;
    union {
        storage_type data;
    };
    T& operator[](size_t i) { return data[i]; }

    template<size_t pos, size_t count>
    type<T,N>& rotate(ssize_t i = 1)
    {
        std::rotate(&data[pos], &data[pos + (pos + (i % count))], &data[pos + count] );
        return (*this);
    }

    template<size_t pos, size_t count, size_t dst = pos, size_t size = N>
    type<T,size> rotated(ssize_t i = 1)
    {
        type<T,size> tmp = {};
        std::rotate_copy(&data[pos], &data[pos + (pos + (i % count))], &data[pos + count], &tmp[pos]);
        return tmp;
    }
};

};

Example:

#include <cstdlib>
#include <cstdio>
#include "vec.hpp"

int main(int argc, char** argv)
{
    vec::type<float, 7> v = {1,2,3,4,5,6,7};
    vec::type<float, 4> u = {1,2,3,4};
    /* rotate 3 elements at pos 1 to the left by 4 */
    printf("vector_aligned: %zu/%zu\n", alignof(u), sizeof(u));
    printf("[%f %f %f %f]\n", u[0], u[1], u[2], u[3]);
    u = u.rotated<1,3>(-4);
    printf("[%f %f %f %f]\n", u[0], u[1], u[2], u[3]);
    /* rotate 3 elements at pos 1 to the right by 4 and place at 0 */
    printf("element_aligned: %zu/%zu\n", alignof(v), sizeof(v));
    printf("[%f %f %f %f %f %f %f]\n", v[0], v[1], v[2], v[3], v[4], v[5], v[6]);
    v = v.rotated<1,3,0>(4);
    printf("[%f %f %f %f %f %f %f]\n", v[0], v[1], v[2], v[3], v[4], v[5], v[6]);
}

Output:

vector_aligned: 16/16
[1.000000 2.000000 3.000000 4.000000]
[0.000000 3.000000 4.000000 2.000000]
element_aligned: 4/28
[1.000000 2.000000 3.000000 4.000000 5.000000 6.000000 7.000000]
[4.000000 2.000000 3.000000 0.000000 0.000000 0.000000 0.000000]

Answer 2

I saw the rotate() function, but I don't think that will work given my code.

Yes it will work.

When learning there is gain in "reinventing the wheel" (e.g. implementing rotate yourself) and there is also gain in learning how to use the existing pieces (e.g. use standard library algorithm functions).

Here is how you would use std::rotate from the standard library:

std::vector<int> rotate_1(const std::vector<int>& v)
{
   std::vector<int> result = v;
   std::rotate(result.begin(), result.begin() + 1, result.end());
   return result;
}

Answer 3

Use Sergey's answer. This answer deals with why what the asker attempted did not work. They're damn close, so it's worth going though it, explaining the problems, and showing how to fix it.

In

v.at(i) = v.at(i + 1);

v is constant. You can't write to it. The naïve solution (which won't work) is to cut out the middle-man and write directly to the result vector because it is NOT const

result.at(i) = v.at(i + 1);

This doesn't work because

   vector<int> result;

defines an empty vector. There is no at(i) to write to, so at throws an exception that terminates the program.

As an aside, the [] operator does not check bounds like at does and will not throw an exception. This can lead you to thinking the program worked when instead it was writing to memory the vector did not own. This would probably crash the program, but it doesn't have to¹.

The quick fix here is to ensure usable storage with

vector<int> result(v.size());

The resulting code

vector<int> rotate(const vector<int>& v)
{
   // PUT CODE BELOW THIS LINE. DON'T CHANGE ANYTHING ABOVE.
   vector<int> result(v.size()); // change here to size the vector
   int size = 3;
   for (auto i = 0; i < size - 1; ++i)
   {
       result.at(i) = v.at(i + 1); // change here to directly assign to result
   }
   return result;
   // PUT CODE ABOVE THIS LINE. DON'T CHANGE ANYTHING BELOW.
}

almost works. But when we run it on {1, 2, 3} result holds {2, 3, 0} at the end. We lost the 1. That's because v.at(i + 1) never touches the first element of v. We could increase the number of for loop iterations and use the modulo operator

vector<int> rotate(const vector<int>& v)
{
   // PUT CODE BELOW THIS LINE. DON'T CHANGE ANYTHING ABOVE.
   vector<int> result(v.size());
   int size = 3;
   for (auto i = 0; i < size; ++i) // change here to iterate size times
   {
       result.at(i) = v.at((i + 1) % size); // change here to make i + 1 wrap
   }
   return result;
   // PUT CODE ABOVE THIS LINE. DON'T CHANGE ANYTHING BELOW.
}

and now the output is {2, 3, 1}. But it's just as easy, and probably a bit faster, to just do what we were doing and tack on the missing element after the loop.

vector<int> rotate(const vector<int>& v)
{
   // PUT CODE BELOW THIS LINE. DON'T CHANGE ANYTHING ABOVE.
   vector<int> result(v.size()); 
   int size = 3;
   for (auto i = 0; i < size - 1; ++i)
   {
       result.at(i) = v.at(i + 1);
   }
   result.at(size - 1) = v.at(0); // change here to store first element

   return result;
   // PUT CODE ABOVE THIS LINE. DON'T CHANGE ANYTHING BELOW.
}

Taking this a step further, the size of three is an unnecessary limitation for this function that I would get rid of and since we're guaranteeing that we never go out of bounds in our for loop, we don't need the extra testing in at

vector<int> rotate(const vector<int>& v)
{
   // PUT CODE BELOW THIS LINE. DON'T CHANGE ANYTHING ABOVE.
   if (v.empty()) // nothing to rotate.
   {
      return vector<int>{}; // return empty result
   }
   vector<int> result(v.size());
   for (size_t i = 0; i < v.size() - 1; ++i) // Explicitly using size_t because
                                             // 0 is an int, and v.size() is an
                                             // unsigned integer of implementation-
                                             // defined size but cannot be larger
                                             // than size_t
                                             // note v.size() - 1 is only safe because
                                             // we made sure v is not empty above
                                             // otherwise 0 - 1 in unsigned math
                                             // Becomes a very, very large positive
                                             // number
   {
      result[i] = v[i + 1];
   }
   result.back() = v.front(); // using direct calls to front and back because it's 
                              // a little easier on my mind than math and [] 

   return result;
   // PUT CODE ABOVE THIS LINE. DON'T CHANGE ANYTHING BELOW.
}

We can go further still and use iterators and range-based for loops, but I think this is enough for now. Besides at the end of the day, you throw the function out completely and use std::rotate from the <algorithm> library.

¹This is called Undefined Behaviour (UB), and one of the most fearsome things about UB is anything could happen including giving you the expected result. We put up with UB because it makes for very fast, versatile programs. Validity checks are not made where you don't need them (along with where you did) unless the compiler and library writers decide to make those checks and give guaranteed behaviour like an error message and crash. Microsoft, for example, does exactly this in the vector implementation in the implementation used when you make a debug build. The release version of Microsoft's vector make no checks and assumes you wrote the code correctly and would prefer the executable to be as fast as possible.

Answer 4

First, just pay attention that you have passed v as const reference (const vector<int>&) so you are forbbiden to modify the state of v in v.at(i) = v.at(i + 1);

Although Sergey has already answered a straight forward solution, you could correct your code like this:

#include <vector>
using namespace std;

vector<int> left_rotate(const vector<int>& v)
{
   vector<int> result;
   int size = v.size(); // this way you are able to rotate vectors of any size
   for (auto i = 1; i < size; ++i)
       result.push_back(v.at(i));

   // adding first element of v at end of result
   result.push_back(v.front());
   return result;
}

Answer 5

Since you know exactly how many elements you have, and it's the smallest number that makes sense to rotate, you don't need to do anything fancy - just place the items in the order that you need, and return the result:

vector<int> rotate3(const vector<int>& x) {
    return vector<int> { x[1], x[2], x[0] };
}

Note that if your collection always has three elements, you could use std::array instead:

std::array<int,3>