0902，DEQUE，LIST，VECTOR

目次
01_vector.cc
02_vector.cc
作业
01STL包括哪些组件？各自具有哪些特点？
02 序列式容器包括哪些？他们之间有哪些异同？
03 下面步调有什么错误？
04 创建和初始化vector的方法，每种都给出一个实例？固然也可以把deque与list写出来
05 如果c1与c2是两个容器，下面的比力操作有什么限制？if(c1 < c2)
06 STL中的std::deque容器的实现原理？
07 评委打分的例子：要求：有五名选手ABCDE，10个评委打分，去掉最高分和最低分，求出每个选手的匀称分。
08 编程题：从一个 vector 初始化一个 string。
09 题目：利用vector打印九九乘法表。
01_vector.cc

1. #include <iostream>
2. #include <vector>
3. using std::cout;
4. using std::endl;
5. using std::vector;
7. template <class T>
8. class vec{
9. public:
10. private:
11.     typedef T* _iterator;
12. };
13. void test(){
14.     /*1*/vector<int> num0;
15.     /*2*/vector<int> num1(10,5);//count same value
17.     int arr[10]={0,1,2,3,4,5,6,7,8,9};
18.     /*3*/vector<int> num2(arr,arr+10);//[0,10)
19.     /*4*///copy & move
20.     /*5*/vector<int> num3{4,5,6,3,2,7,3,9};
22.     //-----------------------------------//
23.     vector<int>::iterator it=num1.begin();//未初始化迭代器
24.     for(;it!=num1.end();++it){
25.         cout<<*it<<" ";
26.     }
27.     cout<<endl;
29.     //-----------------------------------//
30.     for(size_t idx;idx!=sizeof(arr)/sizeof(arr[0]);++idx){
31.         cout<<num1[idx]<<" ";
32.     }
33.     cout<<endl;
35.     //-----------------------------------//
36.     for(auto itt=num2.begin();itt!=num2.end();itt++){
37.         cout<<*itt<<" ";
38.     }
39.     cout<<endl;
41.     //-----------------------------------//
42.     for(auto &ele: num3){
43.         cout<<ele<<" ";
44.     }
45.     cout<<endl;
46. }
48. int main(void)
49. {
50.     test();
51.     return 0;
52. }

复制代码

02_vector.cc

