Perché la complessità del contenitore di mappe C++ STL O (log (n))?

Question

Per contenitori C++ STL come vector e list, la complessità della ricerca di elementi e l'inserimento o la rimozione di essi è autoesplicativa. Tuttavia, per il contenitore map, anche se so dalla mia lettura che la complessità/le prestazioni di accesso e inserimento è O (log (n)), non riesco a calcolare perché. Chiaramente non capisco le mappe tanto quanto ho bisogno, quindi qualche chiarimento su questo argomento sarebbe molto apprezzato.

Answer 1

Gli elementi di una mappa o di un set sono contenuti in una struttura ad albero; ogni volta che esamini un nodo dell'albero, determini se l'elemento che stai cercando di trovare/inserire è minore o maggiore del nodo. Il numero di volte che devi fare questo (per un albero correttamente bilanciato) è log2 (N) perché ogni confronto elimina metà delle possibilità.

Answer 2

Come punti slavik262, le mappe vengono solitamente implementate con alberi rosso-neri, che sono auto-bilanciati. Controllare la complessità di un albero rosso-nero ad esempio nello wikipedia Non conosco alcuna implementazione di una mappa con un albero binario; se Mark Ransom ne sa uno, sarei lieto di sapere quale.