Ищем C ++ STL-подобный векторный класс, но с использованием стекового хранилища

Question

Прежде чем написать свое, я спрошу у всех вас.

Я ищу класс C ++, который почти в точности похож на вектор STL, но хранит данные в массиве в стеке. Какой-то класс распределителя STL также будет работать, но я стараюсь избегать любого вида кучи, даже статической, выделенной кучи для каждого потока (хотя один из них - мой второй выбор). Стек просто эффективнее.

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

Для того, что я собирался написать сам, я думал о чем-то вроде этого:

char buffer[4096];
stack_vector<match_item> matches(buffer, sizeof(buffer));

Или у класса может быть внутреннее выделение буферного пространства. Тогда это будет выглядеть так:

stack_vector<match_item, 256> matches;

Я думал, что он бросит std :: bad_alloc, если ему не хватит места, хотя это не должно происходить.

Обновление

Использование Chrome в stack_container.h прекрасно работает!

Причина, по которой я сам не думал делать это таким образом, заключается в том, что я всегда игнорировал параметр объекта allocator для конструкторов коллекции STL. Я использовал параметр шаблона несколько раз для создания статических пулов, но я никогда не видел ни кода, ни написанного, который бы фактически использовал параметр объекта. Я узнал что-то новое. Очень круто!

Код немного запутан, и по какой-то причине GCC вынудил меня объявить распределитель как фактический элемент вместо его преобразования в параметр-распределитель вектора. Это произошло примерно так:

typedef std::pair< const char *, const char * > comp_list_item;
typedef std::vector< comp_list_item > comp_list_type;

comp_list_type match_list;
match_list.reserve(32);

На это:

static const size_t comp_list_alloc_size = 128;
typedef std::pair< const char *, const char * > comp_list_item;
typedef StackAllocator< comp_list_item, comp_list_alloc_size > comp_list_alloc_type;
typedef std::vector< comp_list_item, comp_list_alloc_type > comp_list_type;

comp_list_alloc_type::Source match_list_buffer;
comp_list_alloc_type match_list_alloc( &match_list_buffer );
comp_list_type match_list( match_list_alloc );
match_list.reserve( comp_list_alloc_size );

И я должен повторять это всякий раз, когда я объявляю новый. Но это работает так, как я хотел.

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

Answer 1

Вам не нужно писать совершенно новый контейнерный класс. Вы можете придерживаться своих контейнеров STL, но измените второй параметр, например, std::vector, чтобы дать ему свой собственный распределитель, который выделяет из стекового буфера. Авторы хрома написали распределитель только для этого:

https://chromium.googlesource.com/chromium/chromium/+/master/base/stack_container.h

Он работает, выделяя буфер, где вы говорите, насколько он велик. Вы создаете контейнер и вызываете container.reserve(buffer_size);. Если вы переполните этот размер, распределитель автоматически получит элементы из кучи (поскольку он получен из std::allocator, в этом случае он просто использует возможности стандартного распределителя). Я не пробовал, но похоже, что это от Google, так что я думаю, что стоит попробовать.

Использование выглядит так:

StackVector<int, 128> s;
s->push_back(42); // overloaded operator->
s->push_back(43);

// to get the real std::vector. 
StackVector<int, 128>::ContainerType & v = s.container();
std::cout << v[0] << " " << v[1] << std::endl;

Answer 2

Кажется, что boost :: static_vector - это то, что вы ищете. Из документации:

static_vector является гибридом между вектором и массивом: подобно вектору, это контейнер последовательности с непрерывным хранилищем, которое может изменяться в размере, наряду со статическим распределением, низкими издержками и фиксированной емкостью массива. static_vector основан на высокопроизводительных классах varray Адама Вулкевича и Эндрю Хундта.

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

Answer 3

Некоторые опции, которые вы можете посмотреть:

STLSoft Мэтью Уилсона (автор Imperfect C ++) имеет шаблонный класс auto_buffer, который помещает в стек массив по умолчанию, но если он становится больше, чем выделение стека, он будет захватывать память из кучи. Мне нравится этот класс - если вы знаете, что размеры вашего контейнера обычно ограничены довольно низким пределом, то вы получите скорость локального массива, выделенного стеком. Тем не менее, для угловых случаев, когда вам нужно больше памяти, все по-прежнему работает должным образом.

http://www.stlsoft.org/doc-1.9/classstlsoft_1_1auto__buffer.html

Обратите внимание, что используемая мной реализация - это не STLSoft, а реализация, которая сильно заимствует из нее.

«Ленивый программист» сделал пост для реализации контейнера, который использует alloca() для хранения. Я не фанат этой техники, но я позволю вам решить, хотите ли вы этого:

