Random errors with queues

[helios]

I'm getting (luckily infrequent) errors at random while getting the top element from a queue. I don't remember the exact error right now (and I don't know the exact conditions under which the error is produced, so I can't reproduce it), but I think it's something about the iterator not being incrementable.
All I think of that could be causing it is that this is an input queue that is pushed in one thread and popped in another.
Could being pushed and popped at the same time (possibly during a reallocation) cause this error? Perhaps if I increase the initial reserved space I could save myself the trouble of wrapping it with a thread-safe structure?

[firedraco]

I would just go for a thread-safe structure, since it will also prevent these kinds of problems from happening to other variables you may be editing...