В ace.delos.com советуют избегать от vector как от чумы.

Да, но все же зачастую, задачу можно решить без их использования. Заюзав, например, сортировку, которая между прочим отличная, плюс бинпоиск или хэшмапу.

Насколько я знаю, всё как раз наоборот. vector в STL работает практически с такой же скоростью что и обычный массив. Вообще если вы заранее объявите размер вектора, то уступит он массиву может 5% времени. А вот set и map. написанные умелыми руками, не только более подойдут для специализированных задач, но будут работать быстрее. Однако писать свой set и map долго и почти всегда не нужно. Совсем другое дело string. Более ужасной вещи чем string представить трудно. Он может есть памяти не в 2, а чуть ли не в 5 раз больше чем использует на самом деле. При этом работает он ОЧЕНЬ медленно. Вот это точно чума.

Я бы так сильно не бросался нападками на std::list для этого нужно привести свою реализацию и я могу хорошо раскритиковать твой код где всё гладко, а где плохо. Знаешь почему память выделяется блоками это сделано специально для оптимизации ведь для этого и создавалась страничная адресация, да ладно что тут говорить вернёмся к списку. list двунаправленный список то есть он жрёт больше памяти чем однонаправленный slist-список, но он быстрее работает по удалению и вставки узла где у 2-ух связного оценка в O(1) по сравнению с slist O(n)... Наверное у тебя каша в голове для каких реализаций применять ту или иную структуру данных, только без обид. Связные списки хороши тем что используют память эффективно без лишней памяти по сравнению с разряжёнными массивами и хэш-таблицами, например для создания ассоциативных структур можно выбирать использовать хэш-таблицу или BST-деревья, AVL-деревья или RB-деревья, ну да можно и декартовое дерево, а для линейных данных vector, deque, slist, list, queue, stack. Я как разработчик 3D-игр давно убедился в эффективности библиотеки STL почти никогда меня stl-контейнеры не подводили, для начала попробуй написать свою реализацию list для работы в боевых условиях где кол-во выборок зашкаливает. На счёт статических массивов ведь не всегда точно известно сколько будет входных данных или думаешь зря в языке С/С++ строки заканчиваются \0 — null terminate. Конечно статический массив работает быстрее динамического так как динамический массив теряет время на реаллокацию и копирование. Приведу немного прикладной пример, например вы разрабатываете векторный редактор и вы как разработчик не можете точно знать сколько объектов будет создавать пользователь и что на ум приходит какая структура данных, конечно динамический массив или связной список, вот как раз тут статический массив не подходит. И последнее ведь библиотека STL создавалась не для одного типа машин, теперь подумайте на досуге.
P.S. Чем сложнее код, тем больше число ошибок.

Я использую командную строку linux + блокнот (если Вы это имели в виду). Что касается времени, сначала я заметил, что одна и та же задача с использованием стека выполняется несколько дольше, чем в случае применения массива. Впрочем, здесь оба решения укладывались в отведенное время с огромным запасом. Сейчас я обнаружил, что задача не укладывается во время, даже когда максимальные тесты значительно меньше, чем в исходной задаче , хотя действовал я по алгоритму, описанному в разборе.

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

Благодарю всех отписавшихся за помощь.

Статические объекты (со static storage duration) выделяются не на стеке, а в специально отведённой области памяти, которая создаётся при запуске программы.

Я проводил некоторые исследования по теме vector vs массив. Могу подтвердить, что в GCC операции доступа к элементам одинаковы в обоих случаях. Единственное различие — это необходимость одной лишней инструкции в случае vector, которая загружает адрес массива, хранящийся в объекте vector. Естественно, в случае цикла по вектору эту инструкцию не нужно повторять при каждой итерации, так что она почти не влияет на скорость выполнения.

Так вот упрощенно stack, queue, deque устроены следющим образом -- это список корзин

deque да, а stack и queue — это адапторы. Не нравится deque? Передавай им другой контейнер.

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

• a) использовать существенно больше памяти, чем статический массив такого же размера (из-за обеспечения амортизированного O(1) на push_back/pop_back)
• b) намного медленнее работать из-за перевыделения памяти при увеличении размера.

Когда же мы работаем с вектором, как со статическим массивом, то есть итерация/обращение по индексу, то наличие разницы по скорости будет зависеть от конкретной реализации stl и конкретного компилятора. Я видел очень много обсуждений (не связанных с олимпиадами), где рассматривались тормоза вектора по сравнению с массивом при итерациях с обращением по индексу. Большинства этих обсуждений не было бы, если бы во многих версиях Dinkum STL (это именно та STL, что идет вместе с Visual Studio) в релизной версии vector::operator[] не было бы проверки на выход за пределы вектора (!). А она там была, поэтому обращение по индексу к вектору даже в релизе было совсем не таким же легким, как обращение по индексу к массиву. И поэтому сравнивать их было бесполезно в таком виде, сравнивать нужно было итерацию по вектору с помощью итераторов.

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