STL-vector和deque得使用

实验目的：

本实验主要用于练习容器deque和vector的使用方法。

实验器材：

vscode

实验内容：

一．练习课本第7章的例7.1-7.10.

二．简述vector和deque的实现原理并比较二者的缺点。

实验步骤：

7.1：初始化

#include<iostream>

#include<vector>

#include<deque>

using?namespace?std;

class?A{

};

int?main(int?argc,char*argv[]){

? ? vector<int>intv;

? ? vector<float>floatv;

? ? vector<A>ca;

? ? vector<A*>cca;

? ? cout<<"方法一:initial successful!"<<endl;

? ? typedef?vector<int>?intvv;

? ? typedef?vector<float>?floatvv;

? ? typedef?vector<A>?cav;

? ? typedef?vector<A*>?caav;

? ? intvv?a;

? ? floatvv?b;

? ? cav?c;

? ? caav?d;

? ? cout<<"方法二:initial successful!"<<endl;

? ? return?0;

}

7.2：增加及获得元素示例

#include<iostream>

#include<vector>

using?namespace?std;

int?main(){

? ? typedef?vector<int>?vec;

? ? vec?v;

? ? v.push_back(1);

? ? v.push_back(2);

? ? v.push_back(3);

? ? int?nsize;

? ? nsize=v.size();

? ? cout<<"数组:";

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

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

? ? }

? ? cout<<endl;

? ? cout<<"引用:";

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

? ? ? ? cout<<v.at(i)<<"\t";

? ? }

? ? cout<<endl;

? ? cout<<"迭代器:";

? ? vec::iterator?it=v.begin();

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

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

? ? ? ? it++;

? ? }

? ? cout<<endl;

}

7.3

#include<iostream>

#include<vector>

using?namespace?std;

class?A{

public:

? ? int?n;

public:

? ? A(int?n){

? ? ? ? this->n=n;

? ? ? ? //cout<<n<<endl;

? ? }

};

int?main(){

? ? cout<<"类A向量的操作:"<<endl;

? ? typedef?vector<A>?vec;//类A向量的定义

? ? vec?v;

? ? A?a1(1);

? ? A?a2(2);

? ? A?a3(3);

? ? v.push_back(a1);

? ? v.push_back(a2);

? ? v.push_back(a3);

? ? cout<<"数组输出:";

? ? for(int?i=0;i<v.size();i++){

? ? ? ? cout<<v[i].n<<"\t";

? ? }

? ? cout<<endl;

? ? cout<<"引用输出:";

? ? for(int?i=0;i<v.size();i++){

? ? ? ? int?&y=v.at(i).n;

? ? ? ? cout<<y<<"\t";

? ? }

? ? cout<<endl;

? ? cout<<"代器输出:";

? ? vec::iterator?it=v.begin();

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

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

? ? }

? ? cout<<endl;

? ? cout<<"类A向量的指针的操作:"<<endl;

? ? typedef?vector<A*>?veca;//类A的指针向量定义

? ? veca?vv;

? ? A*?p1=new?A(1);

? ? A*?p2=new?A(2);

? ? A*?p3=new?A(3);//新建3个对象的指针

? ? vv.push_back(p1);

? ? vv.push_back(p2);

? ? vv.push_back(p3);

? ? cout<<"数组输出:";

? ? for(int?i=0;i<vv.size();i++){

? ? ? ? cout<<vv[i]->n<<"\t";

? ? }

? ? cout<<endl;

? ? cout<<"引用输出:";

? ? for(int?i=0;i<vv.size();i++){

? ? ? ? int?&?x=vv.at(i)->n;

? ? ? ? cout<<x<<"\t";

? ? }

? ? cout<<endl;

? ? // cout<<"代器输出:";

? ? // veca::iterator it=vv.begin();

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

? ? // ? ? cout<<(**it).n<<"\t";

? ? // }

? ? cout<<endl;

? ? delete?p1;

? ? delete?p2;

? ? delete?p3;

? ? return?0;

}

7.4:修改元素

#include<iostream>

#include<vector>

using?namespace?std;

