Обработка большого количества элементов в std :: stack - PullRequest
Новая
       8

Обработка большого количества элементов в std :: stack

1 голос
/ 24 мая 2010

Может ли C ++ std::stack обрабатывать более 10 тыс. Элементов int?А как насчет его производительности?

Ответы [ 5 ]

8 голосов
/ 24 мая 2010

10К что? Большинство реализаций std :: stack могут легко обрабатывать 10K примитивы с хорошей производительностью, поскольку это, вероятно, <80KB. Тем не менее, стандарт не гарантирует производительность. </p>

Также обратите внимание, что это зависит от того, какой бэкэнд вы используете. По умолчанию используется std :: deque, который в основном является массивом массивов. Тем не менее, вы должны получить приличную производительность с любым бэкэндом.

5 голосов
/ 24 мая 2010

A std::stack ограничивается только нижележащим контейнером (a std::stack является адаптером контейнера).

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

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

3 голосов
/ 24 мая 2010

Производительность зависит от используемого контейнера. Как уже упоминалось, stack - это адаптер, базовый контейнер может быть deque (по умолчанию), или vector, или list (все в std пространстве имен).

Ниже приведен пример сравнения производительности. Поскольку тип сохраняемого файла не указан в этом вопросе, я предполагаю, что он имеет тип unsigned int. Не стесняйтесь менять его в соответствии с вашими требованиями. В примере создается стек из 100 тыс. Элементов.

Содержание stack.cpp

#include <stack>
#include <vector>
#include <list>
#include <deque>
#include <assert.h>

typedef unsigned int Type;

#ifdef USE_VECTOR
typedef std::stack< Type, std::vector< Type > > StackType;
#elif USE_LIST
typedef std::stack< Type, std::list< Type > > StackType;
#else
typedef std::stack< Type, std::deque< Type > > StackType;
#endif

int main() {
    StackType mystack;
    for( unsigned int i = 0; i < 100 * 1024; ++i ) {
        mystack.push( i );
    }
    assert( mystack.size() == 100 * 1024 );
    return 0;
}

Сравнение исполнения: 

$ g++ -DUSE_VECTOR stack.cpp -o stack; time ./stack

real    0m0.023s
user    0m0.030s
sys     0m0.031s

$ g++ -DUSE_LIST stack.cpp -o stack; time ./stack

real    0m0.144s
user    0m0.186s
sys     0m0.030s

$ g++  stack.cpp -o stack; time ./stack

real    0m0.024s
user    0m0.030s
sys     0m0.015s

asaha@nedata8 ~/code
$

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

Очевидно, deque и vector приводят к аналогичной производительности, тогда как list хуже.

2 голосов
/ 24 мая 2010

Да, он может обрабатывать 10 КБ.Пока у вас есть ресурсы памяти для этого.Если вы беспокоитесь, что он использует внутренний стек, это не так.

Производительность зависит от реализации, но должна быть очень быстрой

1 голос
/ 24 мая 2010

std :: stack - это не контейнер, а адаптер контейнера. По умолчанию он использует std :: deque в качестве контейнера, но вы также можете использовать std :: vector или std :: list. Запросы освобождают память при удалении элементов.

...