1. #include <iostream>
2. #include <vector>
3. #include <deque>
4. #include <list>
5. using std::cout;
6. using std::endl;
7. using std::vector;
8. using std::list;
9. using std::deque;
11. template <typename Container>
12. void display(const Container & con){
13.     for(auto &ele: con){
14.         cout<<ele<<" ";
15.     }
16.     cout<<endl;
17. }
18. void display_cap(const vector<int> & con){
19.     cout<<endl;
20.     display(con);
21.     cout<<"size::"<<con.size()<<endl;
22.     cout<<"capacity::"<<con.capacity()<<endl;
23. }
27. //---------------------------------//
28. //vector  可变数组
29. template <class T>
30. class vec{
31. public:
32.     T* data(){return _M_start;}
33. private:
34.     T* _M_start;           //第一个元素
35.     T* _M_finish;          //最后一个元素的下一个位置
36.     T* _M_end_of_storage;  //最后一个空间的下一个位置
37. };
38. //---------------------------------//
39. //deque  逻辑连续 物理存储分散
40. //中控器数组 Map  -->  小片段(内部连续)
41. //迭代器不是一个普通类型的指针，是一个类，对指针的基本功能都做了重载
42. template <class T>
43. class _Tp{
44. private:
45.     _Tp* _M_cur;
46.     _Tp* _M_first;
47.     _Tp* _M_last;
48.     /* _Map_pointer _M_node;  //和中控器联系 */
49. };
50. template <class _Tp,class _Alloc>
51. class _deque_base{
52. };
53. //---------------------------------//
58. void test(){
59.     vector<int> num3{4,5,6,7,8,9};
60.     display(num3);
61.     num3.push_back(333);
62.     display(num3);
63.     num3.pop_back();
64.     display(num3);
65.     //vector不支持头部插入和删除，一端开口
66.     //效率——整体前移/后移
68.     cout<<"<<<<<<<<<<<<<<<<vector first number addr"<<endl;
69.     &num3;//error  _M_tart
70.     cout<<&(*num3.begin())<<endl;
71.     cout<<&(num3[0])<<endl;
72.     int *pdata=num3.data();
73.     cout<<pdata<<endl;
75.     vector<int>::iterator v_it=num3.begin();
76.     v_it++;
77.     v_it+=2;
78.     cout<<"*v_it  "<<*v_it<<endl;
79.     num3.insert(v_it,11);//insert front ,return cur
80.     display_cap(num3);
81.     cout<<"*v_it  "<<*v_it<<endl;
83.     /* num3.insert(v_it,10,222);//迭代器失效 invalid pointer */
84.     v_it=num3.begin();
85.     num3.insert(v_it,10,222);//迭代器失效 invalid pointer
86.     display_cap(num3);
87.     cout<<"*v_it  "<<*v_it<<endl;
89.     v_it=num3.begin();
90.     num3.insert(v_it,{666,777,888});
91.     display_cap(num3);
92.     cout<<"*v_it  "<<*v_it<<endl;
94.     v_it=num3.begin();
95.     num3.insert(v_it,num3.begin(),num3.end());
96.     display_cap(num3);
97.     cout<<"*v_it  "<<*v_it<<endl;
98.     //insert操作的时候，会导致底层发生扩容操作
99.     //迭代器还指向老的空间，老的空间已经回收了，所以
100.     //迭代器失效了
101.     //解决：每次都重新 置位 迭代器
104.     cout<<endl<<endl;
105.     //-----------------------------//
106.     list<int> num2{4,5,6,7,8,9};
107.     display(num2);
108.     num2.push_back(333);
109.     num2.push_front(44444);
110.     display(num2);
111.     num2.pop_back();
112.     num2.pop_front();
113.     display(num2);
115.     cout<<"<<<<<<<<<<<<<<<<<<list push anywhere"<<endl;
116.     list<int>::iterator l_it=num2.begin();
117.     l_it++;
118.     /* l_it+=2; */
119.     cout<<"*l_it  "<<*l_it<<endl;
120.     num2.insert(l_it,11);//insert front ,return cur
121.     display(num2);
122.     cout<<"*l_it  "<<*l_it<<endl;
124.     num2.insert(l_it,3,222);
125.     display(num2);
126.     cout<<"*l_it  "<<*l_it<<endl;
127.     num2.insert(l_it,{666,777,888});
128.     display(num2);
129.     cout<<"*l_it  "<<*l_it<<endl;
130.     num2.insert(l_it,num2.begin(),num2.end());
131.     display(num2);
132.     cout<<"*l_it  "<<*l_it<<endl;
135.     cout<<endl<<endl;
136.     //-----------------------------//
137.     deque<int> num1{0,1,2,3,4,5,6,7};
138.     display(num1);
139.     num1.push_back(333);
140.     num1.push_front(44444);
141.     display(num1);
142.     num1.pop_back();
143.     num1.pop_front();
144.     display(num1);
146.     cout<<"<<<<<<<<<<<<<<<<<<deque push anywhere"<<endl;
147.     deque<int>::iterator d_it=num1.begin();
148.     d_it++;
149.     d_it+=2;
150.     cout<<"*d_it  "<<*d_it<<endl;
151.     num1.insert(d_it,11);//insert前面一半，前移前面一半，后面一半后移
152.     display(num1);
153.     cout<<"*d_it  "<<*d_it<<endl;
155.     num1.insert(d_it,3,222);
156.     display(num1);
157.     cout<<"*d_it  "<<*d_it<<endl;
158.     num1.insert(d_it,{666,777,888});
159.     display(num1);
160.     cout<<"*d_it  "<<*d_it<<endl;
161.     num1.insert(d_it,num1.begin(),num1.end());
162.     display(num1);
163.     cout<<"*d_it  "<<*d_it<<endl;
165.     cout<<endl;
167. }
169. int main(void)
170. {
171.     test();
172.     return 0;
173. }

复制代码

作业

01STL包括哪些组件？各自具有哪些特点？

01 容器（用来存放数据，也是数据结构
02 算法（用来实现容器的算法操作
03 迭代器（用来访问容器中的成员，是广义上的指针，也叫泛型指针
04 适配器（起到适配的作用
05 函数对象（仿函数：进行定制化操作
06 空间配置器（对空间的申请和开释进行管理
02 序列式容器包括哪些？他们之间有哪些异同？

