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

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

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

Ответ 1

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

Ответ 2

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

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

facebook folly библиотека также содержит несколько удивительных контейнеров.

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

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

Ответ 3

Если T - тип POD, почему бы не basic_string вместо vector??

Ответ 4

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

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