The standard's requirements for the standard library types don't imply any corresponding requirement for types you define yourself. If you want to write a container which can't reasonably do O(1) size() then you just don't do O(1) size(). If such a container was added to the standard library, the standard library's Container requirements will be adjusted to permit that.