01 vector 可变数组
02 deque 双向队列
03 list 双向链表
04 foward_list 单向链表
05 array 数组
内存上，array 和 vector是一片连续的空间，别的是逻辑上连续，物理存储时分散的
实现上，vector底层通过三个指针实现，分别指向第一个元素的位置，最后一个元素的下一个位置，最后一个空间的下一个位置；
deque的实现依赖  中控器数组Map+小片段实现的，片段内部是连续的，片段与片段之间是不连续的，当deque必要扩容时，直接对Map进行扩容，申请新的小片段（小片段成员包括四个指针，分别指向第一个元素，最后一个元素，当前元素，一个指针用于和Map进行联系）
list 链表喵
利用上，deque,vector支持随机访问，list不支持
03 下面步调有什么错误？

1. list<int> lst;
2. list<int>::iterator iter1 = lst.begin(), iter2 = lst.end();
3. while(iter1 < iter2)
4. {   
5.      //....
6. }

复制代码

list的迭代器不能进行<比力,要用迭代器特有的！=
04 创建和初始化vector的方法，每种都给出一个实例？固然也可以把deque与list写出来

01 创建空容器
02 count个value
03 迭代器
04 {}
05 拷贝构造和移动构造

1. #include <iostream>
2. #include <vector>
3. #include <deque>
4. #include <list>
5. using std::cout;
6. using std::endl;
7. using std::vector;
8. using std::list;
9. using std::deque;
12. template <class T>
13. void print( T & con){
14.     for(auto & ele: con){
15.         cout<<ele<<" ";
16.     }
17.     cout<<endl;
18. }
20. void test(){
21.     /*1*/vector<int> num0;
22.     /*2*/vector<int> num1(10,5);//count same value
23.     int arr[10]={0,1,2,3,4,5,6,7,8,9};
24.     /*3*/vector<int> num2(arr,arr+10);//[0,10)
25.     /*4*/vector<int> num4(num1);
26.     /*4*/vector<int> num5(vector<int>{1,2,3});
27.     /*5*/vector<int> num3{4,5,6,3,2,7,3,9};
28.     print(num0);
29.     print(num1);
30.     print(num2);
31.     print(num3);
32.     print(num4);
33.     print(num5);
34.     cout<<endl;
35. }
36. void test1(){
37.     /*1*/deque<int> num0;
38.     /*2*/deque<int> num1(10,5);//count same value
39.     /*3*/deque<int> num2(num1.begin(),num1.end());//[0,10)
40.     /*4*/deque<int> num4(num1);
41.     /*4*/deque<int> num5(deque<int>{1,2,3});
42.     /*5*/deque<int> num3{4,5,6,3,2,7,3,9};
43.     print(num0);
44.     print(num1);
45.     print(num2);
46.     print(num3);
47.     print(num4);
48.     print(num5);
49.     cout<<endl;
50. }
51. void test2(){
52.     /*1*/list<int> num0;
53.     /*2*/list<int> num1(10,5);//count same value
54.     /*3*/list<int> num2(num1.begin(),num1.end());//[0,10)
55.     /*4*/list<int> num4(num1);
56.     /*4*/list<int> num5(list<int>{1,2,3});
57.     /*5*/list<int> num3{4,5,6,3,2,7,3,9};
58.     print(num0);
59.     print(num1);
60.     print(num2);
61.     print(num3);
62.     print(num4);
63.     print(num5);
64.     cout<<endl;
65. }
66. int main(void)
67. {
68.     test();
69.     test1();
70.     test2();
71.     return 0;
72. }

复制代码

05 如果c1与c2是两个容器，下面的比力操作有什么限制？if(c1 < c2)

01，是相同的容器类型
02，容器的元素类型支持比力操作
03，容器内部元素的次序性比力（deque,vector支持，list不支持，只能利用！=）
04，容器支持随机访问元素
06 STL中的std::deque容器的实现原理？

deque的实现依赖  中控器数组Map+小片段实现的，片段内部是连续的，片段与片段之间是不连续的，当deque必要扩容时，直接对Map进行扩容，申请新的小片段（小片段成员包括四个指针，分别指向第一个元素，最后一个元素，当前元素，一个指针用于和Map进行联系）
07 评委打分的例子：要求：有五名选手ABCDE，10个评委打分，去掉最高分和最低分，求出每个选手的匀称分。

思绪： 
1.创建Person类，定义name，score成员属性；创建五名选手存放到vector容器中；
2.遍历vector容器，首先10个评委的打分存放到deque容器中，sort算法对分数排序，去掉最高最低分；
3.deque容器遍历，进行剩余分数的累加，求匀称；
4.输出每个选手的姓名，结果
提示：还是容器vector与deque的根本利用

