0

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.

Daniel
  • 10,641
  • 12
  • 47
  • 85
shrubbroom
  • 45
  • 4
  • Why don't you look at how the pros do it? E.g. _"Microsoft choose values of 16 or smaller for the number of elements in a block. (Search for _DEQUESIZ)."_ - https://stackoverflow.com/a/46724521/2920343 – CompuChip Apr 18 '19 at 08:03
  • Possible duplicate of [What the heque is going on with the memory overhead of std::deque?](https://stackoverflow.com/questions/4088999/what-the-heque-is-going-on-with-the-memory-overhead-of-stddeque) – ponury-kostek Apr 18 '19 at 10:33

1 Answers1

1

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.

Dblaze47
  • 868
  • 5
  • 17