Комментарии 16
В описании std::vector небольшая неточность - стратегия роста емкости никак не указана в стандарте, так что это деталь реализации. В stdlibc++ и libc++ это удвоение размера, но вроде бы в Visual C++ используется множитель 1.5
Еще у Matthew Bentley, автора Colony, есть интересный документ про рост емкости для deque-like контейнера: https://plflib.org/matt_bentley_-_pot_blocks_bit_tricks.pdf
Я конечно не специалист по C, и возможно что-то не так понял, но... Если ваш контейнер содержит не ссылку на объект, а сам объект, то использовать ссылку на него, во вне работы с контейнером - ну... будет беда. Либо copy on write (value type), без ссылок, либо ссылки в контейнере.
Возможно я был не прав, но сама идея ссылки на элемент контейнера, инстинктивно вызывает у меня отторжение, и это мягко сказано. Тем более, тип контейнера имеет тенденцию меняться, а код который его использует, нет.
Иногда без этого никак. Например, вам нужен быстрый поиск и одновременно определенный порядок: придется завести map и скажем list, и иметь перекрестные ссылки между контейнерами. Хорошая практика конечно абстрагировать это как новый тип контейнера, но внутри будут ссылки между используемыми контейнерами.
fbvector не cache-friendly, а снижает фрагментацию памяти (или, лучше сказать, в случае удвоения фрагментация практически гарантирована).
Это одно и то же в данном контексте: рост с фактором меньше 2х позволяет вектору при росте использовать свои предыдущие куски памяти. Это и снижает фрагментацию и делает это cache-friendly поскольку предыдущие куски вероятно в кеше.
Так ли важно, находится ли в кэше память, которую вы перезаписываете?
Да, хотя не так сильно как на чтение конечно, и от конкретной системы зависит.
Всё что вы перезапишите должно быть рано или поздно скинуто в основную память. Если новый вектор расположен поверх старых, а старые версии еще не попали в основную память - то сброс этих старых версий в основную память вы сэкономили. В результате вам надо меньше пропускной способности шины.
Плюс в многопроцессорных системах экономия на координации в каком кеше какая память лежит.
Потрясающая статья, спасибо за труды!
более оптимально аллоцировать
классическая ошибка, не бывает более или менее оптимально, бывает либо оптимально, либо нет, это же определение оптимальности :)
Спасибо, хорошая подборка. Вы не упомянули boost::intrusive (как концепцию и как набор конкретных контейнеров). Она хорошего качества (я использую в проде много лет) и позволяет клепать вещи типа multi-index или queue-map правильно и быстро.
Искренне интеретсуюсь, почему std::valarray пропущен в статье ?
Часто провожу собеседования, статистически о std::valarray, кандидаты знают +- как и о std::deque = ничего.
В статье рассматривается скорее внутреннее устройство контейнеров и управление памятью.
std::valarray по своему внутреннему устройству имеет незначительное отличие от std::vector (а именно 2 указателя вместо 3, так как там size = capacity).
"Синтаксический сахар" (методы min, sqrt, и тд) для std::valarray отличается от такового у std::vector, но это не так важно. В мире C++ есть много vector-like объектов, но они не принесли бы принципиально новой информации в статью.
std::valarray имеет довольно таки интересный "сахар", как например, запись для обнуления элементов меньших нуля:
data[ data < 0 ] = 0;
Само по себе, существование такого сахара вызывает как минимум - любопытство. (Кто сможет реализовать такое API в векторе, не зная изначально и не подглядывая как это сделано в valarray ?).
Ну и в отличии от vector`а стандрат разрешает распарралеливать "сахар" (интересно реализовано ли это в современных компиляторах ?), и имеет дополнительные правила для aliasинга элементов что ещё больше делает его особенным.
Неклассические контейнеры в C++