STL 容器

STL Containers,STL容器，他用来存储一组对象，在存储对象上，比较灵活。
容器管理着这些元素的存储，并且提供了一些方法直接的去访问或者提供iterators(reference objects with similar properties to pointers).
我们经常使用的重写容器的一些class有如下：
动态数组 (vector),队列(queue), 堆 (stack), 栈 (priority_queue), 链表(list), 树 (set), map(map)...
这些容器内部都有有些方法，在实际应用中，我们应该根据这些容器的内部方法的使用效率来决定。比如插入删除，链表等高效一些

 
stack, queue 和priority_queue 被实现为容器的适配器。

 
容器适配器不完全是容器类，对依赖的一些容器类，提供了一些特殊结构，比如用deque or list去处理。其他的容器类被封装成气元素方法的一些方法使用
 

容器类
顺序容器 ：
Sequence containers:

vector
Vector
 (class template )



deque
Double
 ended queue (class template )



list
List
 (class template )


Container adaptors:

stack
LIFO
 stack (class template )



queue
FIFO
 queue (class template )



priority_queue
Priority
 queue (class template)


Associative containers:

set
Set
 (class template )



multiset
Multiple-key
 set (class template)



map
Map
 (class template )



multimap
Multiple-key
 map (class template )



bitset
Bitset
 (class template)


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



Sequence
 containers
Associative containers


Headers
<vector>
<deque>
<list>
<set>
<map>
<bitset>


Members
complex
vector
deque
list
set
multiset
map
multimap
bitset


constructor
*
constructor
constructor
constructor
constructor
constructor
constructor
constructor
constructor


destructor
O(n)
destructor
destructor
destructor
destructor
destructor
destructor
destructor


operator=
O(n)
operator= 
operator= 
operator= 
operator= 
operator= 
operator= 
operator= 
operators


iterators
begin
O(1)
begin
begin
begin
begin
begin
begin
begin


end
O(1)
end
end
end
end
end
end
end


rbegin
O(1)
rbegin
rbegin
rbegin
rbegin
rbegin
rbegin
rbegin


rend
O(1)
rend
rend
rend
rend
rend
rend
rend


capacity
size
*
size
size
size
size
size
size
size
size


max_size
*
max_size
max_size
max_size
max_size
max_size
max_size
max_size


empty
O(1)
empty
empty
empty
empty
empty
empty
empty


resize
O(n)
resize
resize
resize


element
 access
front
O(1)
front
front
front


back
O(1)
back
back
back


operator[]
*
operator[] 
operator[] 
operator[] 
operator[] 


at
O(1)
at
at


modifiers
assign
O(n)
assign
assign
assign


insert
*
insert
insert
insert
insert
insert
insert
insert


erase
*
erase
erase
erase
erase
erase
erase
erase


swap
O(1)
swap
swap
swap
swap
swap
swap
swap


clear
O(n)
clear
clear
clear
clear
clear
clear
clear


push_front
O(1)
push_front
push_front


pop_front
O(1)
pop_front
pop_front


push_back
O(1)
push_back
push_back
push_back


pop_back
O(1)
pop_back
pop_back
pop_back


observers
key_comp
O(1)
key_comp
key_comp
key_comp
key_comp


value_comp
O(1)
value_comp
value_comp
value_comp
value_comp


operations
find
O(log
 n)
find
find
find
find


count
O(log
 n)
count
count
count
count
count


lower_bound
O(log
 n)
lower_bound
lower_bound
lower_bound
lower_bound


upper_bound
O(log
 n)
upper_bound
upper_bound
upper_bound
upper_bound


equal_range
O(log
 n)
equal_range
equal_range
equal_range
equal_range


unique
 members
capacity reserve
splice remove remove_if unique merge sort reverse
set reset flip to_ulong to_string test any none


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

Container adaptors:

Container
 Adaptors

Headers
<stack>
<queue>


Members
stack
queue
priority_queue


constructor
*
constructor
constructor
constructor


capacity
size
O(1)
size
size
size


empty
O(1)
empty
empty
empty


element
 access
front
O(1)
front


back
O(1)
back


top
O(1)
top
top


modifiers
push
O(1)
push
push
push


pop
O(1)
pop
pop
pop