http://tlzprgmr.wordpress.com/2008/04/02/c-how-to-create-variable-length-arrays-on-the-stack/

Тогда есть boost::array, который не имеет динамического определения размеров первых двух, но дает вам больше интерфейса vector, чем просто использование указателей в качестве итераторов, которые вы получаете со встроенными массивами (т. Е. Вы получить begin(), end(), size() и т. д.):

http://www.boost.org/doc/libs/1_37_0/doc/html/boost/array.html

Answer 4

Если скорость имеет значение, я вижу время выполнения

• 4 нс int [10], фиксированный размер в стеке
• 40 нс <vector>
• 1300 нс <stlsoft/containers/pod_vector.hpp>

для одного глупого теста ниже - всего 2 нажатия, v [0] v [1], 2 щелчка, на одной платформе, Mac PPC, только gcc-4.2 -O3. (Понятия не имею, оптимизировал ли Apple их stl.)

Не принимайте время, которое вы сами не притворялись. И, конечно, каждый шаблон использования отличается. Тем не менее факторы> 2 меня удивляют.

(Если мемы, доступ к памяти, являются доминирующим фактором во время выполнения, Каковы все дополнительные мемы в различных реализациях?)

#include <stlsoft/containers/pod_vector.hpp>
#include <stdio.h>
using namespace std;

int main( int argc, char* argv[] )
{
        // times for 2 push, v[0] v[1], 2 pop, mac g4 ppc gcc-4.2 -O3 --
    // Vecint10 v;  // stack int[10]: 4 ns
    vector<int> v;  // 40 ns
    // stlsoft::pod_vector<int> v;  // 1300 ns
    // stlsoft::pod_vector<int, std::allocator<int>, 64> v;

    int n = (argv[1] ? atoi( argv[1] ) : 10) * 1000000;
    int sum = 0;

    while( --n >= 0 ){
        v.push_back( n );
        v.push_back( n );
        sum += v[0] + v[1];
        v.pop_back();
        v.pop_back();
    }
    printf( "sum: %d\n", sum );

}

Answer 5

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

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

Answer 6

tr1 :: array частично соответствует вашему описанию. В нем отсутствуют такие вещи, как push ___ back () и т. Д., Но, возможно, стоит взглянуть в качестве отправной точки. Завернуть его и добавить индекс в «back» для поддержки push_back () и т. Д. Должно быть довольно просто.

Answer 7

Возможно, вы используете Qt. Тогда Вы можете пойти на QVarLengthArray ( документы ). Он находится в основном между std::vector и std::array, статически выделяя определенную сумму и возвращаясь к распределению кучи в случае необходимости.

Я бы предпочел буст-версию, если бы использовал ее.

Answer 8

Почему вы хотите поместить его в стек ? Если у вас есть реализация alloca (), вы можете использовать распределитель классов, используя его вместо malloc (), но ваша идея использовать статически распределенный массив еще лучше: на большинстве архитектур это так же быстро, и вы этого не сделаете вы испортили стопку рисков.

Answer 9

Boost есть это. Его называют small_vector

small_vector - вектороподобный контейнер, оптимизированный для случая, когда он содержит мало элементов. Он содержит некоторые предварительно выделенные элементы на месте, что позволяет избежать использования динамического хранилища распределение, когда фактическое количество элементов ниже предварительно выделенный порог. small_vector вдохновлен SmallVector от LLVM контейнер. В отличие от static_vector, емкость small_vector может расти сверх первоначальной предварительно выделенной емкости.

small_vector можно преобразовать в small_vector_base, тип, который не зависит от предварительно выделенного элемента рассчитывать, позволяя клиентский код, который не должен быть шаблонным на этом N аргумент. small_vector наследует все функции-члены вектора, поэтому поддерживает все стандартные функции, такие как размещение, распределители состояний, и т.д.

Answer 10

Если вы хотите разместить в стеке, но не хотите заранее определять максимальный размер во время компиляции, вы можете использовать StackVector , небольшую реализацию, которая может использоваться следующим образом:

new_stack_vector(Type, name, size)

, где Type - тип элемента в векторе, name - имя переменной вектора, а size - максимальное количество элементов, разрешенных в векторе.

size может быть переменной и не обязательно должна быть константой времени компиляции! : D

Пример:

new_stack_vector(int, vec, 100); //like vector<int> vec; vec.reserve(100); but on the stack :)
vec.push_back(10); //added "10" as the first item in the vector

... и все!

Отказ от ответственности: Никогда не используйте очень большой размер массива в стеке в целом. Как вы не должны использовать int var[9999999], так же вы не должны использовать new_stack_vector(int, vec, 9999999)! Используйте ответственно.