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 
#include 

int main()
{

    int n, m;
    std::cin >> n >> m;

    std::list myList (n);

    for (int i = 0 ; i > op;
        if (op[1] == 'O') {
            std::cout > 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(&line[5]);
     linestream >> 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

StackExchange Code Review Q#115744, answer score: 5