queue container?

[Timon Gehr]

On 10/26/2011 12:25 PM, bearophile wrote:
> Timon Gehr:
>
>> A dynamic array of pointers to fixed size arrays is this:
>> T[N]*[] arr;
>> What would you wrap exactly?
>
> How do you allocate those T[N] in D?

int[N]* x = (new int[N][1]).ptr;


I don't like that either.

>
>
>> Do you know how this implementation compares to a circular buffer
>> implementation? I'd have expected that to be faster.
>
> A circular buffer is faster in some situations, when you on average need a constant number of items in your data structure. But a circular buffer needs lot of time to change its size a lot, because you have to halve or double it once in a while. Generally, if you don't know much about how your queue will be used, a dynamic array of chunks is better (some people use a linked list of chunks, but this makes it worse to access items randomly, and the time saved not managing a growable circular queue of the chunk pointers is not much, because the chunks usually contain hundreds of items or more).
>

Ok, I see, thanks. In my specific application of a queue buffer, the 
number of items is constant on average, except for some extreme border 
cases.