第四课 动态数组

作者： 作者的头像   huolong , 时间：2023-01-10 20:25:50 , 所有人可见, 阅读  13

vector入门

vector是Cpp标准库中的一个类，与数组颇为相似，不同之处在于，vector可以自动扩展容量，故可以将其视为会自动扩展容量的数组。vector是Cpp标准程序库中的众多容器（container）之一，能够像容器一样存放各种类型的对象，简单地说，vector是一个能够存放任意类型数据的动态数组。

string和vector实现一样。 为了支持快速随机访问，vector中对象在内存中必须是连续存储的。

为了可以使用vector，需要在你的头文件中包含下面的代码：

#include <vector>
using namespace std;

定义一个长度为10，每个元素的值为-1的vector数组 vector<int> a(10, -1);

如何定义10个vector vector<int> a[10];

API函数

size()和empty()是所有容器中都有的API，时间复杂度是O(1)的。但是clear()就不是，队列中就没有clear() ，vector倍增的思想——C++中，系统为某一程序分配空间的时候，所需的时间与空间大小无关，与申请次数有关。所以使用vector的时候，尽可能地减少申请次数。32->64->128，先开一个32的，不够了倍增，变成64的，然后go on。 假如数组长度为n, 申请空间(开辟空间)次数是O(log n)，额外的copy的次数均摊是O(1)，比如push()操作。 从而可见倍增的好处——申请空间的次数不多，并且额外操作的次数也不多。

容量空间 接口说明
size 获取数据个数
capacity 获取容量大小
empty 判断是否为空
resize 改变vector的size
reserve 改变vector的capacity 
int main()  
{  
    vector<int> b;
    //reserve只负责开空间，如果确定要开多少空间，可以直接用reverse缓解vector增容的代价缺陷问题。
    //b.reserve(1024);
    for(int i=0; i<100; i++){
        b.push_back(i);
        //长度n的，只需要倍增 O(log(n)) 
        cout <<b.size() << " " << b.capacity() << endl;
    }
    return 0;
}

size()时间复杂度是O(1)

empty()时间复杂度是O(1)

clear()

front()/back()

push_back()/pop_back()

begin()/end() a.begin() = a[0]，a.end() = a[a.size()]，其中end()表示最后一个数的后面一个数

支持比较运算，按字典序——黑科技

#include <bits/stdc++.h>
using namespace std;

int main()
{
    vector<int> a(4, 3);
    vector<int> b(3, 4);
    cout << (a < b) << endl;//输出：1
    return 0;
}

erase() vector的删除操作的时间复杂度是O(n)的

erase删除区间 erase(v.begin()+l,v.begin()+r)

使用了这样的删除语句后，原vector的[l,r)之间的元素会被删去

输入 10 1 2 3 4 5 6 7 8 9 10 删去区间在[2,5)的元素

erase(v.begin()+2,v.begin()+5)

输出 1 2 3 4 5 6 7 8 9 10 1 2 6 7 8 9 10 

#include<bits/stdc++.h>
using namespace std;
int n,a[20];
int main()
{
    vector<int> v;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
        v.push_back(a[i]);            
    }
    for(auto x:v) cout<<x<<" ";
    v.erase(v.begin()+2,v.begin()+5);   //删除在[2,5)间的元素(第2,3,4号元素)
    puts("");
    for(auto x:v) cout<<x<<" ";
    return 0;
}

erase循环删除某个元素会有个巨坑！深坑！vector.erase()函数的常见陷阱  

vector<int> v(10000, 10);
    v.front() = 10;
    v.back() = 10;
    v.pop_back();
    for (vector<int>::iterator it = v.begin(); it != v.end(); )
    {
        if (*it == 10)
        {
            it = v.erase(it); 
        }else{
            it++;
        }
    }

举例：删除前导0

int main()  
{  
    vector<int> b(1000, 0);
    b.push_back(2);
    b.push_back(0);
    b.push_back(4);
    bool is_f = true;
    for (auto it = b.begin(); it != b.end(); )
    {
        if (*it == 0 && b.size() > 1 && is_f)
        {
            b.erase(it);
        }
        else{
            is_f = false;
            it++;
        }

    }

    for(auto i : b){
        cout << i <<endl;
    }

    return 0;
}

