A couple thoughts:

size takes O(n).  That's just depressing.  Really.

Do you think union, intersection, etc. could be supported?