VecDeque
documentation说它使用可增长的环形缓冲区作为实现。
它在内部如何运作?
push_back
和pop_front
)的情况下,何时进行转换?每次我打电话给pop_front
?当内部缓冲区达到临界尺寸?TL; DR:
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 ]
当内部缓冲区被填满并且你推送另一个东西时,你有三个场景描述in the code:
缓冲区只会增长。
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 . . . . . . ]
缓冲区增长后,尾部移动到缓冲区的末尾。
H T
Before [o o o o o . o o ]
H T
After [o o o o o . . . . . . . . . o o ]