Contenidors: resum
Aquesta pàgina resumeix les principals operacions dels contenidors del la llibreria estàndard de C++ que s'han descrit i en dóna la seva eficiència.
A totes les taules, size().
| Contenidor | Cost en el cas pitjor i mitjà | Espai | ||
|---|---|---|---|---|
| Consulta | Inserció | Esborrat | ||
| Pila `stack` | O(1) | O(1) | O(1) | O(n) |
| Cua `queue` | O(1) | O(1) | O(1) | O(n) |
| Cua de prioritats `priority_queue` | O(1) | O(log n) | O(log n) | O(n) |
| Contenidor | Cost en el cas pitjor | Cost en el cas mitjà | Espai | ||||
|---|---|---|---|---|---|---|---|
| Cerca | Inserció | Esborrat | Cerca | Inserció | Esborrat | ||
| Conjunt `set` | O(log n) | O(log n) | O(log n) | O(log n) | O(log n) | O(log n) | O(n) |
| Diccionari `map` | O(log n) | O(log n) | O(log n) | O(log n) | O(log n) | O(log n) | O(n) |
| Conjunt no ordenat `unordered_set` | O(n) | O(n) | O(n) | O(1) | O(1) | O(1) | O(n) |
| Diccionari no ordenat `unordered_map` | O(n) | O(n) | O(n) | O(1) | O(1) | O(1) | O(n) |
Lliçons.jutge.org
Jordi Petit, Jordi Cortadella
© Universitat Politècnica de Catalunya, 2025