迭代器和非变异算法

实验目的：

本实验主要练习容器set、multiset、map、multimap的使用方法，插入迭代器、反向迭代器的用法，以及四种非变异算法的基本用法。

实验器材：

VScode

实验内容：

一．回顾以上四种容器相关的例题（不作为实验报告内容），例7.33作为实验报告内容。

二．练习课本第7章的例7.35、7.36，均作为实验报告内容。

三．练习第8章例8.1、8.3、8.6、8.9、8.10。8.3和8.10作为实验报告内容。

实验步骤：

7-28：

#include<iostream>

#include<set>

using?namespace?std;

typedef?multiset<int>ss;

void?display(ss&s){

? ? ss::iterator?it=s.begin();

? ? for(it;it!=s.end();it++){

? ? ? ? cout<<*it<<"\t";

? ? }

? ? cout<<endl;

}

int?main(){

? ? ss?s1;

? ? int?a[]={5,3,9,3,7,2,9,3};

? ? for(int?i=0;i<sizeof(a)/sizeof(int);i++){

? ? ? ? s1.insert(a[i]);

? ? }

? ? display(s1);

? ? cout<<"tong guo insert:"<<endl;

? ? display(s1);

? ? cout<<"tong guo duplicate:"<<endl;

? ? ss?s2(s1);

? ? display(s2);

? ? cout<<"tong guo gou zhao:"<<endl;

? ? ss?s3(a,a+sizeof(a)/sizeof(int));

? ? display(s3);

? ? return?0;

}

7-29：

#include<iostream>

#include<set>

using?namespace?std;

int?main(){

? ? int?a[]={5,3,9,3,7,2,9,3};

? ? set<int>myset(a,a+sizeof(a)/sizeof(int));

? ? multiset<int>mymultiset(a,a+sizeof(a)/sizeof(int));

? ? pair<set<int>::iterator,set<int>::iterator>rangset;

? ? pair<multiset<int>::iterator,multiset<int>::iterator>rangmultiset;

? ? rangset=myset.equal_range(3);

? ? rangmultiset=mymultiset.equal_range(3);

? ? int?ncount=myset.count(3);

? ? int?mcount=mymultiset.count(3);

? ? set<int>::iterator?te=rangset.first;

? ? cout<<"set=3de yuansu:"<<" ?";

? ? for(te;te!=rangset.second;te++){

? ? ? ? cout<<*te<<"\t";

? ? }

? ? cout<<endl;

? ? cout<<"the total of three:"<<ncount<<endl;

? ? cout<<"the myset's size:"<<myset.size()<<endl;

? ? multiset<int>::iterator?it=rangmultiset.first;

? ? cout<<"multiset is equal three:"<<" ?";

? ? for(it;it!=rangmultiset.second;it++){

? ? ? ? cout<<*it<<"\t";

? ? }

? ? cout<<endl;

? ? cout<<"the total of three:"<<mcount<<endl;

? ? cout<<"the mymultiset's size:"<<mymultiset.size()<<endl;

? ? return?0;

}

7-31：

#include<iostream>

#include<map>

#include<string>

using?namespace?std;

typedef?map<int,string>?ma;

void?display(ma&m){

? ? ma::iterator?it=m.begin();

? ? for(it;it!=m.end();it++){

? ? ? ? cout<<(*it).first<<"\t"<<(*it).second;

? ? }

? ? cout<<endl;

}

int?main(){

? ? ma?m;

? ? pair<int,string>s1(1,"zhangsan");

? ? pair<int,string>s2(2,"wangwu");

? ? pair<int,string>s3(3,"lisi");

? ? pair<int,string>s4(4,"zhaoliu");

? ? pair<int,string>s5(5,"chengqi");

? ? pair<int,string>s6(7,"kouba");

? ? m.insert(s1);

? ? m.insert(s2);

? ? m.insert(s3);

? ? m.insert(s4);

? ? m.insert(s5);

? ? m.insert(s6);

? ? display(m);

? ? ma?m1(m);

? ? display(m1);

? ? return?0;

}

7-33:

#include<iostream>

#include<set>

#include<string>

using?namespace?std;

