stl 容器选择 时间效率比较

  一.主角介绍 Container class templates Sequence containers:Vector (class template )Double ended queue (class template )List (class template )
Container adaptors:LIFO stack (class template )FIFO queue (class template )Priority queue (class template )
Associative containers:Set (class template )Multiple-key set (class template)Map (class template )Multiple-key map (class template )Bitset (class template) 二.比较表格

Member map

This is a comparison chart with the different member functions present on each of the different containers:

			Sequence containers			Associative containers
Headers
Members		complex
	constructor	*
	destructor	O(n)
	operator=	O(n)
iterators	begin	O(1)
	end	O(1)
	rbegin	O(1)
	rend	O(1)
capacity	size	*
	max_size	*
	empty	O(1)
	resize	O(n)
element access	front	O(1)
	back	O(1)
	operator[]	*
	at	O(1)
modifiers	assign	O(n)
	insert	*
	erase	*
	swap	O(1)
	clear	O(n)
	push_front	O(1)
	pop_front	O(1)
	push_back	O(1)
	pop_back	O(1)
observers	key_comp	O(1)
	value_comp	O(1)
operations	find	O(log n)
	count	O(log n)
	lower_bound	O(log n)
	upper_bound	O(log n)
	equal_range	O(log n)
unique members

Amortized complexity shown. Legend: O(1) constant < O(log n) logarithmic < O(n) linear; *=depends on container

来源：