〖算法面试刷题〗C++动态数组类vector！

C++动态数组类vector！

一. vector介绍

• 在程序设计过程中，如果我们知道数组的长度，可以定义静态数组。实际上，我们会经常遇到数组长度在一开始并不能确定的情况，那么这个时候就需要考虑用动态数组了，这样不仅节省了存储的内存，还使得程序更加灵活可靠。
• vector是STL中最常见的容器，它是一种顺序容器，支持随机访问。vector是一块连续分配的内存，从数据安排的角度来讲，和数组极其相似，不同的地方就是：数组是静态分配空间，一旦分配了空间的大小，就不可再改变了；而vector是动态分配空间，随着元素的不断插入，它会按照自身的一套机制不断扩充自身的容量。
• vector的扩充机制：按照容器现在容量的一倍进行增长。vector容器分配的是一块连续的内存空间，每次容器的增长，并不是在原有连续的内存空间后再进行简单的叠加，而是重新申请一块更大的新内存，并把现有容器中的元素逐个复制过去，然后销毁旧的内存。这时原有指向旧内存空间的迭代器已经失效，所以当操作容器时，迭代器要及时更新。

二. 定义和初始化

#include<iostream>
#include<vector>
using namespace std;
int main(){
    vector<int> arr1;          //声明一个int型向量
    vector<int> arr2(10);      //声明一个初始大小为10的int型向量
    vector<int> arr3(10, 1);   //声明一个初始大小为10且值都是1的int型向量
    vector<int> arr4 = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};   //声明一个int型变量并依次赋值
    vector<int> arr5(arr4);    //声明并用tmp向量初始化vec向量
    vector<int> vec(arr4.begin(), arr4.begin()+3);        //用向量arr4的第0个到第2个值初始化vec向量

    int a[5] = {1, 2, 3, 4, 5};   
    vector<int> vec1(a, a + 5);                        //将arr数组的元素用于初始化vec向量
    vector<int> vec2(&a[1], &a[4]);                    //将arr[1]~arr[4]范围内的元素作为vec的初始值

    vector<vector<int>> vec3;                          //声明一个二维数组
    vector<vector<int>> vec4(4);                       //声明一个4行的二维数组
    vector<vector<int>> vec5(4, vector<int>(5, 6));     //声明一个4行5列的二维数组并赋值维6
    
    system("pause");
    return 0;
}

三. 赋值和获取长度

#include<iostream>
#include<vector>
using namespace std;
int main(){
    vector<int> v1{0, 3, 5, 7, 8, 1, 4, 9, 2, 6};     // 赋值时会先清空数组
    vector<int> v2;

    //v2.assign(v1.ita,v1.itb)                   将动态数组v1的[ita,itb)赋值给动态数组v2
    v2.assign(v1.begin(), v1.begin()+8);

    //v.assign(n,p)                              给动态数组v赋值n个元素p
    v2.assign(10, 7);

    vector<int> vec(4);
    int len = vec.size();             // len = 4;获取长度（size）

    system("pause");
    return 0;
}

四. 重置大小(resize)和数组访问

重置大小配合初始化使用，随心所欲设定数组。

#include<iostream>
#include<vector>
using namespace std;
int main(){
    vector<vector<int>> v1(4);        //声明一个4行的二维数组，对每行分别定义列数为5并赋值
    for(int i=0;i<4;i++){
        v1[i].resize(5, 6);
    }

    vector<vector<int>> array;
    array.resize(3, vector<int>(4));  //修改二维数组大小为3行4列

    system("pause");
    return 0;
}

数组访问有下标访问、迭代器访问、指针访问及其他等方式。

#include<iostream>
#include<vector>
using namespace std;
int main(){
    vector<int> v1{1, 2, 3, 4, 5};      //声明一个4行的二维数组，对每行分别定义列数为5并赋值
    
    //1、通过下标访问数组
    for(int i=0;i<v1.size();i++){
        cout<<v1[i]<<" ";
    }
    cout<<endl;
    //2、通过迭代器访问数组
    for(vector<int>::iterator iter=v1.begin(); iter != v1.end(); iter++){
        cout<<*iter<<" ";                        //依次输出 1 2 3 4 5
    }
    cout<<endl;
    //3、通过指针访问数组
    int *p=v1.data();
    for(int i=0;i<v1.size();i++){
        cout<<*p++<<" ";
    }

    system("pause");
    return 0;
}

五. 插入和删除元素

插入元素。

#include<iostream>
#include<vector>
using namespace std;
int main(){
    vector<int> v;
    v.push_back(1);  //v.push_back(p)在数组v的末尾添加元素p
    v.push_back(2);               
    v.push_back(3);

    v.insert(v.begin(), 9);
    v.insert(v.begin()+3, 10);
    v.insert(v.end(), 20);

    for(int i=0;i<v.size();i++){
        cout<<v[i]<<" ";
    }
    system("pause");
    return 0;
}

删除元素，使用时，要清楚数组在时刻变化。

#include<iostream>
#include<vector>
using namespace std;
int main(){
    vector<int> v{1, 2, 3, 4, 5, 6, 7, 8, 9};
    v.pop_back(); //v.pop_back()删除数组v末尾的元素
    v.pop_back();   
    v.pop_back();

    v.erase(v.begin()); //v.erase(v.it) 删除数组v.it指向位置的元素 
    v.erase(v.begin()+2);
    v.erase(v.end()-1);

    system("pause");
    return 0;
}

六. 交换,反转(swap,reverse)

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main(){
    vector<int> v1{1, 2, 3};
    vector<int> v2{4, 5, 6};
    swap(v1, v2);                   //或者v1.swap(v2)，输出结果相同
    reverse(v1.begin(), v1.end());  //反转数组中的元素

    system("pause");
    return 0;
}

七. 排序(sort)

sort(begin, end, cmp)，其中begin为指向待sort()的数组的第一个元素的指针，end为指向待sort()的数组的最后一个元素的下一个位置的指针，cmp参数为排序准则，如果没有的话，默认以非降序排序。

• 默认形式。

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main(){
    vector<int> v{0, 3, 5, 7, 8, 1, 4, 9, 2, 6};
    sort(v.begin(), v.end());  //默认情况下升序排列
    for(int i=0;i<v.size();i++){
        cout<<v[i]<<" ";
    }
    cout<<endl;
    system("pause");
    return 0;
}

• 自定义cmp参数。

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

//可自定义排序方式（此为降序）
bool cmp(int &a, int &b){
    return a>b;
}

int main(){
    vector<int> v{0, 3, 5, 7, 8, 1, 4, 9, 2, 6};
    sort(v.begin(), v.end(), cmp);  
    for(int i=0;i<v.size();i++){
        cout<<v[i]<<" ";
    }
    cout<<endl;
    system("pause");
    return 0;
}

八. 清除和空判断(clear,empty)

#include<iostream>
#include<vector>
using namespace std;

int main(){
    vector<int> v{0, 3, 5, 7, 8, 1, 4, 9, 2, 6};
    v.clear();         // v = {}；
    v.empty();         // 1  (v为空则输出1)
    system("pause");
    return 0;
}

参考文章

参考了以下作者的文章，这里表示感谢！

• c++之vector用法
• c++动态数组vector的使用
• C++中sort()的使用