c++ - 有没有一种快速方法可以将所有 vector 值 'move' 移动 1 个位置？

Question

我想实现一种算法，基本上将每个值(除了最后一个值)向左移动一个位置，就像第一个元素变成第二个元素，依此类推。

我已经这样实现了:

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

这可行，但我只是想知道是否有更快、可选更短的方法来达到相同的结果？

编辑:我犯了一个错误，我说我希望它向右移动，但实际上我希望它向左移动，对于造成的困惑感到抱歉，并感谢大家指出这一点。我还事先检查了 vector 是否不为空，只是没有将其包含在代码片段中。

Answer 1

正如评论(或多个评论？)所指出的，这里明显的选择是仅使用 std::deque。

另一种可能性是使用循环缓冲区。在这种情况下，您通常会有一个指向集合中第一个和最后一个项目的索引(或指针)。从开头删除一个项目包括增加该索引/指针(并将其环绕到已到达缓冲区末尾的开头)。无论集合大小如何，这都非常快且恒定的时间。缺点是每次添加项目、删除项目或查看项目时，您都需要做一些额外的数学运算。但通常只是添加一项，因此开销非常小。圆形缓冲区工作得很好，但它们有相当多的极端情况，所以让它们恰到好处通常是一种痛苦。更糟糕的是，许多明显的实现浪费了一个数据项的插槽(尽管这通常并不重要)。

稍微简单一点的可能性可以将开销减少一些常数因子。为此，请使用一个小包装器来跟踪集合中的第一个项目以及项目 vector 。当您想要删除第一项时，只需增加跟踪第一项的变量即可。当达到某个预设限制时，您会立即删除前 N 个元素。这将移动元素所花费的时间减少了 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]; }
};

如果您想变得非常棘手，您可以对此进行一些更改，以便将 max_slop 计算为集合中数据大小的百分比。在这种情况下，您可以更改所涉及的计算复杂性，而不是仅仅使其保持线性，而是使用比当前更大的常数因子。但我不知道您对此有多关心(如果有的话)——只有当您处理各种尺寸时，它才可能很重要。