C++ STL Data Structure Constant Time Push/Pop/Random Access by Index With Reliable Pointers to Elements

I've been looking through the C++ STL, and I'm not sure which data structure is the most appropriate for this particular use case. It needs to be able to do the following three things in constant time:

1. Constant time Random Access by Index (so a random element can be chosen in constant time)
2. Constant time push/pop at the end only
3. Pointers to contained items cannot be invalided when pushing/popping (don't care about iterators)

Initially, I tried using a vector; it satisfies the first two criteria perfectly. However, I learned the hard way that when you push new items onto the vector, pointers to its elements will become invalidated since the vector relocates itself to keep all its memory contiguous. Although the problem can be fixed by using the vector's reserve() method ahead of time, the problem then is that it requires knowing the largest number of elements I may need to store inside of it, and this is not a value that I know ahead of time, nor can I really calculate it. I also can't just use reserve again whenever the size gets to big because then pointers to the elements of the vector will still become invalidated.

So then I tried a deque. Believe it or not, a deque actually satisfies all three criteria perfectly. Pointers to elements are NOT invalidated with pushing/popping, which are constant time. However, I noticed that there was a cost; the deque was about two times slower than the vector. I know that the deque has the additional capability of being able to put items at the front, which is unnecessary for my purposes, and I'm not sure if it is specifically this additional capability OR the fact that not all memory is kept contiguously that's responsible for the slowdown.

So while a deque does satisfy those three criteria, is there a data structure in the C++ STL that can do better? Or perhaps an workaround with the vector to prevent pointers from becoming invalidated? What do you think?