class?employmee{

? ? private:

? ? string?name;

? ? string?department;

? ? public:

? ? employmee(string?m_name,string?m_department):name(m_name),department(m_department){}

? ? bool?operator<(const employmee&e)const{

? ? ? ? bool?mark=(department.compare(e.department)<0)?true:false;

? ? ? ? if(department.compare(e.department)==0){

? ? ? ? ? ? mark=(name.compare(e.name)<0)?true:false;

? ? ? ? }

? ? ? ? return?mark;

? ? }

? ? string?getname() const{return?name;}

? ? string?getdepartment() const{return?department;}

};

class?manger{

? ? private:

? ? multiset<employmee>myset;

? ? public:

? ? bool?add(employmee& e){

? ? ? ? myset.insert(e);

? ? ? ? return?true;

? ? }

? ? void?show(){

? ? ? ? multiset<employmee>::iterator?it=myset.begin();

? ? ? ? while(it!=myset.end()){

? ? ? ? ? ? const?employmee&?obj=*it;

? ? ? ? ? ? cout<<obj.getdepartment()<<"\t"<<obj.getname()<<endl;

? ? ? ? ? ? it++;

? ? ? ? }

? ? }

};

int?main(){

? ? employmee?e1("zhangsan","renlibu");

? ? employmee?e2("zhaoqi","zhuangpeibu");

? ? employmee?e3("wangwu","zhizhaobu");

? ? employmee?e4("zhaoliu","zhizhaobu");

? ? employmee?e5("lisi","zhuangpeibu");

? ? employmee?e6("tianjun","zhizhaobu");

? ? manger?mm;

? ? mm.add(e1);

? ? mm.add(e2);

? ? mm.add(e3);

? ? mm.add(e4);

? ? mm.add(e5);

? ? mm.add(e6);

? ? mm.show();

? ? return?0;

}

7-35:

#include<iostream>

#include<list>

#include<iterator>

using?namespace?std;

void?display(list<int> v){

? ? list<int>::iterator?it=v.begin();

? ? for(it;it!=v.end();it++){

? ? ? ? cout<<*it<<"\t";

? ? }

? ? cout<<endl;

}

int?main(){

? ? list<int>v;

? ? back_insert_iterator<list<int>>?backit(v);

? ? *backit++=1;

? ? *backit++=2;

? ? display(v);

? ? *back_inserter(v)=3;

? ? *back_inserter(v)=4;

? ? display(v);

? ? front_insert_iterator<list<int>>?frontit(v);

? ? *frontit++=5;

? ? *frontit++=6;

? ? display(v);

? ? *front_inserter(v)++=7;

? ? *front_inserter(v)++=8;

? ? display(v);

? ? list<int>::iterator?it=v.begin();

? ? for(int?i=0;i<3;i++){

? ? ? ? it++;

? ? }

? ? insert_iterator<list<int>>?insertit(v,it);

? ? *insertit++=9;

? ? display(v);

? ? return?0;

}

7-36:

#include<iostream>

#include<list>

#include<vector>

#include<iterator>

using?namespace?std;

template<class?reverse_iter>

void?reverse_display(reverse_iter?first,reverse_iter?last){

? ? while(first!=last){

? ? ? ? cout<<*first<<"\t";

? ? ? ? first++;

? ? }

? ? cout<<endl;

}

int?main(){

? ? vector<int>v;

? ? list<int>l;

? ? for(int?i=0;i<=5;i++){

? ? ? ? v.push_back(i);

? ? ? ? l.push_back(i+5);

? ? }

? ? cout<<"vectorer's reverse display:"<<endl;

? ? reverse_iterator<vector<int>::iterator>first(v.end());

? ? reverse_iterator<vector<int>::iterator>last(v.begin());

? ? reverse_display(first,last);

? ? cout<<"lister's reverse display:"<<endl;

? ? reverse_iterator<list<int>::iterator>first1(l.end());

? ? reverse_iterator<list<int>::iterator>last1(l.begin());

? ? reverse_display(first1,last1);

? ? return?0;

}

8-3:

#include<iostream>

#include<algorithm>

using?namespace?std;

bool?mygrater(int?m){

? ? return?m>4;

}

