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)$

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