небольшая строковая оптимизация для вектора?

Question

Я знаю, что несколько (все?) Реализаций STL реализуют оптимизацию «маленькой строки», где вместо хранения обычных 3 указателей для начала, конца и емкости строка будет хранить фактические символьные данные в памяти, используемой для указателей, если sizeof (символы) <= sizeof (указатели). Я нахожусь в ситуации, когда у меня есть много маленьких векторов с размером элемента <= sizeof (указатель). Я не могу использовать массивы фиксированного размера, поскольку векторы должны иметь возможность динамического изменения размера и могут потенциально стать довольно большими. Тем не менее, средний (не средний) размер векторов будет всего 4-12 байтов. Так что оптимизация «маленькой строки», адаптированная к векторам, была бы для меня очень полезной. Существует ли такая вещь? </p>

Я думаю о том, чтобы свернуть свое собственное, просто грубой силой преобразовав вектор в строку, то есть предоставив векторный интерфейс для строки. Хорошая идея?

Answer 1

Boost 1.58 был только что выпущен, и в его библиотеке Container есть класс small_vector на основе LLVM SmallVector.

Существует также static_vector, который не может превышать изначально заданный размер. Оба контейнера предназначены только для заголовков.

Библиотека folly от Facebook также содержит несколько потрясающих контейнеров.

Он имеет small_vector, который можно настроить с помощью параметра шаблона, чтобы он действовал как векторы static или small форсирования. Он также может быть настроен на использование маленьких целочисленных типов для ведения учета по внутреннему размеру, что не удивительно:)

Идет работа по созданию межплатформенной библиотеки, поэтому поддержка Windows / MSVC должна когда-нибудь появиться ...

Answer 2

Вы можете позаимствовать реализацию SmallVector от LLVM. (только заголовок, расположенный в LLVM \ include \ llvm \ ADT)

Answer 3

Если T является типом POD, почему не basic_string вместо вектора ??

Answer 4

Это было обсуждено года назад (и некоторые имена в этой теме могут показаться немного знакомыми :-)), но я не знаю о существующей реализации. Я не думаю, что я бы попытался адаптировать std :: string к задаче. Точные требования к типу, по которым std :: basic_string не очень хорошо сформулированы, но стандарт довольно ясен, что он предназначен только для чего-то, что действует как char. Для типов, которые существенно различаются, это может все еще работать, но трудно сказать, что произойдет - это никогда не предназначалось и, вероятно, не было проверено со многими типами, кроме маленьких целых.

Когда вы приступите к этому, реализовать std::vector с нуля (даже с небольшой векторной оптимизацией) будет не очень сложно.