目录
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; //0
cout << lt.size() << endl; //5
return 0;
}
元素访问
#include <iostream>
#include <list>
int main()
{
const list<int> lt(5, 2);
cout << lt.front() << endl; //2
cout << lt.back() << endl; //2
return 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 4
lt.push_back(5);
print(lt); //0 1 2 3 4 5
lt.pop_front();
print(lt); //1 2 3 4 5
lt.pop_back();
print(lt); //1 2 3 4
lt.insert(++lt.begin(), 10);
print(lt); //1 10 2 3 4
lt.erase(--lt.end());
print(lt); //1 10 2 3
list<int> lt2;
lt2.assign(lt.begin(), lt.end());
print(lt2); //1 10 2 3
lt.clear();
cout << lt.size() << endl; // 0
return 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 4
lt.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 1
lt.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 1
less<int> ls;
lt.sort(ls);
print(lt); //1 2 3 4
greater<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 5
lt.unique(); // 把相邻的重复去掉, 配合sort可以达到去重的功能
print(lt); //1 2 3 4 5
return 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 3
return 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 3
lt.remove_if(Cmp());
print(lt); //4 2 3
return 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 5
print(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 4
print(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 4
print(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 4
print(lt2); //空
}