int?main(){

? ? typedef?vector<int>?vec;

? ? vec?v;

? ? v.push_back(1);

? ? v.push_back(2);

? ? v.push_back(3);

? ? cout<<"通过数组替换:";

? ? v[0]=20;

? ? for(int?i=0;i<v.size();i++){

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

? ? }

? ? cout<<endl;

? ? cout<<"通过引用替换:";

? ? int&m=v[1];

? ? m=20;

? ? for(int?i=0;i<v.size();i++){

? ? ? ? cout<<v.at(i)<<"\t";

? ? }

? ? cout<<endl;

? ? cout<<"通过迭代替换:";

? ? vec::iterator?it=v.begin();

? ? *(it+2)=20;

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

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

? ? }

? ? cout<<endl;

? ? return?0;

}

7.5：删除元素

#include<iostream>

#include<vector>

using?namespace?std;

int?main(){

? ? typedef?vector<int>?vec;

? ? vec?v;

? ? for(int?i;i<10;i++){

? ? ? ? v.emplace_back(i);

? ? }

? ? cout<<"删除第五个元素:";

? ? v.erase(v.begin()+4);

? ? cout<<"size:"<<v.size()<<"\t";

? ? cout<<"capacity:"<<v.capacity()<<"\t";

? ? vec::iterator?it=v.begin();

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

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

? ? ? ? it++;

? ? }

? ? cout<<endl;

? ? cout<<"删除第二个到第五个的元素:";

? ? v.erase(v.begin()+1,v.begin()+5);

? ? cout<<"size:"<<v.size()<<"\t";

? ? cout<<"capacity:"<<v.capacity()<<"\t";

? ? for(int?i=0;i<v.size();i++){

? ? ? ? cout<<v.at(i)<<"\t";

? ? }

? ? cout<<endl;

? ? return?0;

}

7.6：综合示例1

#include<iostream>

#include<vector>

#include<string>

using?namespace?std;

class?Student{

? ? public:

? ? string?sno;

? ? string?name;

? ? string?age;

? ? string?sex;

? ? string?data;

? ? public:

? ? Student(string?msno,string?mname,string?mage,string?msex,string?mdata):name(mname),age(mage),data(mdata),sex(msex),sno(msno){}

? ? void?Display(){

? ? ? ? cout<<name<<"\t"<<age<<"\t"<<sex<<"\t"<<data<<endl;

? ? }

};

class?Studcollect{

? ? typedef?vector<Student>?vec;

? ? public:

? ? vec?v;

? ? public:

? ? void?Add(Student&?s1){

? ? ? ? v.emplace_back(s1);

? ? }

? ? Student*?Find(string?msno){

? ? ? ? int?i;

? ? ? ? bool?find=false;

? ? ? ? for(int?i=0;i<v.size();i++){

? ? ? ? ? ? Student?&s=v[i];

? ? ? ? ? ? if(msno==s.sno){

? ? ? ? ? ? ? ? find=true;

? ? ? ? ? ? ? ? break;

? ? ? ? ? ? }

? ? ? ? }

? ? ? ? Student?*s=NULL;

? ? ? ? if(find){

? ? ? ? ? ? s=&v[i];

? ? ? ? ? ? return?s;

? ? ? ? }

? ? }

};

int?main(){

? ? Student?s1?("202102811534","张三","20","男","2003.01.01");

? ? Student?s2?("202102811513","李四","23","女","2000.11.21");

? ? Student?s3?("202102811523","王五","18","男","2005.08.21");

? ? Student?s4?("202102811521","赵六","21","女","2002.05.23");

? ? Studcollect?sc;

? ? sc.Add(s1);

? ? sc.Add(s2);

? ? sc.Add(s3);

? ? sc.Add(s4);

? ? Student*s=sc.Find("202102811534");

? ? if(s){

? ? ? ? s->Display();

? ? }

? ? return?0;

}

7.7综合示例2

#include<iostream>

#include<vector>

#include<string>

using?namespace?std;

class?Book{

? ? public:

? ? string?bpublic;

? ? string?bcno;

? ? string?bname;

? ? Book(string?mbpublic,string?mbcno,string?mbname){

? ? ? ? this->bpublic=mbpublic;

? ? ? ? this->bcno=mbcno;

? ? ? ? this->bname=mbname;

? ? }

};

