Data Struction-Vector

Posted on | In | Views:

底层数据结构为数组 ，支持快速随机访问

vector和built-in数组类似，它拥有一段连续的内存空间，并且起始地址不变，因此它能非常好的支持随机存取，即[]操作符，但由于它的内存空间是连续的，所以在中间进行插入和删除会造成内存块的拷贝，另外，当该数组后的内存空间不够时，需要重新申请一块足够大的内存并进行内存的拷贝。这些都大大影响了vector的效率。（中间插入和删除效率低）.它采用线性空间存储数据。如果空间不够，则另外分配新的两倍大小的空间，然后把旧空间释放掉。

  • vector不适合push_front(效率很低)
  • vector不适合中间插入删除操作。中间插入删除操作会引起内存拷贝。

存放结构体类型的变量的两种存放方式

  • 方式一：放入这个结构体类型变量的副本。
  • 方式二：放入指向这个结构体类型变量的指针。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/*[方式一] 结构体放栈中,vector中放副本---------------------*/
#include <iostream>
#include <string>
#include <vector>
typedef struct student{
   char school_name[100];
   char gender;
   int age;
   bool is_absent;
} StudentInfo;
 
typedefstd::vector<StudentInfo> StudentInfoVec;
 
void print(StudentInfoVec* stduentinfovec){
   for (int j=0;j<(*stduentinfovec).size();j++)
    {
       std::cout<<
           (*stduentinfovec)[j].school_name<<"\t"<<
           (*stduentinfovec)[j].gender<<"\t"<<
           (*stduentinfovec)[j].age<<"\t"<<
           (*stduentinfovec)[j].is_absent<<"\t"<<std::endl;
    }
   return;
}
 
int main(){
   StudentInfo micheal={"Micheal",'m',18,false};
   StudentInfo cherry={"Cherry",'f',16,true};
   StudentInfoVec studentinfovec;
   studentinfovec.push_back(micheal);
   studentinfovec.push_back(cherry);
   print(&studentinfovec);
   return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
/*[方式二]  结构体放入堆中，vector中放指针---------------------*/
typedef struct student{
   char* school_name;
   char gender;
   int age;
   bool is_absent;
} StudentInfo;
 
typedefstd::vector<StudentInfo*> StudentInfoPtrVec;
 
void print(StudentInfoPtrVec*stduentinfoptrvec){
   for (int j=0;j<(*stduentinfoptrvec).size();j++)
    {
       std::cout<<
           (*stduentinfoptrvec)[j]->school_name<<"\t"<<
           (*stduentinfoptrvec)[j]->gender<<"\t"<<
           (*stduentinfoptrvec)[j]->age<<"\t"<<
           (*stduentinfoptrvec)[j]->is_absent<<"\t"<<std::endl;
    }
   return;
}
 
int main(){
 
   StudentInfoPtrVec studentinfoptrvec;
 
   char* p_char_1=NULL;
   p_char_1=new char[100];
   strcpy(p_char_1,"Micheal");
   StudentInfo* p_student_1=new StudentInfo;
   p_student_1->school_name=p_char_1;
   p_student_1->gender='m';
   p_student_1->age=18;
   p_student_1->is_absent=false;
   studentinfoptrvec.push_back(p_student_1);
 
   char* p_char_2=NULL;
   p_char_2=new char[100];
   strcpy(p_char_2,"Cherry");
   StudentInfo* p_student_2=new StudentInfo;
    p_student_2->school_name=p_char_2;
   p_student_2->gender='f';
   p_student_2->age=16;
   p_student_2->is_absent=false;
   studentinfoptrvec.push_back(p_student_2);
      
   print(&studentinfoptrvec);
   delete p_char_1;
   delete p_student_1;
   delete p_char_2;
   delete p_student_2;
   return 0;
}