Consider trying ext/pdb/ version of splay tree

[mattyv]

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;

typedef tree<
int, // Key type.
null_type, // Mapped policy.
std::less, // Key comparison functor.
splay_tree_tag, // Specifies that we want a splay tree.
null_node_update // No node update policy.

plain_splay_tree;

[mattyv]

or even boost intrusive splay tree