C++ Stack implementation using std::list I have the following 'interface' to the C++ std::list and I was wondering how I could make it go faster. In particular, it needs to be able to evaluate up to two million operations in a matter of a couple seconds. Right now it's at around 8 seconds.

#include &lt;iostream&gt;
#include &lt;list&gt;

int main()
{

    int n, m;
    std::cin &gt;&gt; n &gt;&gt; m;

    std::list&lt;int&gt; myList (n);

    for (int i = 0 ; i &lt; m; i++) {
        std::string op;
        std::cin &gt;&gt; op;
        if (op[1] == 'O') {
            std::cout &lt;&lt; myList.back() &lt;&lt; '\n';
            myList.pop_back();
        } else {
            int val;
            std::cin &gt;&gt; val;
            myList.push_back(val);
        }
    }

    return 0;
}


It reads input in the form

3 4
PUSH 2
PUSH 3
POP
POP


With expected output

3
2


Where 3 corresponds to highest value, and 4 corresponds to number of operations. 

The operations are guaranteed to be safe (no POPing empty stacks), and each value is used at most once (this part in particular I feel I could optimize, but I'm not sure how).

Right now I'm testing with the following Python script:

print "1000000 2000000"

for val in xrange(1,1000001):
    print "PUSH ", val

for _ in xrange(0,1000000):
    print "POP"


And getting this for time:


8.89 real         0.00 user         0.01 sys



I started out using std::stack, but tried switching to std::list in order to give a preset size, so as to not need to reallocate memory. This did not help the time any, but that's where it stands as of now.
C++ std::cin and std::cout are both tied together and and tied to C stdin and C stdout respectively. This causes a lot of performance problems when dealing with std::cin and std::cout.

You can help the situation by using:

std::ios_base::sync_with_stdio(false);   // Disconnect from C IO
std::cin.tie(NULL);                      // Disconnect in from out (otherwise they flush).


If you change the code to use std::fstream (rather than std::cin/std::cout) you can get even better performance.

I did some experiments and reading a line and parsing the line separately improves things even more.

 std::getline(std::cin, line);
 if (line[1] == 'O') {
     // STUFF
 }
 else {
     int  val;
     std::stringstream  linestream(&amp;line[5]);
     linestream &gt;&gt; val;
     // STUFF;
 }


Also you should be using vector rather than list. It has two advantages: 1) You can allocate all the space you need in advance. 2) Spacial locality can make access faster.

Times:

 As written:  real  0m5.119s   user  0m4.751s   sys  0m0.362s
 Use vector:  real  0m4.906s   user  0m4.585s   sys  0m0.325s
 Un Tie:      real  0m4.247s   user  0m4.233s   sys  0m0.017s
 std::getline real  0m1.559s   user  0m1.546s   sys  0m0.017s
 std::fstream real  0m0.804s   user  0m0.766s   sys  0m0.022s


 C Version    real  0m0.434s   user  0m0.422s   sys  0m0.016s