Comment by adunsmoor

Intel's Threaded Building Blocks (http://threadingbuildingblocks.org) has a very nice collection of threaded data structures and algorithms.

I've found the performance to be quite good and the interfaces are compatible with STL in most cases which can be useful.