总结：

1.初始化 ① 初始化一个不定长容器

vector<int> a;

② 初始化一个长度为10的容器

vector<int> a(10);

③ 初始化一个长度为10的容器，每个元素赋值为-1

vector<int> a(10, -1);

④ 把a数组复制到vector内

int a[2] = {1, 2};
vector<int> f(a, a + 2);

⑤ 把vector a复制到vector中

vector <int> a;
a.push_back(1);
vector<int> b(a);

// 或者取任意长度复制
vector <int> a;
a.push_back(1);
vector<int> b(a.begin(), a.end());

2.求长度(时间复杂度为O(1))

vector<int> a;
a.size();

3.判空(时间复杂度为O(1))

vector<int> a;
a.empty();

4.清空

vector<int> a;
a.clear();

5.随机访问

vector<int> a;
a.front(); // 取第一个数
a.back();  // 取最后一个数
a[10];  // 取第11个元素，下标为10

6.删除元素/插入元素

vector<int> a;
a.push_back();   // 插入一个元素
a.pop_back();  // 删除一个元素
a.insert(a.begin(), k);  // 在开头插入数字k

7.迭代器

vector<int> a;
a.begin();  // 第一个元素的迭代器
a.end();  // 最后一个元素的下一位的迭代器

8.遍历

// 1.下标遍历
for (int i = 0; i < a.size(); ++i) cout << a[i] << ends;

// 2.迭代器遍历
for (vector <int> :: iterator it = a.begin(); it != a.end(); ++it)
    cout << *it << ends;

for (auto = a.begin(); it != a.end(); ++it)//自动推导
    cout << *it << ends;

// 3. c++方式遍历
for (auto ai: a) cout << ai << ends;

9.比较运算（vector支持按照字典序进行比较）

#include <bits/stdc++.h>

using namespace std;

int main()
{
    vector<int> a(4, 3);
    vector<int> b(3, 4);
    cout << (a < b) << endl;
    return 0;
}
输出：1

10.常见函数 sort 排序 reverse 逆序 find 查找 以及区间最值的常见函数。

以下着重介绍vector的常见用法：

1） 创建一个vector，有多种方法。

vector< 类型 > 标识符 ; //如vector< int> Vint ;
vector< 类型 > 标识符(最大容量) ; // 如vector< int> Vint(100)创建包含100个int数据的vector ;
vector< 类型 > 标识符（最大容量，初始所有值）; // 如vector< int> Vint(100，int(10))极为创建包含100个int数据(均初始化为10)的vector ;
vector< 类型 > 标识符（该类型vector对象）; // 如vector< int> Vint2(Vint)创建了一个Vint的拷贝

2） 利用数组初始化vector

int i[10] ={0,1,2,3,4,5,6,7,8,9} ; 
vector<int> v(i+1,i+9);//使用数组对C++ Vector进行初始化
其中i+1,i+9表示从数组的第一个值到第九个值之前的值，即i[1]到i[8]

3） vector二维对象定义，相当于二维数据。

vector< int > v(100,int(9));//创建包含100个int数据的vector 
vector< vector<int> > v2;//二维容器
for(int i =0;i<10;i++)
{
    v2.push_back(v);
}

4） 元素访问方法

vec[i] - 访问索引值为 i 的元素引用。 (索引值从零起算，故第一个元素是vec[0]。)
vec.at(i) - 访问索引值为 i 的元素的引用，以 at() 访问会做数组边界检查，如果访问越界将会抛出一个例外，这是与operator[]的唯一差异。
vec.front() - 回传 vector 第一个元素的引用。
vec.back() - 回传 vector 最尾元素的引用。

5） 新增或移除元素

vec.push_back() - 新增元素至 vector 的尾端，必要时会进行存储器配置。
vec.pop_back() - 删除 vector 最尾端的元素。
vec.insert() - 插入一个或多个元素至 vector 内的任意位置。
vec.erase() - 删除 vector 中一个或多个元素。
vec.clear() - 清空所有元素。

6）   取得长度/容量

