How does the VecDeque buffer buffer work internally?

Question

VecDequeThe documentation says that it uses a growing ring buffer as an implementation.

How does it work inside?

• In the case when I use it only as a queue (only push_backand pop_front), when is the transfer carried out? Every time I call pop_front? When does the internal buffer reach a critical size?
• Why are there two slices (one for the back, one for the front)? Aren't they contiguous?

Answer 1

TL DR:

• A “shift” is performed when the buffer is full and if the head is not at the end. If you click every time you click, there is no need to move data.
• Values ​​are not contiguous because they wrap the buffer.

---

VecDeque 2 : . / VecDeque, , /.

:

, , push_back pop_front.

        T       H
Before [o o o o . . . . ]
          T       H
After  [. o o o o . . . ]

. .

        H       T
Before [. . . . o o o o ]
          H       T
After  [o . . . . o o o ]

:

, , :

.

        T             H
Before [o o o o o o o . ]
        T             H
After  [o o o o o o o . . . . . . . . . ]

, , .

            H T
Before [o o . o o o o o ]
              T             H
After  [. . . o o o o o o o . . . . . . ]

After the buffer grows, the tail moves to the end of the buffer.

                  H T
Before [o o o o o . o o ]
                  H                 T
After  [o o o o o . . . . . . . . . o o ]