1. //嘻嘻，每一个初始化都会worning
3. #include <iostream>
4. #include <vector>
5. #include <deque>
6. #include <string.h>
7. #include <random>
8. using std::cout;
9. using std::endl;
10. using std::vector;
11. using std::deque;
12. using std::ostream;
14. #define  PER_NUM 5
15. #define  SCO_NUM 10
17. class Person{
18. public:
19. //const char* 坏，终于知道为什么worning了
20.     Person(char* name,int sc)
21.         :_name(new char[strlen(name)+1]()),_score(sc)
22.     {
23.         strcpy(_name,name);
24.     }
25.     Person(const Person & p)
26.         :_name(new char[strlen(p._name)+1]()),_score(p._score)
27.     {
28.         strcpy(_name,p._name);
29.     }//vector初始化使用拷贝构造
30.     ~Person(){
31.         if(_name){
32.             delete []  _name;
33.             _name=nullptr;
34.         }
35.     }
36.     Person & operator=(const Person & p){
37.         if(this!=&p){
38.             delete [] _name;
39.             _name=new char[strlen(p._name)+1]();
40.             strcpy(_name,p._name);
41.             _score=p._score;
42.         }
43.         return *this;
44.     }
45.     void p_sc(int sc){
46.         _score=sc;
47.     }
48.     friend ostream & operator<<(ostream & os,const Person & p);
49. private:
50.     char* _name;
51.     int _score;
52. };
53. ostream & operator<<(ostream & os,const Person & p){
54.     os<<p._name<<"--"<<p._score<<"  ";
55.     return os;
56. }
59. //-------------------------//
60. void test(){
61.     Person p1("xixi",0);
62.     Person p2("jiajia",0);
63.     Person p3("kewu",0);
64.     Person p4("dada",0);
65.     Person p5("shazi",0);
66.     vector<Person> people{p1,p2,p3,p4,p5};
68.     std::random_device rd;
69.     //获取随机数种子
70.     std::mt19937 gen(rd());
71.     //生成随机数引擎
72.     std::uniform_int_distribution<> dis(60,100);
73.     //范围
75.     for(int i=0;i<PER_NUM;i++){
76.         deque<int> sc;
77.         for(int j=0;j<SCO_NUM;j++){
78.             sc.push_back(dis(gen));
79.             /* cout<<sc[j]<<" "; */
80.         }
81.         /* cout<<endl; */
82.         int max=0,min=0,rel=0;
83.         for(auto & ele:sc){
84.             if(ele>max){max=ele;}
85.             if(ele<min){min=ele;}
86.             rel+=ele;
87.         }
89.         rel=(rel-max-min)/(SCO_NUM-2);
90.         people[i].p_sc(rel);
91.         cout<<people[i]<<endl;
92.     }
94.     cout<<endl;
95. }
96. int main(void)
97. {
98.     test();
99.     return 0;
100. }

复制代码

1. #include <iostream>
2. #include <string>
3. #include <vector>
4. #include <deque>
5. #include <algorithm>
7. using namespace std;
9. class Person
10. {
11. public:
12.         Person(const string &name,int score)
13.     : _name(name)
14.     , _score(score)
15.     {
16.         }
18.         string _name;
19.         int _score;
20. };
22. void creatPerson(vector<Person>& vec)
23. {
24.         string nameSeed = "ABCDE";
26.         for (int idx = 0; idx < 5; ++idx)
27.     {
28.                 string name = "选手";
29.                 name += nameSeed[idx];
31.                 int score = 0;
32.                 Person p(name, score);
33.                 vec.push_back(p);
34.         }
35. }
37. void setScore(vector<Person>& vec)
38. {
39.         for (vector<Person>::iterator it = vec.begin(); it != vec.end(); ++it)
40.         {
41.                 deque<int> dq;
42.                 for (int idx = 0; idx < 10; ++idx)
43.         {
44.             //将分数设定在[60, 100]范围中
45.                         int score = ::rand() % 41 + 60;//产生随机的分数
46.                         dq.push_back(score);
47.                 }
49.         //对分数进行排序
50.                 sort(dq.begin(), dq.end());
51.                 dq.pop_front();//去掉最低分
52.                 dq.pop_back();//去掉最高分
54.                 int sum = 0;
55.                 for (deque<int>::iterator dit = dq.begin(); dit != dq.end(); ++dit)
56.         {
57.                         sum += *dit;
58.                 }
59.         //求10个评委的平均分
60.                 int avg = sum/dq.size();
61.                
62.         //然后将10个评委的平均分赋值给每个选手
63.                 it->_score = avg;       
64.     }
65. }
67. void showScore(vector<Person>& vec)
68. {
69.         for (vector<Person>::iterator it = vec.begin(); it != vec.end(); ++it)
70.     {
71.                 cout << "姓名:" << it->_name << "  平均分数:" << it->_score << endl;
72.         }
73. }
75. int main()
76. {
77.     //种随机种子
78.         ::srand(::clock());
80.     //定义Person类型的容器
81.         vector<Person> vec;
83.     //创建五名选手，创建容器类里面的成员及其属性
84.         creatPerson(vec);
85.     //给每个选手设定分数（让10个评委打分）
86.         setScore(vec);
87.     //显示每个选手的分数
88.         showScore(vec);       
90.         return 0;
91. }