vec.size() - 取得 vector 目前持有的元素个数。
vec.empty() - 如果 vector 内部为空，则传回 true 值。
vec.capacity() - 取得 vector 目前可容纳的最大元素个数。这个方法与存储器的配置有关，它通常只会增加，不会因为元素被删减而随之减少。

7）   重新配置／重设长度

vec.reserve() - 如有必要，可改变 vector 的容量大小（配置更多的存储器）。在众多的 STL 实做，容量只能增加，不可以减少。
vec.resize() - 改变 vector 目前持有的元素个数。

8）  迭代 (Iterator)

vec.begin() - 回传一个Iterator，它指向 vector 第一个元素。
vec.end() - 回传一个Iterator，它指向 vector 最尾端元素的下一个位置（请注意：它不是最末元素）。
vec.rbegin() - 回传一个反向Iterator，它指向 vector 最尾端元素的。
vec.rend() - 回传一个Iterator，它指向 vector 的第一个元素。

9）  vector排序

vector< int > v ;   
v.push_back(11);  
v.push_back(7);  
v.push_back(15);  
sort(v.begin() , v.end()); // 从小到大  
reverse(v.begin(),v.end()) // 从大到小

10） vector查找

vector < int > v ;   
for( int i = 0 ; i < 10 ; i ++ )  
{  
    vector.push_back(i);  
}
//find方法需引入#include<algorithm>>
vector < int >::interator itr = find(v.begin() , v.end(), 7) ;  
cout << *itr << endl ; ///返回容器内找到值的位置。

11） vector访问

for(int i = 0 ; i < 10 ; i ++) // 第一种方法  
    cout <<v[i] <<" " ;   
cout<<endl;

vector<int>::iterator itr;
for(itr = v.begin();itr!= v.end();itr++)//第二种方法
    cout<<*itr<<" ";
cout<<endl;

vector<int> v(10, -1);
for(auto i : v){   //第三种方法
    cout << i << endl;
}

一段完整代码示例：

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int main(int argc,char* argv[])
{
    int i[11] ={0,1,2,3,4,5,6,7,8,9,10} ; 
    vector<int> v(i,i+10);//使用数组对vector进行初始化
    //vector< int > v(100,int(9));//创建包含100个int数据的vector ;
    //vector< int > v ;

    // for(int i = 0; i < 10; i++ )//插入项方式初始化
    //  v.push_back( i );

    vector<vector<int>> v2;//二维容器
    for(int i =0;i<10;i++)
    {
        v2.push_back(v);
    }

    cout<<"方法一输出："<<endl;
    for(int i = 0 ; i < 10 ; i ++) // 第一种方法  
        cout <<v[i] <<" " ;   
    cout<<endl;

    cout<<"方法二输出："<<endl;
    vector<int>::iterator itr;
    for(itr = v.begin();itr!= v.end();itr++)//第二种方法
        cout<<*itr<<" ";
    cout<<endl;

    vector<int>::iterator itr2 = find(v.begin(),v.end(),7);//查找
        cout<<"数据7的位置"<< *itr2<<endl;

    system("pause");
    return 0;
}

区间最值的常见函数：

#include<bits/stdc++.h>  
using namespace std;  

int main()  
{  
    vector<int> a;
    a.push_back(1);
    a.push_back(2);
    a.push_back(3);
    int sum = accumulate(a.begin(),a.end(),0); //求和 
    int max_val = *max_element(a.begin(),a.end());//最大值 
    int min_val = *min_element(a.begin(),a.end());//最小值 
    //nth_element函数能快速的找到第几大的数，但不能同时保证数组是有序的
    //而sort函数也能找到第几大的数，同时能保证数组是有序的，但找的时间不如nth_element函数要快

    nth_element(a.begin(), a.begin()+1,a.end());//默认第k小值 

    cout << sum << " " << max_val << " " << min_val << " " << a[1] ;
    return 0;
}

—— 本文来自火龙信奥（义乌睿码科技）：义乌青少年信息学奥赛与编程教育平台，专注 CSP-J/S、NOIP、GESP 竞赛培训，线上线下融合教学，助力编程升学。网址：hlcoding.com