VecDeque documentation说它使用可增长的环形缓冲区作为实现。
它在内部是如何工作的？
- 在我只将它用作队列的情况下(仅
push_back和pop_front)，移位何时完成？每次调用pop_front？当内部缓冲区达到临界大小时？ - 为什么有两片(一张在背面，一张在正面)？它们不是连续的吗？
最佳答案
长话短说:
- “移位”在缓冲区已填满且头部不在缓冲区末尾时完成。如果每次推送时都弹出，则无需移动数据。
- 值不连续，因为它们环绕缓冲区。
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 ]
关于collections - VecDeque 环形缓冲区在内部是如何工作的？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/49072494/