http://gcc.gnu.org/bugzilla/show_bug.cgi?id=59508
--- Comment #2 from Oleg Endo <olegendo at gcc dot gnu.org> --- (In reply to Daniel Krügler from comment #1) > A conforming implementation cannot do that, unless the difference weren't > observable by the user (modulo the performance difference), i.e. it would > only be possible for containers that have neither user-defined value types > nor user-defined allocators. I don't understand why it would not be possible to do with user defined value types or user defined allocators. For example, in the current RB tree implementation each node (_Rb_tree_node_base) has a field that stores a red/black bit. It is possible to use the spare bits to store additional node information whether a node is the begin () node or end () node. This will work regardless of the value type or allocator, since the node type is implementation internal and not visible to the user. Could you please elaborate?