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

Question

I was solving the puzzles in 2017 Advent of Code. It was necessary to fill in circular buffer using certain algorithm. For the buffer implementation I first used vector, and then I tried with deque. I am getting different results when printing values of the vector and the queue. Here's the code:

#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;
}

This is the result when using vector:

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

and this is when using deque (just change "vector" to "deque" and comment out circularBuffer.reserve(20) line):

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

Why there are different results for vector and deque?

Answer 1

You get undefined behaviour when you insert an element causing reallocation, and then use the old iterator again.

Anything can happen.

Use index to store current position and it'll work the same way.