L'approccio più semplice è usare std::set se non possono mai essere in lista due elementi equivalenti (cioè tali che, per l'ordinamento debole D usato, x D y è falso e y D x è pur esso falso). Altrimenti si può ricorrere a std::multiset in quanto, in generale, non si può escludere che interessi anche tenere nel contenitore elementi fra loro equivalenti. In questo caso e` da notare che l'ordinamento imposto da multiset NON è "stabile" (elementi equivalenti possono trovarsi in qualsiasi ordine fra loro), quindi può darsi che convenga in ogni caso (se interessa la "stabilità") usare un set, arricchendo gli elementi di un identificatore unico (ad esempio, l'ordine progressivo di arrivo nel contenitore) in modo da escludere l'equivalenza.
E l'utilizzo della funzione sort della libreria standard ?
Normalmente list<>::sort è una accurata implementazione di mergesort, mentre l'algoritmo sort (non adatto a list<>, bensì a contenitori come vector<>, con iteratori random-access) usa l'eccellente algoritmo di Singleton (dal cognome del suo autore, nulla a che vedere con la pattern detta "Singleton"). L'importante è la garanzia che sort è O(N logN) anche nel caso peggiore (qsort, invece, garantisce O(N logN) solo come media, ed è O(N quadrato) nel caso peggiore). Richiamare l'algoritmo di ordinamento ad ogni inserimento è troppo oneroso in quanto la somma per i da 1 a N di i log(i) è più che quadratico in N, quindi costruire una lista di N elementi con una chiamata a sort ad ogni elemento inserito avrebbe un costo assolutamente disastroso.
Esiste un altro metodo ?
Sì, c'è un approccio generale, decisamente molto sofisticato, basato sull'osservazione che, nel 99% dei casi in cui un analista ingenuo potrebbe pensare che un dato contenitore "deve essere sortato in qualsiasi momento", esso, in realtà, deve esserlo solo in certi specifici momenti di "osservabilità" -- i momenti in cui quel contenitore viene "percorso" (e deve fornire i suoi elementi in quel momento nel giusto ordine)ovvero "frugato" (ricerca di un elemento, ad esempio con binary_search). A questo si unisce il fatto che, nel mondo reale, molto spesso i contenitori "alternano" fasi di "inserimento", in cui la grande maggioranza delle operazioni sono appunto inserimenti di nuovi elementi (o, in certi casi, cancellazione o alterazione di elementi esistenti), e fasi di "percorso/fruga", in cui la grande maggioranza delle operazioni non alterano il contenitore. I "contenitori bifasici" sono basati sull'idea di trarre tutto il vantaggio da questo tipo di "alternanza"; per chiarire, un modello semplificato della completa pattern "contenitore bifasico" potrebbe essere semplicemente:

• se arrivano nuovi elementi o altri "editing" (alterazioni/cancellazioni), entrare in "fase di alterazione" se già il contenitore non vi si trovava, e non apportare modifiche al "corpo principale del contenitore" (che è sortato), bensì accumulare le richieste di editing in un buffer separato
• se arriva una richiesta di "percorso" o "fruga", entrare in "fase di percorso" se già il contenitore non vi era, e quindi apportare tutti gli editing "pending" ripristinando il "corpo principale" del contenitore prima di concedere l'accesso "di fruga" (percorso o ricerca che sia)

Con questo approccio semplificato, la prima richiesta "di fruga" dopo una sequenza di richieste "di editing" può subire un notevole rallentamento, anche se il "costo ammortizzato" resta potenzialmente molto buono;fra i raffinamenti che portano da questo approccio più semplice, a quello "completo" del pattern, vi è lo sfruttamento delle caratteristiche delle "heap" per ammortizzare più uniformemente il costo (migliora il ritardo di caso peggiore, con un lieve appesantimento del ritardo medio e quindi lieve peggioramento del throughput); inoltre, questo raffinamento permette di "irrobustire" il passaggio di fase ("introdurre una isteresi"), così che una occasionale richiesta "di fruga" ad un contenitore "in fase di editing", o viceversa, non forza ancora la commutazione di fase, bensì può venire soddisfatta pur essendo "nella fase sbagliata".
Naturalmente, questa enorme complessità implementativa va giustificata nei fatti, verificando, anzitutto, che un approccio più semplice ed elementare non sia già del tutto soddisfacente.
Come si diceva più sopra l'approccio più semplice in assoluto è usare un multiset (std::multiset, naturalmente): questo è mantenuto in ordine ad ogni insert (ogni insert costa log K, quindi il costo di mantenimento è l'"imbattibile in astratto" N log N,o meglio somma per i da 1 a N di log N, leggermente inferiore ma asintoticamente equivalente), esattamente come da specifiche. Qualsiasi approccio più sofisticato puo` battere questo se e solo se e` in grado di trarre vantaggio, anche solo "euristicamente", da caratteristiche di non-ergodicità degli inserimenti (v. sopra ad esempio il concetto di "fasi"), o da altri trucchi (radix sort, ecc).
[A volte, inoltre, il semplice fatto di poter passare a multiset::insert un iteratore di "hint", se si ha già una idea di dove probabilmente si inserirà il nuovo elemento,può bastare per battere NlogN con un multiset: infatti, se "ci prendo sempre" con l'iteratore che passo, allora il costo di inserimento è ammortizzato costante, invece che log K...! Naturalmente, se l'iteratore di "hint" è "sbagliato", il tempo rischia di peggiorare, invece che di migliorare]