目录
list介绍
list使用
list创建
list迭代器
容量操作
元素访问
修改元素
其他操作
list介绍
● list是可以在常数范围内在任意位置进行插入和删除的序列式容器，并且该容器可以前后双向迭代
● list的底层是双向链表结构，双向链表中每个元素存储在互不相关的独立节点中，在节点中通过指针指向其前一个元素和后一个元素
● list与forward_list非常相似：最主要的不同在于forward_list是单链表，只能朝前迭代，已让其更简单高 效。
● 与其他的序列式容器相比(array，vector，deque)，list通常在任意位置进行插入、移除元素的执行效率 更好。
● 与其他序列式容器相比，list和forward_list最大的缺陷是不支持任意位置的随机访问，比如：要访问list的第6个元素，必须从已知的位置(比如头部或者尾部)迭代到该位置，在这段位置上迭代需要线性的时间 开销；list还需要一些额外的空间，以保存每个节点的相关联信息(对于存储类型较小元素的大list来说这 可能是一个重要的因素)
list使用
list创建
list<int> lt1; // 无参构造
list<int> lt2(3, 2); // 3个2构造
vector<int> v(10, 2);
list<int> lt3(v.begin(), v.end()); // 迭代器区间构造
list<int> lt4(lt3); // 拷贝构造list迭代器
正向普通迭代器
#include <iostream>
#include <list>
int main()
{list<int> lt(5, 2); list<int>::iterator it = lt.begin();while(it != lt.end()){cout << *it << " "; //2 2 2 2 2 it++;}cout << endl;return 0;
}
正向const迭代器
#include <iostream>
#include <list>
int main()
{const list<int> lt(5, 2); list<int>::const_iterator it = lt.begin();while(it != lt.end()){cout << *it << " "; //2 2 2 2 2 it++;}cout << endl;return 0;
}
反向普通迭代器
#include <iostream>
#include <list>
int main()
{list<int> lt(5, 2); list<int>::reverse_iterator it = lt.rbegin();while(it != lt.rend()){cout << *it << " "; //2 2 2 2 2 it++;}cout << endl;return 0;
}
反向const迭代器
#include <iostream>
#include <list>
int main()
{const list<int> lt(5, 2); list<int>::const_reverse_iterator it = lt.rbegin();while(it != lt.rend()){cout << *it << " "; //2 2 2 2 2 it++;}cout << endl;return 0;
}
容量操作
#include <iostream>
#include <list>
int main()
{const list<int> lt(5, 2); cout << lt.empty() << endl; //0cout << lt.size() << endl; //5return 0;
}
元素访问
#include <iostream>
#include <list>
int main()
{const list<int> lt(5, 2); cout << lt.front() << endl; //2cout << lt.back() << endl; //2return 0;
}
修改元素
#include <iostream>
#include <list>
void print(list<int>& lt)
{for(auto& x : lt){cout << x << " ";}cout << endl;
}
int main()
{vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);list<int> lt(v.begin(), v.end());lt.push_front(0); print(lt); //0 1 2 3 4lt.push_back(5);print(lt); //0 1 2 3 4 5lt.pop_front();print(lt); //1 2 3 4 5lt.pop_back();print(lt); //1 2 3 4lt.insert(++lt.begin(), 10);print(lt); //1 10 2 3 4lt.erase(--lt.end()); print(lt); //1 10 2 3list<int> lt2;lt2.assign(lt.begin(), lt.end());print(lt2); //1 10 2 3lt.clear();cout << lt.size() << endl; // 0return 0;
}
其他操作
逆置链表
#include <iostream>
#include <list>
using namespace std;
int main()
{list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);print(lt); //1 2 3 4lt.reverse(); // 逆置链表print(lt); //4 3 2 1
}
排序链表
#include <iostream>
#include <list>
using namespace std;
int main()
{list<int> lt;lt.push_back(2);lt.push_back(3);lt.push_back(4);lt.push_back(1);print(lt); //2 3 4 1lt.sort(); //默认是升序print(lt); //1 2 3 4
}
● 算法库algorithm中也提供了sort函数，但是我们无法直接使用sort函数去排序链表，因为sort函数要求传递的迭代器是随机访问迭代器，而list不支持随机访问迭代器，只有双向迭代器
● list中的sort函数提供了两个重载接口，无参的sort默认是升序，因此不传递任何参数排序的结果就是升序
● 而我们也可以传参，去调用有参的sort，就可以控制升序还是降序了，comp是类模版参数，可以传递类对象，比如less/greater，使用仿函数实现升序/降序
#include <iostream>
#include <list>
using namespace std;
int main()
{list<int> lt;lt.push_back(2);lt.push_back(3);lt.push_back(4);lt.push_back(1);print(lt); //2 3 4 1less<int> ls;lt.sort(ls);print(lt); //1 2 3 4greater<int> gt;lt.sort(gt);print(lt); //4 3 2 1
}
unique
● unique接口可以将链表相邻重复元素去重，如果搭配sort使用，就可以实现将链表所有元素去重
#include <iostream>
#include <list>
using namespace std;
int main()
{list<int> lt;lt.push_back(4);lt.push_back(1);lt.push_back(1);lt.push_back(2);lt.push_back(5);lt.push_back(5);lt.push_back(1);lt.push_back(3);lt.sort();print(lt); //1 1 1 2 3 4 5 5lt.unique(); // 把相邻的重复去掉, 配合sort可以达到去重的功能print(lt); //1 2 3 4 5return 0;
}remove
● remove接口可以将指定的某个元素从链表中全部删除
#include <iostream>
#include <list>
using namespace std;
int main()
{list<int> lt;lt.push_back(4);lt.push_back(1);lt.push_back(1);lt.push_back(2);lt.push_back(5);lt.push_back(5);lt.push_back(1);lt.push_back(3);print(lt); //4 1 1 2 5 5 1 3 lt.remove(1);print(lt); //4 2 5 5 3return 0;
}
remove if
● remove if 接口可以将满足条件的所有元素从链表中删除，因此remove if 的参数是类对象，可以传递函数对象，也可以传递仿函数对象
bool cmp(const int& val)
{return val == 1;
}class Cmp
{
public:bool operator()(const int& val){return val == 5;}
};int main()
{list<int> lt;lt.push_back(4);lt.push_back(1);lt.push_back(1);lt.push_back(2);lt.push_back(5);lt.push_back(5);lt.push_back(1);lt.push_back(3);print(lt); //4 1 1 2 5 5 1 3 lt.remove_if(cmp);print(lt); //4 2 5 5 3lt.remove_if(Cmp());print(lt); //4 2 3return 0;
}merge
● lt1.merge(lt2)，该操作会移除掉lt2的所有元素尾插到lt1链表的后面，完成两个链表的合并
#include <iostream>
#include <list>
using namespace std;
int main()
{list<int> lt1;lt1.push_back(1);lt1.push_back(2);lt1.push_back(3);lt1.push_back(4);list<int> lt2;lt1.push_back(8);lt1.push_back(7);lt1.push_back(6);lt1.push_back(5);lt1.merge(lt2);print(lt1); //1 2 3 4 8 7 6 5print(lt2); //空return 0;
}splice
#include <iostream>
#include <list>
using namespace std;
int main()
{list<int> lt1;lt1.push_back(1);lt1.push_back(2);lt1.push_back(3);lt1.push_back(4);list<int> lt2;lt2.push_back(10);lt2.push_back(20);lt2.push_back(30);lt2.push_back(40);list<int>::iterator it = lt1.begin();++it;lt1.splice(it, lt2); // 将lt2嫁接到lt1第2个位置之后, lt2就为空了!print(lt1); //1 10 20 30 40 2 3 4print(lt2); //空
}
#include <iostream>
#include <list>
using namespace std;
int main()
{list<int> lt1;lt1.push_back(1);lt1.push_back(2);lt1.push_back(3);lt1.push_back(4);list<int> lt2;lt2.push_back(10);lt2.push_back(20);lt2.push_back(30);lt2.push_back(40);lt1.splice(lt1.begin(), lt2, lt2.begin()); // 将lt2的第一个节点接到lt1开始位置print(lt1); // 10 1 2 3 4print(lt2); // 20 30 40
}#include <iostream>
#include <list>
using namespace std;
int main()
{list<int> lt1;lt1.push_back(1);lt1.push_back(2);lt1.push_back(3);lt1.push_back(4);list<int> lt2;lt2.push_back(10);lt2.push_back(20);lt2.push_back(30);lt2.push_back(40);lt1.splice(lt1.begin(), lt2, lt2.begin(), lt2.end()); // 将lt2的全部接到lt1开始print(lt1); //10 20 30 40 1 2 3 4print(lt2); //空
}
