Need to shift elements in deque. Code not working

1.7k views Asked by At

I want a function which shifts according to input index u. If u is negative, shift right, else left. Using the code below the resulting deque is the same as the input.

deque<float> move(deque<float>p, int u)
{
    if(u==0 || p.size()==1)
        return p;

    else if(u<0)
    {
        for(int i=0; i<abs(p.size()); i++)
        {
            int temp = p.back();
            p.pop_back();
            p.push_front(temp);
        }       
    }

    else
    {
        for(int i=0; i<p.size(); i++)
        {
            int temp = p.front();
            p.pop_front();
            p.push_back(temp);
        }
    }

    return p;
  }

Another variation to this code which seems to work fine in Python but not in C++ is this:

deque<float> move1(deque<float>p, int u)
{
    deque<float> q;

    for(int i=0; i<p.size(); i++)
        q.push_back(p[(i-u) % p.size()]);

     return q;
 }
3

There are 3 answers

5
Sami Kuhmonen On BEST ANSWER

You are not actually shifting it one step to left or right, you are shifting it left or right as many times as there are items. This, of course, will result in the same order as it was.

Remove the loops to get what you want to achieve

deque<float> move(deque<float>p, int u)
{
    if(u==0 || p.size()==1)
        return p;

    else if(u<0)
    {
        for(int i=0; i<-u; i++)
        {
            int temp = p.back();
            p.pop_back();
            p.push_front(temp);
        }
    }

    else
    {
        for(int i=0; i<u; i++)
        {
            int temp = p.front();
            p.pop_front();
            p.push_back(temp);
        }
    }

    return p;
}

The second code should work just fine as it is written. It accesses elements displaced by u steps and stores them in another deque, returning it. What is not working with it?

0
The Dark On

For your second question, (i-u) % p.size() will be negative if u is bigger than i, as the % operator does not change sign.

You could use (i - u + p.size()) % p.size() instead.

1
Blastfurnace On

Your code could be much simpler if you used std::rotate from the standard library. For example:

std::deque<float> move(std::deque<float> p, int u)
{
    if (u == 0 || p.empty()) {
        return p;
    }
    if (u < 0) {
        std::rotate(p.begin(), std::prev(p.end(), -u), p.end());
    } else {
        std::rotate(p.begin(), std::next(p.begin(), u), p.end());
    }
    return p;
}