[Bug libstdc++/59508] std::find could use specialized container's find

[olegendo at gcc dot gnu.org]

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?