Глядя на C ++ STL-как вектор класса, но с использованием стека хранения

голоса
44

Перед тем, как написать мой собственный Я прошу всех вас всех.

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

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

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

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

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

stack_vector<match_item, 256> matches;

Я думал, что это было бы бросить зЬй :: bad_alloc, если он работает вне пространства, хотя это не должно когда-нибудь случится.

Обновить

Использование stack_container.h Хром работает отлично!

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

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

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 определенное и я попытался использовать его. Но это не наследуется от вектора или определить те же методы, чтобы она не была капля в замене. Я не хочу, чтобы переписать весь код с помощью вектора, так что я дал на него.

Задан 09/12/2008 в 23:15
источник пользователем
На других языках...                            


10 ответов

голоса
38

Вам не придется писать совершенно новый класс контейнера. Вы можете придерживаться с 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;
Ответил 09/12/2008 в 23:27
источник пользователем

голоса
15

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

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

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

Ответил 16/01/2014 в 14:23
источник пользователем

голоса
11

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

STLSoft Мэтью Уилсон (автор несовершенного 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

Ответил 10/12/2008 в 02:18
источник пользователем

голоса
4

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

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

для одного дурацкого теста ниже - всего 2 толчка, v [0] v [1], 2 поп, на одной платформе, макинтош РРС, НКУ-4,2 -O3 только. (Я понятия не имею, если Apple, оптимизировали их СТЛ.)

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

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

#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 );

}
Ответил 29/07/2009 в 12:20
источник пользователем

голоса
4

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

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

Ответил 09/12/2008 в 23:18
источник пользователем

голоса
3

tr1 :: массив частично совпадает с вашим описанием. Ей не хватает вещей, как толчок ___ назад () и т.д., но это может быть стоит взглянуть на в качестве отправной точки. Подведем и добавление индекса к «спине», чтобы поддержать push_back () и т.д., должны быть достаточно легко.

Ответил 09/12/2008 в 23:39
источник пользователем

голоса
2

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

Я бы предпочел вариант повысить, если бы я использовал его, хотя.

Ответил 13/05/2014 в 21:00
источник пользователем

голоса
2

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

Ответил 09/12/2008 в 23:25
источник пользователем

голоса
1

Повышение иметь это. Его называют small_vector

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

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

Ответил 21/04/2016 в 08:50
источник пользователем

голоса
0

Если вы хотели бы выделить в стеке , но не хочет , чтобы заранее определить максимальный размер во время компиляции, вы можете использовать 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)! Использование ответственно.

Ответил 07/03/2018 в 13:27
источник пользователем

Cookies help us deliver our services. By using our services, you agree to our use of cookies. Learn more