是否将STL deque实现为循环链表？ [英] Is STL deque implemented as a circular linked list?

问题描述

我无法找到在C ++ STL中如何实现deque的内部。

I am not able to find internals of how deque is implemented in C++ STL.

我在C＃中读取它是一个循环列表。 C ++ STL是真的吗？

I read it somewhere earlier that in C# it is implemented as a circular list. is it true of the C++ STL too? Also, can you please explain why it is so?

编辑：通过C ++ STL，我的意思是Visual Studio C ++ 2010附带的STL库，也是一个以及gcc

EDIT : by C++ STL, I mean the STL library that ships with Visual studio C++ 2010, and also the one which ships along with gcc

推荐答案

否。

在大多数实现（包括VC ++和VC ++）中，也许是gcc）它基本上是一个指向数据块的指针数组。当添加数据时，通常只是将它添加到现有的数据块。当现有块已满时，它将分配一个新的块，将其添加到要插入的数组的末尾，然后将数据添加到其中。当/如果基本数组空间不足，它会分配一个新的并复制指针。

In most implementations (including VC++ and probably gcc as well) it's basically an array of pointers to blocks of data. When you add data, it normally just adds it to an existing block of data. When the existing blocks get full, it allocates a new one, adds it to the end of the array where you're inserting, and then adds your data to it. When/if the base array runs out of space, it allocates a new one and copies the pointers there.

这篇关于是否将STL deque实现为循环链表？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！