Recently I and two of my colleagues went into an argument, which was very heated though, about whichever to use as the best containers. The main arguments were focused on commonly used containers in OI, which contained array,queue,stack,vector, and a much less commonly used deque, that I didn ‘t know until one of them started a code fight with it.

I possess suspicion over the exact results of who was right and who was wrong. So we have to test what could we believe in, just as Karl Marx had once said, verum index sui et falsi.

The following table is a list of the final results, all of which intervened \(10^7\) insertions, queries or modifications for each group of operations.

Operation Array Queue Stack Deque Vector
Random Access 0. 306 s N/A N/A N/A 0. 658 s
Random Modification 0. 881 s N/A N/A N/A 0. 924 s
Push (Front) N/A 2. 473 s N/A 1. 995 s ~ 4000 s
Push (Rear) N/A N/A 2. 535 s 2. 130 s 2. 709 s
Get (Front) N/A 2. 000 s N/A 1. 593 s 0. 658 s
Get (Rear) N/A N/A 4. 693 s 4. 606 s 0. 658 s
Pop (Front) N/A 1. 374 s N/A 1. 109 s ~ 7000 s
Pop (Rear) N/A N/A 1. 375 s 1. 148 s ~ 4500 s

Some of the data are not properly tested, due to the \(O(n^2)\) time complexity of doing that, I am not eligible to spend my precious time on such meaningless things.

The aforementioned test results are tested on an Intel 1st Gen Core 2 Duo T7500, with 2. 20 GHz CPU clock frequence, loaded with 4GB DDR2-667 memory. This spec is closer to the official NOI judging interface, and around 10 times slower than the average state-of-the-art computers.

It seems that deque not only captures both the qualities of stack and queue, it also implements it in faster ways than stack and queue, and provides fast access speeds for them.

Manually implementing a queue or a stack using arrays can be a nice choice, when time is required and memory constraints are not severe. Otherwise use deque instead, it is indeed faster than queue or stack, especially after a couple of tests.

The source code of the test is released below, which requires around 400 MB of memory on runtime.


#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <ctime>

#include <queue>
#include <stack>
#include <vector>
// #include <list>
#include <deque>

#define rep(__x) for (int i = 1; i <= (__x); i++)
#define note(__s) printf("%s: %lf\n", __s, get_time())
#define $ if (0)
using namespace std;

double get_time(void)
{
    static double last_time = 0;
    double cur_time = (double)clock() / 1000.0;
    double elapsed_time = cur_time - last_time;
    last_time = cur_time;
    return elapsed_time;
}

const int   n = 10e7; // Size of performance evaluation
const int   m = 10e4; // For smaller sizes, estimated large time complexity.
queue<int>  que;
stack<int>  stk;
vector<int> vec;
deque<int>  deq;
int*        arr = new int[n + 1];

int main(int argc, char** argv)
{${
    // Array operations
    get_time();
    rep(n) arr[i] = 16384;
    note("Array random modify");
    rep(n) int tmp = arr[i];
    note("Array random access");
    // Queue operations
    get_time();
    rep(n) que.push(16384);
    note("Queue pushing");
    rep(n) int tmp = que.front();
    note("Queue fronting");
    rep(n) que.pop();
    note("Queue popping");
    // Stack operations
    get_time();
    rep(n) stk.push(16384);
    note("Stack pushing");
    rep(n) int tmp = stk.top();
    note("Stack topping");
    rep(n) stk.pop();
    note("Stack popping");
    // Deque operations
    get_time();
    rep(n) deq.push_front(16384);
    note("Deque pushing (front)");
    rep(n) int tmp = deq.front();
    note("Deque getting (front)");
    rep(n) deq.pop_front();
    note("Deque popping (front)");
    rep(n) deq.push_back(16384);
    note("Deque pushing (back)");
    rep(n) int tmp = deq.back();
    note("Deque getting (back)");
    rep(n) deq.pop_back();
    note("Deque popping (back)");
    // Vector operations
}
    get_time();
    rep(m) vec.insert(vec.begin(), 16384);
    note("Vector pushing (front)");
    rep(m) int tmp = *vec.begin();
    note("Vector getting (front)");
    rep(m) vec.erase(vec.begin());
    note("Vector popping (front)");
    rep(n) vec.push_back(16384);
    note("Vector pushing (back)");
    rep(n) int tmp = *--vec.end();
    note("Vector getting (back)");
    rep(m) vec.erase(--vec.begin());
    note("Vector popping (back)");
    vec.clear();
    get_time();
    rep(n) int tmp = vec[i];
    note("Vector random access");
    rep(n) vec[i] = 256;
    note("Vector random modify");
    return 0;
}