I want to implement an algorithm that basically moves every value(besides the last one) one place to the left, as in the first element becomes the second element, and so on.

I have already implemented it like this:

for(int i = 0; i < vct.size() - 1; i  ){
    vct[i] = vct[i   1];
}

which works, but I was just wondering if there is a faster, optionally shorter way to achieve the same result?

EDIT: I have made a mistake where I said that I wanted it to move to the right, where in reality I wanted it to go left, so sorry for the confusion and thanks to everyone for pointing that out. I also checked if the vector isn't empty beforehand, just didn't include it in the snippet.

CodePudding user response：

As a comment (or more than one?) has pointed out, the obvious choice here would be to just use a std::deque.

Another possibility would be to use a circular buffer. In this case, you'll typically have an index (or pointer) to the first and last items in the collection. Removing an item from the beginning consists of incrementing that index/pointer (and wrapping it around to the beginning of you've reached the end of the buffer). That's quite fast, and constant time, regardless of collection size. There is a downside that every time you add an item, remove an item, or look at an item, you need to do a tiny bit of extra math to do it. But it's usually just one addition, so overhead is pretty minimal. Circular buffers work well, but they have a fair number of corner cases, so getting them just right is often kind of a pain. Worse, many obvious implementations waste one the slot for one data item (though that often doesn't matter a lot).

A slightly simpler possibility would reduce overhead by some constant factor. To do this, use a little wrapper that keeps track of the first item in the collection, along with your vector of items. When you want to remove the first item, just increment the variable that keeps track of the first item. When you reach some preset limit, you erase the first N elements all at once. This reduces the time spent shifting items by a factor of N.

template <class T>
class pseudo_queue {
    std::vector<T> data;
    std:size_t b;

    // adjust as you see fit:
    static const int max_slop = 20;

    void shift() { 
        data.erase(data.begin(), data.begin()   b);
    }

public:
    void push_back(T &&t) { data.push_back(std::move(t); }
    void pop_back() { data.pop_back(); }
    T &back() { return data.back(); }
    
    T &front() { return data[b]; }
    void pop_front() {
        if (  b > max_slop) shift();
    }

    std::vector<T>::iterator begin() { return data.begin()   b; }
    std::vector<T>::iterator end() { return data.end(); }

    T &operator[](std::size_t index) { return data[index   b]; }
};

If you want to get really tricky, you can change this a bit, so you compute max_slop as a percentage of the size of data in the collection. In this case, you can change the computational complexity involved, rather than just leaving it linear but with a larger constant factor than you currently have. But I have no idea how much (if at all) you care about that--it's only likely to matter much if you deal with a wide range of sizes.

CodePudding user response：

assuming you really meant moving data to the right, and that your code has a bug, you have std::move_backwards from <algorithms> and its sibling std::move to do that, but accessing data backwards may be inefficient.

std::move_backward(vct.begin(),vct.end()-1,vct.end());

if you actually meant move data to the left, you can use std::move

std::move(vct.begin() 1,vct.end(),vct.begin())

you can also use std::copy and std::copy_backward instead if your object is trivially copiable, the syntax is exactly the same and it will be faster for trivially copyable objects (stack objects).

you can just do a normal loop to the right, assuming vct.size() is bigger than 1.

int temp1 = vct[0];  // assume vct of int
int temp2;  // assume vct of int
 for(int i = 0;i<vct.size() - 1;i  ){
        temp2 = vct[i 1];
        vct[i 1] = temp1;
        temp1 = temp2;
    }

and your version is what's to do if you are moving to the left.

also as noted in the comments, you should check that your list is not empty if you are doing the loop version.