Использование памяти std:: deque - Visual С++ и сравнение с другими

Ответ 1

gcc имеет

return __size < 512 ? size_t(512 / __size) : size_t(1);

с комментарием

/*  The '512' is
 *  tunable (and no other code needs to change), but no investigation has
 *  been done since inheriting the SGI code.
 */

Ответ 2

Реализация Dinkumware (MS) хочет увеличить значение deque на 16 байт за раз. Может быть, это просто очень старая реализация (например, первая из них когда-либо?), Которая была настроена для платформ с очень маленькой памятью (по сегодняшним меркам), чтобы предотвратить затухание и исчерпание памяти (например, std::vector)?

Мне пришлось реализовать свою собственную очередь в приложении, над которым я работаю, потому что область памяти размером 2,5X std::queue (которая использует std::deque) неприемлема.

По-видимому, на межстранах очень мало доказательств того, что люди столкнулись с этой неэффективностью, что удивительно для меня. Я бы подумал, что такая фундаментальная структура данных, как очередь (стандартная библиотека, не менее), будет довольно распространенной в природе и будет работать в приложениях с производительностью/временем/пространством. Но мы здесь.

Чтобы ответить на последний вопрос, стандарт С++ не определяет интерфейс для изменения размера блока. Я уверен, что он не предусматривает каких-либо реализаций, просто требования сложности для вставки/удаления с обоих концов.

Ответ 3

STLPort

... кажется до использовать:

::: <stl/_alloc.h>
...
enum { _MAX_BYTES = 32 * sizeof(void*) };
...
::: <deque>
...
static size_t _S_buffer_size()
{
  const size_t blocksize = _MAX_BYTES;
  return (sizeof(_Tp) < blocksize ? (blocksize / sizeof(_Tp)) : 1);
}

Таким образом, это означает, что размер блока 32 x 4 = 128 байтов на 32-битном и 32 x 8 = 256 байтах размером блока на 64 бит.

Моя мысль: из-за большого размера POV я предполагаю, что для любой реализации будет иметь смысл работать с блоками переменной длины, но я думаю, что было бы очень сложно получить правильное требование с постоянным временем случайного доступа deque.

Что касается вопроса

Разрешает ли STL переопределение этого размера блока во время компиляции без изменения кода?

Невозможно и здесь.

Apache

(похоже, версия Rogue Wave STL), по-видимому, использует:

static size_type _C_bufsize () {
    // deque only uses __rw_new_capacity to retrieve the minimum
    // allocation amount; this may be specialized to provide a
    // customized minimum amount
    typedef deque<_TypeT, _Allocator> _RWDeque;
    return _RWSTD_NEW_CAPACITY (_RWDeque, (const _RWDeque*)0, 0);
}

поэтому, кажется, существует некоторый механизм для переопределения размера блока с помощью специализации, а определение... выглядит так:

// returns a suggested new capacity for a container needing more space
template <class _Container>
inline _RWSTD_CONTAINER_SIZE_TYPE
__rw_new_capacity (_RWSTD_CONTAINER_SIZE_TYPE __size, const _Container*)
{
    typedef _RWSTD_CONTAINER_SIZE_TYPE _RWSizeT;

    const _RWSizeT __ratio = _RWSizeT (  (_RWSTD_NEW_CAPACITY_RATIO << 10)
                                       / _RWSTD_RATIO_DIVIDER);

    const _RWSizeT __cap =   (__size >> 10) * __ratio
                           + (((__size & 0x3ff) * __ratio) >> 10);

    return (__size += _RWSTD_MINIMUM_NEW_CAPACITY) > __cap ? __size : __cap;
}

Так что я бы сказал, что это так, аэм, сложный.

(Если кто-то хочет понять это дальше, не стесняйтесь редактировать мой ответ напрямую или просто оставить комментарий.)