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

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

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

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

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

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

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

stack_vector<match_item, 256> matches;

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

Обновление

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

Ответ 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;

Ответ 2

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

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

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

Ответ 3

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

STLSoft от Matthew Wilson (автор Imperfect С++) имеет класс шаблона 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- заместитель стека /

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

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

Ответ 4

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

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

Ответ 5

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

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

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

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

(Если 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 );

}

Ответ 6

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

Ответ 7

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

Ответ 8

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

Я бы предпочел версию boost, если бы я ее использовал.

Ответ 9

Увеличьте это. Его называют small_vector

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

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