其实在日常中, 链表的题目做的比较多, 但是使用 STL 自带链表的还是比较少, 所以里面的一些 API 不大熟悉. 这边也简要介绍一些.
基本的一些 API
先列举的这些和上面几篇用法几乎一样, 所以不再累述.
赋值相关
- list(beg,end);// 构造函数将 [beg, end) 区间中的元素拷贝给本身.
- list(n,elem);// 构造函数将 n 个 elem 拷贝给本身.
- list(const list &lst);// 拷贝构造函数.
- assign(beg, end);// 将 [beg, end) 区间中的数据拷贝赋值给本身.
- assign(n, elem);// 将 n 个 elem 拷贝赋值给本身.
- list& operator=(const list &lst);// 重载等号操作符
- swap(lst);// 将 lst 与本身的元素互换
插入, 删除相关
- push_back(elem);// 在容器尾部加入一个元素
- pop_back();// 删除容器中最后一个元素
- push_front(elem);// 在容器开头插入一个元素
- pop_front();// 从容器开头移除第一个元素
- insert(pos,elem);// 在 pos 位置插 elem 元素的拷贝, 返回新数据的位置.
- insert(pos,n,elem);// 在 pos 位置插入 n 个 elem 数据, 无返回值.
- insert(pos,beg,end);// 在 pos 位置插入 [beg,end) 区间的数据, 无返回值.
- clear();// 移除容器的所有数据
- erase(beg,end);// 删除 [beg,end) 区间的数据, 返回下一个数据的位置.
- erase(pos);// 删除 pos 位置的数据, 返回下一个数据的位置.
- remove(elem);// 删除容器中所有与 elem 值匹配的元素.
list 提供了可以从头部或尾部直接加入元素, 也可以在头部或尾部直接删除元素.
把 remove 函数拿出来讲一下, 如何删除自定义数据. 如果我们的数据是内置类型, 那很好删除, 找到该 elem, 用 == 比较, 为真就表示找到了, 进行删除. 而自定义数据用 == 是不能直接比较的, 我们应该先重载 ==, 再进行删除. 我们重载的时候, 要注意, 传入的参数都必须是 const 类型, 否则编译不会通过, 因为编译器发觉我们会有改变数据的风险, 导致比较结果出错!
大小操作
- size();// 返回容器中元素的个数
- empty();// 判断容器是否为空
- resize(num);// 重新指定容器的长度为 num,
若容器变长, 则以默认值填充新位置.
如果容器变短, 则末尾超出容器长度的元素被删除.
resize(num, elem);// 重新指定容器的长度为 num,
若容器变长, 则以 elem 值填充新位置.
如果容器变短, 则末尾超出容器长度的元素被删除.
这边的 size 函数有个特殊点:
GCC 下时间复杂度为 O(n).
VC 下时间复杂度为 O(1).
在 GCC 下, size 函数的复杂度为 O(n), 它是通过调用标准库的 distance(begin(),end())算法来计算长度的. 而在 VC 类的编译器下, 维护了一个成员变量_Mysize, 保存长度. 就可以直接查出来, 时间复杂度为 O(1).
这其实是一种取舍, 要先讲一下 list::splice 函数, 这是让两个不同的链表进行拼接的函数. GCC 为了维护这个函数, 使拼接后长度更容易计算, 因此没有给一个成员变量来保存大小, 如果给了, 那拼接后的长度是两个 size 相加吗? 不一定, 因为 splice 拼接方法有多种. 所以没有给出.
存取操作
- front();// 返回第一个元素.
- back();// 返回最后一个元素.
注意是直接返回元素.
STL 中 list 是一个双向循环链表
我们用一段代码来证明它是一个双向循环链表: 从头结点遍历 2 倍的长度单位, 看是否会循环再打印一次.
先说一下几个类型:
- // 链表结点类型
- list<int>::_Nodeptr node;
而结点类有三个成员: 下一节点指针, 上一节点指针, 数据:
- node->_Next;
- node->_Prev;
- node->_Myval;
再看例子:
- int main(){
- list<int> myList;
- for (int i = 0; i <10; i ++){
- myList.push_back(i);
- }
- list<int>::_Nodeptr node = myList._Myhead->_Next;
- for (int i = 0; i <myList._Mysize * 2;i++){
- cout << "Node:" << node->_Myval <<endl;
- node = node->_Next;
- if (node == myList._Myhead){
- node = node->_Next;
- }
- }
- return 0;
- }
首先我们用一个 for 循环, 将数据存进去.
然后我们用一个节点指向头结点的的下一节点. list 的头结点_Myhead 是不存任何东西的, 只是为了插入方便而已, 所以这么整. 所以我们要指向第一个有数据的节点.
当我们遍历一次链表长度时, 到达尾节点时, 若是循环链表, 则会再回到头部, 看一下执行结果:
可以清楚的看到, 我循环了 2 倍长度, 它遍历了两次. 所以, list 是一个循环链表.
list 的反转和排序函数
reverse 和 sort 函数
reverse 函数就是反转函数, 较为简单, 没什么特殊的. sort 函数排序也是一样, 默认从小到大排序.
而我们可以是指定排序顺序的. 有两种方法, 一种是回调函数的方法, 另一种是仿函数的方法.
现在假设我们有一个链表:
- list<int> myList;
- for (int i = 0; i <5; i++){
- myList.push_back(i);
- }
- list.sort();
我们执行完 sort 的结果, 会是从小到大排序的链表. 也就是说, 当 sort 的参数为空时, 会执行默认的排序, 那现在我们就给它传递一个参数, 改变排序规则.
现在就来介绍上述的两种方法.
回调函数方法
先写出这个回调函数:
- bool mycmp(int a, int b)
- {
- return a> b;
- }
返回值: bool.
参数: int 型(取决于你的链表存放的数据类型).
排序规则: 从大到小, 所以 return a> b;
我们针对整型进行大到小的排序, 所以, 我们要返回 a> b 即可.
随后, 我们再程序中执行:
mylist.sort(mycmp);
这样就行了, 就可以从大到小排序了.
仿函数方法
记住仿函数不是一个函数, 是一个类. 它通过重载 () 来生效. 因为底层中使用了大量的 cmp(a,b)这种形式来比较 a 和 b 的大小. 来看一下:
- class MyCmp
- {
- public:
- bool operator()(int a, int b)
- {
- return a> b;
- }
- };
同样的, 仿函数里面重载():
返回值: bool.
参数: int 型(取决于你的链表存放的数据类型).
排序规则: 从大到小, 所以 return a> b;
可以看到, 和回调函数的规则几乎一样.
调用形式为:
mylist.sort(MyCmp());
为什么多了一对小括号呢? 我们需要传入的是一个对象, 而回调函数传进去就直接是一个函数对象, 仿函数是一个类, 我们加一对括号生成一个匿名对象, 从而传递正确的参数.
下面看一个 reverse 和 sort 的使用例子:
- int main()
- {
- list<int> myList;
- for (int i = 0; i <5; i++){
- myList.push_back(i);
- }
- // 反转
- myList.reverse();
- list<int>::_Nodeptr node = myList._Myhead->_Next;
- cout <<"反转之后:" << endl;
- for (size_t i = 0; i < myList._Mysize; ++i)
- {
- cout << node->_Myval <<" ";
- node = node->_Next;
- }
- // 再排序(从小到大)
- myList.sort();
- node = myList._Myhead->_Next;
- cout <<endl << "默认排序:" << endl;
- for (size_t i = 0; i < myList._Mysize; ++i)
- {
- cout << node->_Myval <<" ";
- node = node->_Next;
- }
- // 再排序(从大到小)
- //myList.sort(mycmp); // 使用回调函数方法, 传入一个函数对象
- myList.sort(MyCmp()); // 使用仿函数方法, 传入一个匿名对象
- node = myList._Myhead->_Next;
- cout <<endl << "从大到小排序:" << endl;
- for (size_t i = 0; i < myList._Mysize; ++i)
- {
- cout << node->_Myval <<" ";
- node = node->_Next;
- }
- return 0;
- }
执行结果:
为什么不用标准库算法 sort 呢?
如果用系统提供的 sort, 那么参数就为迭代器:
sort(mylist.begin(),mylist.end());
但实际上不能完成的. 因为系统提供的 sort 函数对迭代器有要求: 必须是可以随机访问的迭代器! 而 list 容器不提供随机访问的能力, 所以不能使用. 但是往往这类东西都会自己实现一个 sort, 所以不用担心.
一些复杂需求排序
讲完刚刚指定排序规则的排序, 现在我们可以有更复杂的排序需求了:
若干学生, 优先按照成绩大到小排序, 成绩相同按照年龄小到大排序, 年龄相同按照姓名升序排序, 姓名相同按照班级降序排序.
这就是个不断比较的过程而已, 没什么特殊的地方, 回调函数如下:
- bool ComplicatedCmp(Stu &stu1, Stu &stu2)
- {
- if (stu1._iScore == stu2._iScore)
- {
- if (stu1._iAge == stu2._iAge)
- {
- if (stu1._strName == stu2._strName)
- {
- return stu1._iClass> stu2._iClass;
- }
- else
- {
- return stu1._strName <stu2._strName;
- }
- }
- else
- {
- return stu1._iAge < stu2._iAge;
- }
- }
- else
- {
- return stu1._iScore> stu2._iScore;
- }
- }
主函数:
- int main()
- {
- list<Stu> mylist;
- mylist.push_back(Stu("Tom", 4, 90, 13));
- mylist.push_back(Stu("Jerry", 5, 84, 11));
- mylist.push_back(Stu("Giao", 1, 99, 10));
- mylist.push_back(Stu("Fuck", 6, 35, 15));
- mylist.push_back(Stu("Bill", 2, 96, 17));
- mylist.push_back(Stu("Null", 2, 96, 16));
- mylist.push_back(Stu("Null", 0, 96, 17));
- mylist.sort(ComplicatedCmp);
- for (auto it = mylist.begin(); it != mylist.end(); ++it)
- {
- cout <<"Score:" << it->_iScore <<"Age:" << it->_iAge <<"Name:" << it->_strName <<"Class:" << it->_iClass << endl;
- }
- return 0;
- }
可以看到结果为:
已经按照我们想要的排序进行排序了.
来源: https://www.cnblogs.com/love-jelly-pig/p/9991863.html