STL: list & list知识点
描述
写一个程序完成以下命令：
new id ——新建一个指定编号为id的序列(id<10000)
add id num——向编号为id的序列加入整数num
merge id1 id2——合并序列id1和id2中的数，并将id2清空
unique id——去掉序列id中重复的元素
out id ——从小到大输出编号为id的序列中的元素，以空格隔开
输入
第一行一个数n，表示有多少个命令( n＜＝２０００００)。以后n行每行一个命令。
输出
按题目要求输出。
样例输入
16 new 1 new 2 add 1 1 add 1 2 add 1 3 add 2 1 add 2 2 add 2 3 add 2 4 out 1 out 2 merge 1 2 out 1 out 2 unique 1 out 1
样例输出
1 2 3 1 2 3 4 1 1 2 2 3 3 4 1 2 3 4
#include<cstdio>
#include<list>
#include<string>
#include<iostream>
using namespace std;
int n,id,num;
string s;
list<int> a[200005];
list<int>::iterator j;
int main()
{
scanf("%d",&n);
while(n--)
{
cin >> s;
if(s == "new") scanf("%d",&id);
if(s == "add") //加入整数
{
scanf("%d%d",&id,&num);
a[id].push_back(num);
}
if(s == "merge")//合并id1和id2，并将id2中的数清空
{
scanf("%d%d",&id,&num);
a[id].merge(a[num]);
}
if(s == "unique")
{
scanf("%d",&id);
a[id].sort();//去重之前需要从小到大排序
a[id].unique();
}
if(s == "out")
{
scanf("%d",&id);
if(!a[id].empty())//遍历从小到大输出
{
a[id].sort();
for(j = a[id].begin(); j != a[id].end(); ++j)
{
printf("%d ",*j);
}
printf("\n");
}
else//如果是空的，就输出空行
printf("\n");
}
}
return 0;
}
list知识点
list是一个线性双向链表结构，它的数据由若干个节点构成，每一个节点都包括一个信息块（即实际存储的数据）、一个前驱指针和一个后驱指针。它无需分配指定的内存大小且可以任意伸缩，这是因为它存储在非连续的内存空间中，并且由指针将有序的元素链接起来。由于其结构的原因，list 随机检索的性能非常的不好，因为它不像vector 那样直接找到元素的地址，而是要从头一个一个的顺序查找，这样目标元素越靠后，它的检索时间就越长。检索时间与目标元素的位置成正比。虽然随机检索的速度不够快，但是它可以迅速地在任何节点进行插入和删除操作。因为list 的每个节点保存着它在链表中的位置，插入或删除一个元素仅对最多三个元素有所影响，不像vector 会对操作点之后的所有元素的存储地址都有所影响，这一点是vector 不可比拟的。
list 的特点：
(1) 不使用连续的内存空间这样可以随意地进行动态操作；
(2) 可以在内部任何位置快速地插入或删除，当然也可以在两端进行push 和pop 。
(3) 不能进行内部的随机访问，即不支持[ ] 操作符和vector.at() ；
(4) 相对于verctor 占用更多的内存。
参考链接：https://www.cnblogs.com/loleina/p/5179677.html
list的操作
迭代器:
begin()
返回迭代器开始(公共成员函数)
end()
返回迭代器结束(公共成员函数)
rbegin()
反向迭代器返回开始反向(公共成员函数)
rend()
反向迭代器返回反向结束(公共成员函数)
cbegin()
const_iterator回到开始(公共成员函数)
cend()
返回const_iterator结束(公共成员函数)
crbegin()
返回const_reverse_iterator逆转开始(公共成员函数)
crend()
返回const_reverse_iterator扭转结束(公共成员函数)
容量capacity:
empty()
测试容器是否为空(公共成员函数)
size()
返回的大小(公共成员函数)
max_size
返回最大大小(公共成员函数)
元素访问:
front()
访问第一个元素(公共成员函数)
back()
访问的最后一个元素(公共成员函数)
修饰符Modifiers:
assign()
新内容分配给容器(公共成员函数)
emplace_front()
在开始构建和插入元素(公共成员函数)
push_front()
插入元素开始(公共成员函数)
pop_front()
删除第一个元素(公共成员函数)
emplace_back()
最后构造和插入元素(公共成员函数)
push_back()
末尾添加元素(公共成员函数)
pop_back()
删除最后一个元素(公共成员函数)
emplace()
构造和插入元素(公共成员函数)
insert()
插入元素(公共成员函数)
erase()
删除元素(公共成员函数)
swap()
交换内容(公共成员函数)
resize()
改变大小(公共成员函数)
clear()
清空内容(公共成员函数)
操作:
splice()
将元素从列表中列出(公共成员函数)
remove()
删除元素与特定的值(公共成员函数)
remove_if()
删除元素满足条件(公共成员函数模板)
unique()
删除重复的值(公共成员函数)
merge()
合并排序的列表(公共成员函数)
sort()
排序元素的容器(公共成员函数)
reserve()
改变元素的顺序(公共成员函数)
Observers:
get_allocator()
得到分配器(公共成员函数)
参考链接：https://www.cnblogs.com/ckings/p/3677561.html
push_front & push_back
#include<stdio.h>
#include<iostream>
#include<list>
#include<string>
#include<algorithm>
using namespace std;
void PrintIt(string& StringToPoint)
{
cout << StringToPoint << endl;
}
int main()
{
list<string> test;
list<string>::iterator testiterator;
test.push_back("no");
test.push_back("march");
test.push_front("ok");
test.push_front("loleina");
test.push_front("begin");
test.push_back("end");
for (testiterator = test.begin(); testiterator != test.end(); ++testiterator)
{
cout << *testiterator << endl;
}
cout << "-------------" << endl;
for_each(test.begin(), test.end(), PrintIt);
cout << "-------------" << endl;
system("PAUSE");
return 0;
}
merge
#include <iostream>
#include <list>
#include <iomanip>
using namespace std;
int main()
{
// 有序数据
int A1[]={1,2,3,4,5,6};
int A2[]={2,4,6,8,9,10};
// 无序数据
int A3[]={1,2,3,4,6,9};
int A4[]={5,6,7,8,9,2};
//有序链表
list<int> iL1(A1, A1+6);
list<int> iL2(A2, A2+6);
//无序链表
list<int> iL3(A3, A3+6);
list<int> iL4(A4, A4+6);
iL1.merge(iL2);
iL3.merge(iL4);
list<int>::iterator it = iL1.begin();
while(it!=iL1.end())
{
cout<<setw(3)<<*it++;
}
cout<<endl;
it=iL3.begin();
while(it!=iL3.end())
{
cout<<setw(3)<<*it++;
}
cout<<endl;
system("pause");
return 0;
}count,count_if
#include<stdio.h>
#include<iostream>
#include<list>
#include<string>
#include<algorithm>
using namespace std;
class IsLoleina
{
public:
bool operator()(string& name)
{
return name == "loleina";
}
};
int main()
{
list<string> test;
list<int> score;
list<string>::iterator testiterator;
test.push_back("no");
test.push_back("march");
test.push_front("ok");
test.push_front("loleina");
test.push_front("begin");
test.push_back("end");
score.push_back(100);
score.push_back(90);
score.push_back(80);
score.push_back(70);
score.push_back(100);
score.push_back(20);
int countNum(0);
countNum= count(score.begin(), score.end(), 100);
cout << "there are " << countNum << " scores of 100" << endl;
cout << "-------------" << endl;
int countLoleina(0);
countLoleina=count_if(test.begin(), test.end(), IsLoleina());
cout << "there are " << countLoleina << " loleina" << endl;
system("PAUSE");
return 0;
}