在 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 
...

这是在使用双端队列时（只需将 "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

当您插入一个导致重新分配的元素，然后再次使用旧的迭代器时，您会得到未定义的行为。

任何事情都可能发生。

使用索引存储当前位置，其工作方式相同。

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

Insertion in std::vector vs. insertion in std::deque

c++

vector

deque