STL: list & list知识点

心已赠人 2022-03-29 04:16 280阅读 0赞

描述

写一个程序完成以下命令：  
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;
    }

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbnlhbndlbm1lbmc_size_16_color_FFFFFF_t_70][]

> list知识点

list是一个线性双向链表结构，它的数据由若干个节点构成，每一个节点都包括一个信息块（即实际存储的数据）、一个前驱指针和一个后驱指针。它无需分配指定的内存大小且可以任意伸缩，这是因为它存储在非连续的内存空间中，并且由指针将有序的元素链接起来。由于其结构的原因，list 随机检索的性能非常的不好，因为它不像vector 那样直接找到元素的地址，而是要从头一个一个的顺序查找，这样目标元素越靠后，它的检索时间就越长。检索时间与目标元素的位置成正比。虽然随机检索的速度不够快，但是它可以迅速地在任何节点进行插入和删除操作。因为list 的每个节点保存着它在链表中的位置，插入或删除一个元素仅对最多三个元素有所影响，不像vector 会对操作点之后的所有元素的存储地址都有所影响，这一点是vector 不可比拟的。

![849009-20160203142350538-1403083351.png][]

list 的特点：

(1) 不使用连续的内存空间这样可以随意地进行动态操作；  
(2) 可以在内部任何位置快速地插入或删除，当然也可以在两端进行push 和pop 。  
(3) 不能进行内部的随机访问，即不支持\[ \] 操作符和vector.at() ；  
(4) 相对于verctor 占用更多的内存。

参考链接：[https://www.cnblogs.com/loleina/p/5179677.html][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][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;
    }

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbnlhbndlbm1lbmc_size_16_color_FFFFFF_t_70 1][]

> 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;
    }

![20190107222915293.png][]

> 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;
    }

![2019010722301692.png][]

例题1：链表：约瑟夫问题 （两种解法）[https://blog.csdn.net/yanyanwenmeng/article/details/86020093][https_blog.csdn.net_yanyanwenmeng_article_details_86020093]

例题2：链表：删除数组中的元素 STL[https://blog.csdn.net/yanyanwenmeng/article/details/86020490][https_blog.csdn.net_yanyanwenmeng_article_details_86020490]

例题2：动态链表：统计学生信息 [https://blog.csdn.net/yanyanwenmeng/article/details/86020774][https_blog.csdn.net_yanyanwenmeng_article_details_86020774]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbnlhbndlbm1lbmc_size_16_color_FFFFFF_t_70]: /images/20220329/c928c69ecfab4595b6f2dc51300f3007.png
[849009-20160203142350538-1403083351.png]: /images/20220329/9a4be237e1c74a75aab93a7049e118f5.png
[https_www.cnblogs.com_loleina_p_5179677.html]: https://www.cnblogs.com/loleina/p/5179677.html
[https_www.cnblogs.com_ckings_p_3677561.html]: https://www.cnblogs.com/ckings/p/3677561.html
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbnlhbndlbm1lbmc_size_16_color_FFFFFF_t_70 1]: /images/20220329/fa686637d5f94d6da9d3bbe30126582a.png
[20190107222915293.png]: /images/20220329/fa85cca183fe4b4286f722f4d5c3c0a2.png
[2019010722301692.png]: /images/20220329/4adbae7374af410293dad770c2aab83a.png
[https_blog.csdn.net_yanyanwenmeng_article_details_86020093]: https://blog.csdn.net/yanyanwenmeng/article/details/86020093
[https_blog.csdn.net_yanyanwenmeng_article_details_86020490]: https://blog.csdn.net/yanyanwenmeng/article/details/86020490
[https_blog.csdn.net_yanyanwenmeng_article_details_86020774]: https://blog.csdn.net/yanyanwenmeng/article/details/86020774