class?Writer{

? ? public:

? ? string?wname;

? ? string?wcno;

? ? vector<Book>bec;

? ? public:

? ? Writer(string?wmnamest,string?wmcno):wname(wmnamest),wcno(wmcno){}

? ? void?Add(Book&?book){

? ? ? ? bec.push_back(book);

? ? }

};

class?WriterManager{

? ? private:

? ? vector<Writer>wec;

? ? public:

? ? void?Add(Writer&?writer){

? ? ? ? wec.push_back(writer);

? ? }

};

int?main(){

? ? Writer?w1("zhangsna","1001");

? ? Book?b1("bic","1001","C++");

? ? Book?b2("lic","1002","java");

? ? w1.Add(b1);

? ? w1.Add(b2);

? ? Writer?w2("wangwu","1002");

? ? Book?b3("ads","1003","python");

? ? w2.Add(b3);

? ? WriterManager?wm;

? ? wm.Add(w1);

? ? wm.Add(w2);

? ? cout<<"添加完成！";

? ? return?0;

}

二．二者的实现原理和优缺点：

vector的实现原理：

vector的数据安排及操作方式与array非常相似。两者的唯一差别在于空间运用的灵活性。array是静态空间，一旦配置好了就不能改变了，如果程序需要一个更大的array，只能自己再申请一个更大的array，然后将以前的array中的内容全部拷贝到新的array中。vector是动态空间，随着元素的加入，它的内部机制会自动扩充空间以容纳新的元素。vector的关键技术在于对大小的控制以及重新分配时的数据移动效率。vector采用的数据结构是线性的连续空间，它以两个迭代器start和finish分别指向配置得来的连续空间中目前已将被使用的空间。迭代器end_of_storage指向整个连续的尾部。vector在增加元素时，如果超过自身最大的容量，vector则将自身的容量扩充为原来的两倍。

deque的实现原理：

deque是双向开口的连续线性空间，而vector是单向开口的连续线性空间。deque没有容量的概念，它是动态地以分段连续空间组合而成，随时可以增加一点新的空间并链接起来。不会像vector因“旧空间不足，而重新配置更大空间，然后复制旧元素，再释放旧空间”。因此deque没有reserve功能。deque提供Ramdon Access Iterator，但复杂度和vector不能相提并论，这也影响到各类算法方面。因此，除非必要，应尽量使用vector。例如，对deque进行排序，为了最高效率，可以将deque复制到vector，采用stlsort排序完，再复制回deque。deque是表象的连续线性空间。实际上deque由一段一段的定量连续空间构成。deque最大任务，对多段连续空间的处理，维护整体连续的假象，并提供随机存取接口。而它的代价在于复杂的迭代器结构。

vector和deque的优缺点比较：

vector：使用的是数组，如果只在尾部插入数据，效率会高一些。但是在其他地方插入数据，效率会低一些。当vector中的元素大于容量时要使用realloc()重新分配内存，这会导致vector中元素的引用、指针和迭代器失效，而且重新分配内存会花很多时间。

deque：使用的是链表，在两端插入和删除数据的效率非常高。但是它在中间进行插入和删除操作时效率很低。deque的内存空间不是连续的，是有多块内存使用链表结构链接在一起，不过这样的好处是更有效的使用内存，能够自动释放内存。

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

7.1

7.2.

7.4

7.5

7.6

7.7

实验结果分析及结论：

1. 利用typedef定义是非常简洁的，也使程序容易维护。
2. 容器元素输出时可以有三种方法：数组，引用(at)，迭代器。
3. 迭代器的区间是前闭后开。

实验心得体会和建议：

通过这次实验，我再次体会到了面向对象的优点。练习容器vector和deque的使用方法，我深入了解了这两种数据结构的特性和使用方法。在实际应用中，需要根据具体的需求和场景选择合适的容器类型。同时，还需要注意容器的使用规范，以避免潜在的问题和错误。但是也暴露出自己的不足，例如有些概念，关键字，函数使用的方法等忘记或模糊，需时不时得百度，翻书，从而也通过再次学习让自己在编写的时候有所提高，有所改善。??