int?main(){

? ? int?a[]={1,2,2,2,2,2,2,3,4,5,6,6,2,7};

? ? int?nsize=sizeof(a)/sizeof(int);

? ? cout<<"原始数组:"<<endl;

? ? for(int?i=0;i<nsize;i++){

? ? ? ? cout<<a[i]<<"\t";

? ? }

? ? cout<<endl;

? ? int?*p1=find(a,a+nsize,3);

? ? if(p1!=a+nsize)

? ? ? ? cout<<"the find first position is equal three:"<<p1-a<<"\t"<<*p1<<endl;

? ? int?*p2=find_if(a,a+nsize,mygrater);

? ? if(p2!=a+nsize)

? ? ? ? cout<<"the find first position is >four:"<<p2-a<<"\t"<<*p2<<endl;

? ? int?b[]={10,12,6};

? ? int?nsize2=sizeof(b)/sizeof(int);

? ? int?*p3=find_first_of(a,a+nsize,b,b+nsize2);

? ? if(p3!=a+nsize)

? ? ? ? cout<<"首次在a数组中发现b[10,12,6]元素的位置:"<<p3-a<<*p3<<endl;

? ? int?*p4=adjacent_find(a,a+nsize);

? ? if(p4!=a+nsize)

? ? ? ? cout<<"首次相邻元素相同的位置:"<<p4-a<<*p4<<endl;

? ?

? ? int?c[]={2,3};

? ? int?nsize3=sizeof(c)/sizeof(int);

? ? int*p5=find_end(a,a+nsize,c,c+nsize3);

? ? if(p5!=a+nsize)

? ? ? ? cout<<"最后一次匹配c数组[2,3]的位置:"<<p5-a<<*p5;

? ? int?*p6=search(a,a+nsize,c,c+nsize3);

? ? if(p6!=a+nsize)

? ? ? ? cout<<"首次匹配c数组[2,3]的位置:"<<p6-a<<*p6;

? ?

? ? int*p7=search_n(a,a+nsize,3,2);

? ? if(p7!=a+nsize)

? ? ? ? cout<<"首次出现3个2的:"<<p7-a<<*p7;

? ? ? ? return?0;

}

8-10:

#include<iostream>

#include<algorithm>

using?namespace?std;

int?main(){

? ? int?a1[]={3,1,4,1,5,9,3};

? ? int?a2[]={3,1,4,2,8,5,7};

? ? const?int?N=sizeof(a1)/sizeof(int);

? ? pair<int*,int*>result=mismatch(a1,a1+N,a2);

? ? cout<<"The first mismatch is in position "<<result.first-a1<<endl;

? ? cout<<"values are:"<<*(result.first)<<","<<*(result.second)<<endl;

? ? return?0;

}

实验结果（附数据和图表）：

7-28：

7-29：

7-31：

7-33：

7-35：

7-36：

8-3：

8-10：

实验结果分析及结论：

1. Multiset集合默认是按升序排列的，也会允许有重复元素。
2. Pair类中的两个成员变量为first和second相当于集合类中的lower_bound和upper_bound，也正好符合映射类中的键值映射要求，因此映射类要求保存的都是pair对象。
3. map映射默认也是按键值升序排列的，但是不允许有重复的键值。

实验心得体会和建议：

理解容器的特性：在使用任何一个容器之前，都应该先了解它的特性，比如它是否允许重复元素、是否自动排序等。这将有助于我们选择最适合的容器来解决问题。

????注意内存使用：虽然set、multiset、map、multimap提供了高效的性能，但它们的内存使用相对较大，特别是在元素数量较多时。因此，在内存使用敏感的场景中，应该优先考虑内存使用更小的容器，如vector。

????使用迭代器：在这些容器中，我们应该习惯使用迭代器来访问元素，而不是直接访问。这是因为这些容器在内部可能使用了一些复杂的数据结构，直接访问可能会带来一些不必要的复杂度。

????注意容器的初始化：在使用这些容器时，我们应该注意它们的初始化方式。比如，set和map在初始化时需要指定比较函数，而multiset和multimap则不需要。

总的来说，set、multiset、map、multimap是C++中非常强大的关联容器，它们能够帮助我们高效地管理数据，但在使用时，我们也应该注意它们的特性和使用方法，以充分发挥它们的优势。