知识点
Adapter的定义,:将一个Class的接口转换成另一个Class的接口,使原本因接口不兼容而不能合作的Class可以一起运作。
STL里面主要有两种接配器(Adapter):容器接配器(Container Adapter)和迭代器接配器(Iterator Adapter):
Container Adapter:
最常用的容器接配器无非是queue和stack,从意义上来说,他们为底层的容器提供了一层包装,使得底层的容器只表现出这些接配器所定义的数据结构的功能。 这里假设底层容器是deque,双向开口,而且两端插入删除都能够实现O(1)的时间复杂的。当作为queue进行包装的时候deque就会封闭一端的插入操作,封闭另一端的删除操作,使得整个deque表现出FIFO的特性,在作为stack的时候同理。 可以看到Container Adapter做到的功能很直观,也很好理解,只是对于容器的一层包装,改变了数据结构的接口的同时方便了我们对其的理解和使用。
Iterator Adapter(#include
对于STL中iterator的使用最多的也就是begin(),end(),const_iterator,rbegin()等等,而在这里要讲的Iterator Adapter主要有三种: 分别是insert iterator,reverse iterator,iostream iterator。
- insert iterator:从定义上来讲,它的作用是将一般迭代器的赋值(assign)操作转变为插入(insert)操作。理解了这句话也就理解了insert iterator的本质。
- reverse iterator:显然作用是使得iterator方向相反,常和rbegin,rend一起使用
- iostream iterator:这种Adapter将iterator和输入输出流(可以是文件流)相关联,经常和copy函数联合使用
Iterator是一种抽象的设计概念《Design Patterns》其中对于iterator模式定义如下:提供一种方法,使之能够依序巡访某个聚合物(容器)所包含的各个元素,而又无需暴露该聚合物的内部表达方式。
因此,对于根据定义不允许顺序或随机访问的数据结构,迭代器没有任何意义。这就是堆栈和队列没有迭代器的原因。
unordered_map和map unordered_map存储机制是哈希表,,即unordered_map内部元素是无序的。
map是红黑树,map中的元素是按照二叉搜索树存储,进行中序遍历会得到有序遍历。
unordered_set和set unordered_set基于哈希表,是无序的。
set实现了红黑树的平衡二叉检索树的数据结构,插入元素时,它会自动调整二叉树的排列,把元素放到适当的位置,以保证每个子树根节点键值大于左子树所有节点的键值,小于右子树所有节点的键值;另外,还得保证根节点左子树的高度与右子树高度相等。
priority_queue:
Member functions | description |
---|---|
(constructor) | Construct priority queue |
empty | Test whether container is empty |
size | Return size |
top | Access top element |
push | Insert element |
emplace | Construct and insert element |
pop | Remove top element |
swap | Swap contents |
queue:
Member functions | description |
---|---|
(constructor) | Construct queue |
empty | Test whether container is empty |
size | Return size |
front | Access next element |
back | Access last element |
push | Insert element |
emplace | Construct and insert element |
pop | Remove next element |
swap | Swap contents |
The next element is the "oldest" element in the queue and the same element that is popped out from the queue when queue::pop is called.
stack:
Member functions | description |
---|---|
(constructor) | Construct stack |
empty | Test whether container is empty |
size | Return size |
top | Access next element |
push | Insert element |
emplace | Construct and insert element |
pop | Remove top element |
swap | Swap contents |
list:
Element access: | description |
---|---|
front | Access first element |
back | Access last element |
Modifiers: | description |
---|---|
assign | Assign new content to container |
emplace_front | Construct and insert element at beginning |
push_front | Insert element at beginning |
pop_front | Delete first element |
emplace_back | Construct and insert element at the end |
push_back | Add element at the end |
pop_back | Delete last element |
emplace | Construct and insert element |
insert | Insert elements |
erase | Erase elements |
swap | Swap content |
resize | Change size |
clear | Clear content |
Operations: | description |
---|---|
splice | Transfer elements from list to list |
remove | Remove elements with specific value |
remove_if | Remove elements fulfilling condition |
unique | Remove duplicate values |
merge | Merge sorted lists |
sort | Sort elements in container |
reverse | Reverse the order of elements |
Set
Member functions | description |
---|---|
(constructor) | Construct set |
(destructor) | Set destructor |
operator= | Copy container content |
Iterators | description |
---|---|
begin | Return iterator to beginning |
end | Return iterator to end |
rbegin | Return reverse iterator to reverse beginning |
rend | Return reverse iterator to reverse end |
cbegin | Return const_iterator to beginning |
cend | Return const_iterator to end |
crbegin | Return const_reverse_iterator to reverse beginning |
crend | Return const_reverse_iterator to reverse end |
Capacity | description |
---|---|
empty | Test whether container is empty |
size | Return container size |
max_size | Return maximum size |
Modifiers | description |
---|---|
insert | Insert element |
erase | Erase elements |
swap | Swap content |
clear | Clear content |
emplace | Construct and insert element |
emplace_hint | Construct and insert element with hint |
Observers | description |
---|---|
key_comp | Return comparison object |
value_comp | Return comparison object |
Operations | description |
---|---|
find | Get iterator to element |
count | Count elements with a specific value |
lower_bound | Return iterator to lower bound |
upper_bound | Return iterator to upper bound |
equal_range | Get range of equal elements |
Allocator: get_allocator Get allocator