1. Assumes that std::list<T>::empty() is an atomic operation.
2. Assumes it's safe to use separate locks for reading and writing, which std::list says nothing about. It probably screws up even in practice for at least the case where you have only one element in the list and two threads execute push() and pop() at the same time.
(it's a classical computer science problem with classical solution)
The probabilistic nature of the data structure lets them get those nice O(lg n) and O(1) expected times without the wide-ranging memory conflicts that slow down concurrent min-heaps. Some more basic info on skiplists for people who aren't familiar with them:
There are even designs for lock-free skiplist priorty queues, but they tend to be a little slower than the locking versions.
TAOMP ( http://www.amazon.com/The-Multiprocessor-Programming-Maurice... ) goes over this in great detail and is overall an excellent book.
The book is in Java, but C++11 has the required primitives (cross platform compare and set for integral types, a defined memory model) so you could follow allong in C++11.
I've found the performance to be quite good and the interfaces are compatible with STL in most cases which can be useful.