January 1997/Standard C/C++/Table 1

Table 1: Time complexity of operations on various containers

	vector	deque	list	set/map
insert/erase	N	N	constant	log N
prepend	(N)	constant	constant	(log N)
find(val)	(N)	(N)	(N)	log N
X[N]	constant	constant	(N)	(N)
pointers	0	1	2	3

NOTES: (N) or (log N) -- time complexity for operations not directly
supported by member functions.