4

stl::deque is implemented as an array of arrays; this questions explains how it is implemented in most cases; My question is: is it possible to set the size of the inner array (or chunk) ? It seems to be an implementation detail that is impossible to manipulate. Are there implementations that allow to set the size of inner array?

Thanks Pinky for the answer: in libstdc++ (gcc stl) we have 

#ifndef _GLIBCXX_DEQUE_BUF_SIZE
#define _GLIBCXX_DEQUE_BUF_SIZE 512
#endif

  inline size_t
  __deque_buf_size(size_t __size)
  { return (__size < _GLIBCXX_DEQUE_BUF_SIZE
            ? size_t(_GLIBCXX_DEQUE_BUF_SIZE / __size) : size_t(1)); }

So that the size of the inner node is set by defining _GLIBCXX_DEQUE_BUF_SIZE (#define _GLIBCXX_DEQUE_BUF_SIZE 4096 - if you want an inner node of this size) before including the deque header (for stdc++)

__deque_buf_size even has some doxygen documentation, so that this solution is documented (even though it is not covered by the standard).

  /**
   *  @brief This function controls the size of memory nodes.
   *  @param  __size  The size of an element.
   *  @return   The number (not byte size) of elements per node.
   *
   *  This function started off as a compiler kludge from SGI, but
   *  seems to be a useful wrapper around a repeated constant
   *  expression.  The @b 512 is tunable (and no other code needs to
   *  change), but no investigation has been done since inheriting the
   *  SGI code.  Touch _GLIBCXX_DEQUE_BUF_SIZE only if you know what
   *  you are doing, however: changing it breaks the binary
   *  compatibility!!
  */
Community
  • 1
  • 1
MichaelMoser
  • 3,172
  • 1
  • 26
  • 26
  • 1
    I think it is possible, I have read the source code of SGI STL, the buffer size can be determined by `__deque_buf_size()`. – Jiahao Cai Apr 05 '17 at 03:29
  • the standart says nothing about "inner arrays", so this would be very implementation-specific and will probably rise some compatibility issues, but in the end nothing is really impossible – Ap31 Apr 05 '17 at 06:04
  • Would you mind moving the "answer" part in the question to an actual answer? It's [encouraged by SE rule](https://stackoverflow.com/help/self-answer). – user202729 Mar 27 '19 at 14:56

2 Answers2

0

Unfortunately, the size of inner array (i.e. blocks or chunks) of std::deque cannot be set. The size of inner array depends on an implementation.

I'd like to suggest sfl::segmented_vector container from my library which you can find at GitHub: https://github.com/slavenf/sfl-library

This container is similar to std::deque. The size of inner arrays (I call them segments) is specified at the compile time as a template parameter.

slavenf
  • 56
  • 5
-2

You can use its ctor:

std::deque<int> myDeque (size, defaultValue);

Or resize function:

std::deque<int> myDeque;
...
myDeque.resize(newSize);
jplc
  • 354
  • 1
  • 11