CODEWITHSUNDEEP
c++
shrubbroom
shrubbroom

Reputation: 65

How to determine the size of chunks in a deque

I am trying to write a deque class in cpp by link list, however, I have no idea about how to decide the length of the chunks (buffers) when creating the deque.

Choose a good size for chunks will help to cut down the complexity of random visit in the deque.

Should I write a function that when a new element is pushed, it adjust the size of chunks dynamiclly, but i find it will have a high complexity in time since maybe it will move enormous data.

How should i deal with this problem.

Upvotes: 0

Views: 1352

Answers (1)

Dblaze47
Dblaze47

Reputation: 868

Check out the code for _DEQUESIZ (number of elements per block):

#define _DEQUESIZ   (sizeof (_Ty) <= 1 ? 16 \
: sizeof (_Ty) <= 2 ? 8 \
: sizeof (_Ty) <= 4 ? 4 \
: sizeof (_Ty) <= 8 ? 2 : 1)    /* elements per block (a power of 2) */

The larger the element grows, the smaller the number of element goes down to. You'll get expected percentual decrease of overhead with increase of element size only for elements that are larger than 8 bytes in size.

Check out the original answer here.

Upvotes: 1

Related Questions