Do I need to protect read access to an STL container in a multithreading environment?
Yes, the read threads will need some sort of mutex control, otherwise the write will change things from under it.
A reader/writer mutex should be enough. But strictly speaking this is an implmentation-specific issue. It's possible that an implementation may have mutable members even in const objects that are read-only in your code.
Checkout the concurrent containers provided by Intel's Open Source Threading Building Blocks library. Look under "Container Snippets" on the Code Samples page for some examples. They have concurrent / thread-safe containers for vectors, hash maps and queues.
I don't believe the STL containers are thread-safe, as there isn't a good way to handle threads cross-platform. The call to size() is simple, but it still needs to be protected.
This sounds like a great place to use read-write locks.