Почему std :: deque не позволяет указывать размер корзины?

std::deque хранит элементы в "корзинах" (массивах) фиксированного размера. Различные компиляторы используют разные размеры ковша:

  • MSVC: 16 байт или размер элемента, если он больше
  • GCC: 512 байт или размер элемента, если он больше
  • Clang: element_size < 256? 4096: element_size * 16 element_size < 256? 4096: element_size * 16

Для MSVC (особенно) и GCC, если размер элемента deque больше, чем размер, std::deque жестко, std::deque превращается в свернутый std::list с потерями производительности в большинстве случаев.

Clang работает лучше, на мой взгляд, независимо от того, какой размер элемента deque, ведро будет составлять не менее 16 элементов. Хотя минимальный размер сегмента 4096 байт может быть неоптимальным в некоторых случаях для небольших элементов.

Почему в std::deque нет дополнительного параметра шаблона для размера корзины со значением по умолчанию, которое, по мнению поставщика, является разумным? Это не нарушит обратную совместимость, но позволит оптимизировать производительность.

Ответы

Ответ 1

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

Конечно, такая структура данных полезна. Стандарт мог предоставить его (под именем deque или как новый контейнер), но они этого не сделали. Напротив, в контейнерах unordered_* гарантированно используются контейнеры. За [unord.req]/9:

Элементы неупорядоченного ассоциативного контейнера организованы в сегменты. Ключи с одинаковым хеш-кодом появляются в том же сегменте. Количество сегментов автоматически увеличивается при добавлении элементов в неупорядоченный ассоциативный контейнер, так что среднее количество элементов в сегменте остается ниже границы. Перефразирование делает недействительными итераторы, изменяет порядок между элементами и изменения, в которых появляются элементы сегментов, но не делает недействительными указатели или ссылки на элементы. Для unordered_multiset и unordered_multimap перефразировка сохраняет относительный порядок эквивалентных элементов.

deque не имеет аналогичной формулировки.