Aparentemente podrías hacer cualquiera de las dos cosas, pero lo primero es más común.

¿Por qué elegirías este último y cómo funciona?

Leo esto:http://www.drdobbs.com/cpp/stls-red-black-trees/184410531; Lo que me hizo pensar que lo hicieron. Dice:

insert_always es una variable de estado que le dice a rb_tree si se permiten varias instancias del mismo valor clave. Esta variable es establecida por el constructor y es utilizada por la STL para distinguir entre conjunto y multiset y entre map y multimap. set y map solo pueden tener una aparición de una clave en particular, mientras que multiset y multimap pueden tener múltiples apariciones.

Aunque ahora creo que no necesariamente significa eso. Todavía podrían estar usando contenedores.

Estoy pensando que todos los nodos con la misma clave tendrían que estar en una fila, porque o bien tienes que almacenar todos los nodos con la misma clave en el lado derecho o en el lado izquierdo. Entonces, si almacena nodos iguales a la derecha e inserta 1000 1s y uno 2, básicamente tendrá una lista enlazada, lo que arruinaría las propiedades del árbol rojo y negro.

¿Es la razón por la que no puedo encontrar mucho en eso que es solo una mala idea?