Как мне лучше сгладить (одномерный) вектор для N значений? - PullRequest
Новая
       80

Как мне лучше сгладить (одномерный) вектор для N значений?

2 голосов
/ 19 марта 2020

Мне нужно что-то, что ведет себя как std::vector (interface / features / et c.), Но мне нужно, чтобы оно было плоским, то есть оно не должно динамически выделять буфер. Понятно, что в общем это не работает, так как доступный размер должен быть определен во время компиляции. Но я хочу, чтобы тип мог иметь дело с N объектами без дополнительных выделений, и только при нажатии дальнейших элементов прибегают к динамическому c выделению.

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

Я думаю, что я мог бы либо

  • A) самостоятельно готовить тип (вероятно, плохо, потому что я потерял бы нелепые оптимизации производительности от vector)
  • B) использовать какой-то вид variant<vector<T>,array<T,N>> с упаковщиком доступа (о, шаблон)
  • C) придумали MyAllocator<T,N>, который имеет array<T,N> элемент, который затем может быть использован для удерживать первые N элементов и после этого отложенного значения до allocator<T>, но я не уверен, может ли это сработать, потому что я не могу выяснить, должен ли vector постоянно хранить экземпляр своего типа распределителя как члена (я верю этому нет)

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

1 Ответ

1 голос
/ 19 марта 2020

Вы можете найти folly / small_vector использования.

folly :: small_vector - это контейнер последовательности, который реализует небольшую оптимизацию буфера. Он ведет себя так же, как std :: vector, за исключением того, что до тех пор, пока не зарезервировано определенное количество элементов, он не использует кучу.

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

Простой пример использования: 

small_vector<int,2> vec;
vec.push_back(0); // Stored in-place on stack
vec.push_back(1); // Still on the stack
vec.push_back(2); // Switches to heap buffer.

// With space for 32 in situ unique pointers, and only using a
// 4-byte size_type.
small_vector<std::unique_ptr<int>, 32, uint32_t> v;

// A inline vector of up to 256 ints which will not use the heap.
small_vector<int, 256, NoHeap> v;

// Same as the above, but making the size_type smaller too.
small_vector<int, 256, NoHeap, uint16_t> v;
...