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, $n$ denota el nombre d’elements dins del contenidor, és a dir, el seu 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)$


Fòrum







Lliçons.jutge.org
Jordi Petit, Jordi Cortadella
Universitat Politècnica de Catalunya, 2019

Prohibit copiar. Tots els drets reservats.
No copy allowed. All rights reserved.