Aparentemente você poderia fazer qualquer um, mas o primeiro é mais comum.

Por que você escolheria o último e como funciona?

Eu li isso:http://www.drdobbs.com/cpp/stls-red-black-trees/184410531; o que me fez pensar que eles fizeram isso. Diz:

insert_always é uma variável de status que informa ao rb_tree se várias instâncias do mesmo valor de chave são permitidas. Essa variável é definida pelo construtor e é usada pelo STL para distinguir entre set e multiset e entre map e multimap. set e map só podem ter uma ocorrência de uma chave particular, enquanto multiset e multimap podem ter múltiplas ocorrências.

Embora agora eu acho que isso não significa necessariamente isso. Eles ainda podem estar usando contêineres.

Eu estou pensando que todos os nós com a mesma chave teriam que estar em uma linha, porque você tem que armazenar todos os nós com a mesma chave no lado direito ou no lado esquerdo. Então, se você armazenar nós iguais à direita e inserir 1000 1s e um 2, você basicamente teria uma lista vinculada, o que arruinaria as propriedades da árvore preta vermelha.

É a razão pela qual eu não consigo encontrar muito sobre isso que é apenas uma má ideia?