STL : 单向链表 Forward_list 与 双向链表 List
目录
Forward_list
Member functions
List
Elements access
Modifiers
Operations
Observes
Forward_list
-
#include using namespace std;
-
单链表：数据的存储位置是分散的、随机的，整个链表的数据的线性关系通过指针来维持；
-
擅长在序列的任何位置进行元素的插入或删除操作，访问元素效率低；
-
只能从前向后遍历，只提供前向迭代器；
-
存储相同个数的同类型元素，耗用的内存空间更少，空间利用率高。
Member functions
| Name | Roel | Notice |
|---|---|---|
| cbefore_begin | 和 before_begin 功能相同，在原有基础上增加了 const 属性 | before_begin( ) : 返回前向迭代器，指向第一个元素之前的位置 |
| cbegin | 和 begin 功能相同，在原有基础上增加了 const 属性 | begin( ) : 返回前向迭代器，指向第一个元素的位置 |
| cend | 和 end 功能相同，在原有基础上增加了 const 属性 | end( ) : 返回前向迭代器，指向最后一个元素之后的位置 |
| assign | 用新元素替换容器中的原有内容 | |
| emplace_front | 在容器头部生成一个元素，和 push_front 相同，效率更高 | push_front( ) : 容器头部插入一个元素 |
| emplace_after | 和 insert_after 功能相同，但效率更高 | insert_after( ) : 指定位置之后插入一个新元素，并返回一个指向新元素的迭代器 |
| erase_after | 删除容器中某个指定位置或区域内的所有元素 | |
| remove_if | 删除容器中满足条件的元素 | remove(val) : 删除容器中所有等于 val 的元素 |
| merge | 合并两个事先已排好序的容器，且合并之后的容器依然是有序的 | |
| advance | 容器前向单步移动 | 除了使用 ++ 运算符，还可以advance(it, 2); |
List
-
#include; using namespace std;
-
双向链表 ：元素存储在连续的列表容器中，封装：链表；
-
动态存储分配，由一系列结点（数据域、指针域）构成；
-
支持对任意位置的插入、删除；
-
支持 ++ / -- 双向访问，不支持 += / -= 随机访问；
-
按顺序访问，遍历速度没有数组快，占用空间比数组大；
-
内存空间是不连续的，通过指针来访问访问数据，
-
List 接口函数介绍。
Elements access
| Name | Role | Notice |
|---|---|---|
| front | 返回第一个元素的引用 | |
| back | 返回最后一个元素的引用 |
Modifiers
| Name | Role | Notice |
|---|---|---|
| assign | 赋值，替换旧元素为列表容器添加新元素 | assign(beg, end) assign(n, elem) |
emplace_front c11 |
列表开头插入新元素，容器大小增加 1（就地构造） | |
| push_front | 列表开头插入新元素，容器大小增加 1 | |
| pop_front | 列表开头删除元素，容器大小减少 1 | |
emplace_back c11 |
列表末尾插入新元素，容器大小增加 1（就地构造） | |
| push_back | 列表末尾插入新元素，容器大小增加 1 | |
| pop_back | 列表末尾删除元素，容器大小减少 1 | |
emplace c11 |
指定位置插入新元素来扩展列表，返回一个指向新插入元素的随机访问迭代器 | |
| insert | 指定位置插入一个或多个元素 | insert(pos,beg,end) |
| erase | 指定位置删除一个元素，返回指向下一参数的随机访问迭代器 | rease(beg, end) erase(pos) |
| swap | 与另一相同类型的列表交换列表的内容 | |
| resize | 重新设置列表大小（尺寸更大则补充，int 默认 0） | resize(num, elem) |
| clear | 删除列表所有元素，使其大小为 0 |
Operations
| Name | Role | Notice |
|---|---|---|
| splice | 部分或全部删除源列表的内容，并插入到目的 list | |
| remove | 从列表中删除与作为函数参数给出的值相对应的所有值 | remove(elem) |
| remove_if | 从列表中删除与谓词或条件相对应的所有值 | |
| unique | 从列表中删除所有连续出现的重复元素 | |
| merge | 以递增的顺序合并两个已排序的列表。compare : 比较器，实现内部比较合并列表。 | merge(list, compare) |
| sort | 按递增顺序排列给定列表的元素（仅在列表中移动） | |
| reverse | 反转列表中元素的顺序 |
Observes
| Name | Role | Notice |
|---|---|---|
| get_allocator | 返回与列表关联的分配器 | 函数不抛出异常 |
