插入std :: vector与std :: deque中的插入

Question

我正在解决2017 Advent of Code的难题。有必要使用某种算法填充循环缓冲区。对于缓冲区实现我首先使用了vector，然后我尝试了deque。打印矢量和队列的值时，我得到的结果不同。这是代码：

#include <iostream>
#include <vector>

void PrintBuffer(std::vector<int> a_CircularBuffer)
{
    for (std::vector<int>::iterator it = a_CircularBuffer.begin(); it != a_CircularBuffer.end(); ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;
}

int main()
{
    std::vector<int> circularBuffer;
    circularBuffer.reserve(20);

    circularBuffer.push_back(0);
    circularBuffer.push_back(1);

    std::vector<int>::iterator currentPosition = circularBuffer.begin() + 1;

    for (int i = 2; i < 20; ++i) {
        int steps = 378;
        if (steps >= i) {
            steps = (steps % i);
        }    

        if ((circularBuffer.end() - currentPosition) <= steps) {
            currentPosition = circularBuffer.begin() + (((currentPosition - circularBuffer.begin()) + steps) % i);
            circularBuffer.insert(currentPosition, i);
        }
        else {
            currentPosition = currentPosition + steps;
            circularBuffer.insert(currentPosition, i);
        }
        PrintBuffer(circularBuffer);
    }
    return 0;
}

这是使用向量时的结果：

0 2 1
0 3 2 1 
0 3 2 4 1 
0 5 3 2 4 1 
0 6 5 3 2 4 1 
0 7 6 5 3 2 4 1 
0 7 6 8 5 3 2 4 1 
0 7 6 9 8 5 3 2 4 1 
0 10 7 6 9 8 5 3 2 4 1 
0 10 7 6 9 11 8 5 3 2 4 1 
0 10 7 6 9 11 8 5 3 2 4 12 1 
0 10 7 6 9 11 8 5 3 2 4 12 13 1 
0 10 7 6 9 11 8 5 3 2 4 12 14 13 1 
15 0 10 7 6 9 11 8 5 3 2 4 12 14 13 1 
...

这是在使用deque时（只需将“vector”更改为“deque”并注释掉circularBuffer.reserve（20）行）：

0 2 1 
0 3 2 1 
0 3 2 4 1 
0 5 3 2 4 1 
0 5 6 3 2 4 1 
0 5 6 7 3 2 4 1 
0 5 6 7 3 8 2 4 1 
0 5 6 7 3 9 8 2 4 1 
0 5 6 10 7 3 9 8 2 4 1 
0 5 6 10 7 3 9 8 11 2 4 1 
0 5 12 6 10 7 3 9 8 11 2 4 1 
0 5 12 6 13 10 7 3 9 8 11 2 4 1 
0 5 12 6 13 14 10 7 3 9 8 11 2 4 1 
0 5 12 6 13 14 10 7 3 15 9 8 11 2 4 1
...

为什么vector和deque有不同的结果？

Answer 1

插入导致重新分配的元素时会出现未定义的行为，然后再次使用旧的迭代器。

任何事情都可能发生。

使用索引存储当前位置，它将以相同的方式工作。