复制代码

 不想看，虽然我的初始化一直woring
//Person(const char* name,int score)坏，终于知道为什么worning了
  08 编程题：从一个 vector<char> 初始化一个 string。

提示：可以定义vector如下：vector<char> vc = { 'H', 'E', 'L', 'L', 'O' };然后查察如何给string进行初始化大概赋值，考查对vector与string的根本利用

1. #include <iostream>
2. #include <vector>
3. #include <deque>
4. #include <list>
5. #include <string>
6. using std::cout;
7. using std::endl;
8. using std::vector;
9. using std::list;
10. using std::deque;
11. using std::string;
14. //---------------------------------//
17. void test(){
18.     vector<char>vc={'h','e','l','l','o'};
19.     string s1{'\0'};
20.     cout<<s1<<endl;
21.     for(auto & ele:vc){
22.         s1+=ele;
23.     }
24.     s1+='\0';
25.     cout<<s1<<endl;
26. }
28. int main(void)
29. {
30.     test();
31.     return 0;
32. }

复制代码

1. #include <iostream>
2. #include <string>
3. #include <vector>
4. using namespace std;
5. int main()
6. {
7.         vector<char> vc = { 'H', 'E', 'L', 'L', 'O' };
8.         string s(vc.data(), vc.size());
9.         cout << s << endl;
10.        
12.         return 0;
13. }

复制代码

 我好蠢嘻嘻
  09 题目：利用vector打印九九乘法表。

提示：可以利用vector嵌套vector的利用方式。比方：vector<vector<int>>，然后就是veector的根本操作。

1. #include <iostream>
2. #include <vector>
3. #include <deque>
4. #include <list>
5. #include <string>
6. using std::cout;
7. using std::endl;
8. using std::vector;
9. using std::list;
10. using std::deque;
11. using std::string;
13. //---------------------------------//
15. void print(vector<vector<int>>  & con){
16.     for(int i=0;i<9;i++){
17.         for(auto & ell : con[i]){
18.             cout<<(i+1)<<"×"<<ell<<"="<<(i+1)*(ell)<<"  ";
19.         }
20.         cout<<endl;
21.     }   
22. }
25. //---------------------------------//
26. void test(){
27.     vector<vector<int>> v1(9);
28.     for(int i=0;i<9;i++){
29.         vector<int> tempv;
30.         for(int j=0;j<=i;j++){
31.             tempv.push_back(j+1);
32.         }
33.         v1[i]=tempv;
34.     }
35.     print(v1);
36. }
39. int main(void)
40. {
41.     test();
42.     return 0;
43. }

复制代码

1. #include<iostream>
2. #include<vector>
4. using namespace std;
6. int main()
7. {
8.         vector<vector<int> >v2d;
9.         for (int i = 0; i < 9; i++)
10.         {
11.                 v2d.push_back(vector<int>());
12.         }
13.    
14.         for (int i = 0; i < v2d.size(); i++)
15.         {
16.                 for (int j = 0; j <= i; j++)
17.                 {
18.                         v2d[i].push_back((i + 1) * (j + 1));
19.                 }
20.         }
21.         for (int i = 0; i < v2d.size(); i++)
22.         {
23.                 for (int j = 0; j < v2d[i].size(); j++)
24.                 {
25.                         cout << i + 1 << "*" << j + 1 << "=" << v2d[i][j] << "\t";
26.                 }
27.                 cout << endl;
28.         }
29.         return 0;
30. }

复制代码

01，初始化9个空 vector<int>-->vector<vector<int>>
  02，vector<int>存乘积
  03，打印

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。