Thanks for your comments. Both options seems reasonable. I think the user of a splay_tree expects splaying as the default option, so I'm starting to think that avoiding const versions could be a better choice (generic code using non-const containers would work). Users that are sure about thread-safety can uncast the container before passing it to the algorithm. Anyway, I'm afraid my opinion might change again ;-)
I like this approach. A splay tree is inherently non-const. Attempting to support const operations is a mistake for a variety of reasons. Removing all const operations on a collection will have a number of negative consequences, but I'd like to believe that a lot of that is required when you have a collection that behaves like a splay tree. I can think of a bunch of ways of softening the blow to the STL collection concept, but they all revolve around hiding the fact that you don't want to do non-const lookups with a splay tree. I'd rather advertise that behavior rather than trying to hide it.