C++ STL——Vector

发布于 2021-02-04  0 次阅读


什么是 vector

向量(Vector)是一个封装了动态大小数组的顺序容器(Sequence Container)。跟任意其它类型容器一样,它能够存放各种类型的对象。可以简单的认为,向量是一个能够存放任意类型的动态数组。

容器特性

  1. 顺序序列:顺序容器中的元素按照严格的线性顺序排序。可以通过元素在序列中的位置访问对应的元素。

  2. 动态数组:支持对序列中的任意元素进行快速直接访问,甚至可以通过指针算述进行该操作。操供了在序列末尾相对快速地添加/删除元素的操作。

  3. 能够感知内存分配器的(Allocator-aware):容器使用一个内存分配器对象来动态地处理它的存储需求。

基本函数实现

构造函数

函数名 函数功能
vector( ); 创建一个空的 vector
vector(int nSize); 创建一个 vector,元素个数为 nSize
vector(int nSize, const t& t); 创建一个 vector,元素个数为 nSize,且值均为 t
vector(const vector&); 复制构造函数
vector(begin ,end): 复制 [begin,end) 区间内另一个数组的元素到 vector 中

增加函数

函数名 函数功能
void push_back(const T& x); 向量尾部增加一个元素 x
iterator insert(iterator it, const T& x); 向量中迭代器指向元素前增加一个元素 x
iterator insert(iterator it, int n, const T& x); 向量中迭代器指向元素前增加 n 个相同的元素 x
iterator insert(iterator it, const_iterator first, const_iterator last); 向量中迭代器指向元素前插入另一个相同类型向量的 [first,last) 间的数据

删除函数

函数名 函数功能
iterator erase(iterator it); 删除向量中迭代器指向元素
iterator erase(iterator first,iterator last); 删除向量中 [first,last) 中元素
void pop_back( ); 删除向量中最后一个元素
void clear( ); 清空向量中所有元素

遍历函数

函数名 函数功能
reference at(int pos); 返回 pos 位置元素的引用
reference front( ); 返回首元素的引用
reference back( ); 返回尾元素的引用
iterator begin( ); 返回向量头指针,指向第一个元素
iterator end( ); 返回向量尾指针,指向向量最后一个元素的下一个位置
reverse_iterator rbegin(); 反向迭代器,指向最后一个元素
reverse_iterator rend( ); 反向迭代器,指向第一个元素之前的位置

判断函数

函数名 函数功能
bool empty( ) const; 判断向量是否为空,若为空,则向量中无元素

大小函数

函数名 函数功能
int size( ) const; 返回向量中元素的个数
int capacity( ) const; 返回当前向量所能容纳的最大元素值
int max_size( ) const; 返回最大可允许的 vector 元素数量值

其他函数

函数名 函数功能
void swap(vector&); 交换两个同类型向量的数据
void assign(int n,const T& x); 设置向量中前 n 个元素的值为 x
void assign(const_iterator first, const_iterator last); 向量中 [first,last) 中元素设置成当前向量元素

简单介绍

  1. Vector<类型>标识符
  2. Vector<类型>标识符(最大容量)
  3. Vector<类型>标识符(最大容量,初始所有值)
  4. Int i[5]={1,2,3,4,5}
    Vector<类型>vi(I,i+2); //得到i索引值为3以后的值
  5. Vector< vector< int> >v; 二维向量 //这里最外的<>要有空格。否则在比较旧的编译器下无法通过

实例

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstdlib>
#include <ctime>

using namespace std;

void print(vector<int> v)
{
    cout << "vector v 中的元素为 [";
    for (int i = 0; i < v.size() - 1; i++) cout << v[i] << "," << " ";
    cout << v[v.size() - 1] << "]" << endl;
}

