std::vector

insert	find	push_back	erase
O(N+M)	O(N)	O(1)	O(N+M)
Number of inserted elements, and move elements	Number of inserted elements	Copy an element to the back	Number of deleted elements, and move elements

std::set

insert	find	push_back	erase
O(log(N))	O(log(N))	X	O(log(N))
Finding the suitable position in binary search tree	Finding the element in binary search tree		Finding the element in binary search tree

std::list

insert	find	push_back	erase
O(N)	O(N)	O(1)	O(1)
Linear search for the suitable position	Linear search for the element	Copy an element to the back	The given argument is an iterator. remove() is O(N)

std::map

insert	find	push_back	erase
O(log(N))	O(log(N))	O(1)	O(log(N))
Finding the suitable position in binary search tree	Finding the element in binary search tree	Copy an element to the back	Finding the element in binary search tree

Last updated: February 25, 2024