int main()
{
    vector<int> obj;                               // 创建一个向量存储容器 List
    obj.push_back(1);
    obj.push_back(2);                              // push_back(elem) 在数组最后添加数据
    obj.push_back(3);
    obj[2] = 4;
    print(obj);                                    // 1, 2, 4

    obj.insert(obj.begin() + 2, 3);     // 在第 3 个位置插入数字 3
    print(obj);                                    // 1, 2, 3, 4

    for (int i = 0; i < 5; i++) obj.push_back(i);
    print(obj);                                    // 1, 2, 3, 4, 0, 1, 2, 3, 4
    for (int i = 0; i < 5; i++) obj.pop_back();    //去掉数组最后一个数据
    print(obj);                                    // 1, 2, 3, 4

    obj.clear();                                   // 清空数组
    obj.push_back(1);
    print(obj);                                    // 1

    srand((int) time(NULL));
    for (int i = 0; i < 9; i++) obj.push_back(rand() % 100);
    sort(obj.begin(), obj.end());
    print(obj);

    vector<int>::iterator it;                      //声明一个迭代器,来访问 vector 容器,作用:遍历或者指向 vector 容器的元素
    for (it = obj.begin(); it != obj.end(); it++) cout << *it << " ";
    cout << endl;

    int n = 5, m = 6;
    vector<vector<int>> v(n);                      //定义二维动态数组大小 5 行
    for (int i = 0; i < v.size(); i++)             //动态二维数组为 5 行 6 列,值全为 0
        v[i].resize(m);
    for (int i = 0; i < v.size(); i++)             //输出二维动态数组
    {
        for (int j = 0; j < v[i].size(); j++) cout << v[i][j] << " ";
        cout << endl;
    }
    cout << endl;

    vector<vector<int> > x(n, vector<int>(m));     //定义二维动态数组 5 行 6 列
    for (int i = 0; i < x.size(); i++)             //输出二维动态数组
    {
        for (int j = 0; j < x[i].size(); j++) cout << x[i][j] << " ";
        cout << endl;
    }
    return 0;
}

输出结果:

vector v 中的元素为 [1, 2, 4]
vector v 中的元素为 [1, 2, 3, 4]
vector v 中的元素为 [1, 2, 3, 4, 0, 1, 2, 3, 4]
vector v 中的元素为 [1, 2, 3, 4]
vector v 中的元素为 [1]
vector v 中的元素为 [1, 21, 21, 22, 30, 31, 40, 42, 54, 72]
1 21 21 22 30 31 40 42 54 72
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0

0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0

例题

洛谷 P3156 深基15.例1询问学号

题目描述

n(n \le 2 \times 10^6) 名同学陆陆续续进入教室。我们知道每名同学的学号(在 110^9 之间),按进教室的顺序给出。上课了,老师想知道第 i 个进入教室的同学的学号是什么(最先进入教室的同学 i =1),询问次数不超过 10^5 次。

输入格式

第一行 2 个整数 n 和 m,表示学生个数和询问次数。

第二行 n 个整数,表示按顺序进入教室的学号。

第三行 m 个整数,表示询问第几个进入教室的同学。

输出格式

m 个整数表示答案,用换行隔开。

输入输出样例

输入 #1

10 3
1 9 2 60 8 17 11 4 5 14
1 5 9

输出 #1

1
8
5

AC代码

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    vector<int> v;
    int n, m;
    cin >> n >> m;
    while (n--)
    {
        int t;
        cin >> t;
        v.push_back(t);
    }
    while (m--)
    {
        int t;
        cin >> t;
        cout << v[t - 1] << endl;
    }
    return 0;
}

洛谷 P3613 【深基15.例2】寄包柜

题目描述

超市里有 n(n\le10^5) 个寄包柜。每个寄包柜格子数量不一,第 i 个寄包柜有 a_i(a_i\le10^5) 个格子,不过我们并不知道各个 a_i 的值。对于每个寄包柜,格子编号从 1 开始,一直到 a_i。现在有 q(q\le10^5) 次操作:

  • 1 i j k:在第 i 个柜子的第 j 个格子存入物品 k(0\le k\le 10^9)。当 k$=0$ 时说明清空该格子。
  • 2 i j:查询第 i 个柜子的第 j 个格子中的物品是什么,保证查询的柜子有存过东西。

已知超市里共计不会超过 10^7 个寄包格子,a_i 是确定然而未知的,但是保证一定不小于该柜子存物品请求的格子编号的最大值。当然也有可能某些寄包柜中一个格子都没有。

输入格式

第一行 2 个整数 n 和 q,寄包柜个数和询问次数。

接下来 q 个整数,表示一次操作。

输出格式

对于查询操作时,输出答案。

输入输出样例

输入 #1

5 4
1 3 10000 114514
1 1 1 1
2 3 10000
2 1 1

输出 #1

114514
1

AC代码

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    int n, q;
    cin >> n >> q;
    vector<vector<int> > v(n + 1);
    while (q--)
    {
        int t;
        cin >> t;
        if (t == 1)
        {
            int i, j, k;
            cin >> i >> j >> k;
            if (v[i].size() < j + 1)
                v[i].resize(j + 1);
            v[i][j] = k;
        }
        if (t == 2)
        {
            int i, j;
            cin >> i >> j;
            cout << v[i][j] << endl;
        }
    }
    return 0;
}

大变に气分がいい