C++ - Vector

编程 评论

C++ 学习笔记
C++ vector 容器浅析

数组

简介

  • 数组其实是一个指针

    1
    2
    int example[5]; // in stack
    int* ptr = example;

  • 数组取值的两种方式

    1
    2
    3
    4
    5
    *(example+2) = 5;
    example[1] = 3;

    *(ptr+2) = 5;
    ptr[1] = 3;

  • 一段神奇的代码

    1
    2
    3
    4
    5
    6
    // error, 申请数组变量大小不可以是变量
    int size = 5;
    int a[size];
    // correct
    static const int size = 5;
    int a[size];

mem in stack/heap

  • C++ 程序中的内存分为两个部分：
    • 栈（stack）：在函数内部声明的所有变量都将占用栈内存。
    • 堆（heap）：这是程序中未使用的内存，在程序运行时可用于动态分配内存
  • 在 C++ 中，您可以使用特殊的运算符（new）为给定类型的变量在运行时分配堆（heap）内的内存，这会返回所分配的空间地址。
  • 如果您不再需要动态分配的内存空间，可以使用 delete 运算符，删除之前由 new 运算符分配的内存

标准库的数组

1
2
3
4
5
6
7
8
9
10
11
12
#include <iostream>
#include <array>

#pragma pack(2)

int main() {
   std::array<int, 5> e;

   std::cout<< e.size() << std::endl;

    return 0;
}

什么是vector？

  • 向量（Vector）是C++中的一种数据结构,确切的说是一个类。一个封装了动态大小数组的顺序容器（Sequence Container）。跟任意其它类型容器一样，它能够存放各种类型的对象。vector是一个能够存放任意类型的动态数组。

  • 使用vector之前要导入头文件

    1
    #include<vector>

  • 其中vector是一个定义于namespace std内的模板（template）：

    1
    2
    3
    4
    namespace std{
        template <class T, class Allocator = allocator<T> >
        class vector;
    }

  • vector中的元素可以使任意类型，但是必须能够赋值和拷贝。第二个参数可有可无，是用来定义内存模型（memory model），缺省的内存模型是C++标准库提供的allocator。

容器特性

  • 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中

  • demo

    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
    #include <iostream>
    #include <vector>

    using namespace std;

    void show(vector<int> v) {
        cout << "vector : ";
        for (auto val : v) {
            cout << val << " ";
        }
        cout << endl;
    }

    int main() {
        vector<int> v; //定义一个空 vector 对象
        vector<int> v1(10); //定义一个具有 10 个元素的 vector 对象（int 型元素默认初始化为 0）
        vector<int> v2(3,5); //v = { 5, 5, 5 }
        vector<int> v3(v); //v1 = v
        vector<int> v4 = { 1, 2, 3 };
        vector<int> v5 = v;


        show(v);
        show(v1);
        show(v2);
        show(v3);
        show(v4);
        show(v5);
    }

  • 结果如下

    1
    2
    3
    4
    5
    6
    vector : 
    vector : 0 0 0 0 0 0 0 0 0 0 
    vector : 5 5 5 
    vector : 
    vector : 1 2 3 
    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)间的数据 
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
#include <iostream>
#include <vector>

using namespace std;

void show(vector<int> v) {
    cout << "vector : ";
    for (auto val : v) {
        cout << val << " ";
    }
    cout << endl;
}

int main() {
    vector<int> v = { 1, 2, 3 };

    v.push_back(4); // v = { 1, 2, 3, 4 };
    show(v);

    v.insert(v.begin(), 4); // v = { 4, 1, 2, 3, 4 };
    show(v);

    v.insert(v.begin(), 3,0); // v = { 0, 0, 0, 4, 1, 2, 3, 4 };
    show(v);

    vector<int> v1 = { 1, 2 };
    vector<int> v2 = { 3, 4 };
    v2.insert(v2.begin(), v1.begin(), v1.end()); // v = { 1, 2, 3, 4 };
    show(v2);
}
  • 结果如下
    1
    2
    3
    4
    vector : 1 2 3 4 
    vector : 4 1 2 3 4 
    vector : 0 0 0 4 1 2 3 4 
    vector : 1 2 3 4

删除函数

函数名 说明
iterator erase(iterator it) 删除向量中迭代器指向元素
iterator erase(iterator first,iterator last) 删除向量中[first,last)中元素
void pop_back() 删除向量中最后一个元素
void clear() 清空向量中所有元素 
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
#include <iostream>
#include <vector>

using namespace std;

void show(vector<int> v) {
    cout << "vector : ";
    for (auto val : v) {
        cout << val << " ";
    }
    cout << endl;
}

int main() {
    vector<int> v = { 1, 2, 3, 4, 5 };

    v.pop_back(); // v = {1, 2, 3, 4};
    show(v);

    v.erase(v.begin()); // v = { 2, 3, 4};
    show(v);

    v.erase(v.begin(), v.begin()+2); // v = {4};
    show(v);

    v.clear(); // v = {};
    show(v);
}
  • 结果如下
    1
    2
    3
    4
    vector : 1 2 3 4 
    vector : 2 3 4 
    vector : 4 
    vector :

遍历函数

函数名 说明
reference at(int pos) 返回pos位置元素的引用
reference front() 返回首元素的引用
reference back() 返回尾元素的引用
iterator begin() 返回向量头指针，指向第一个元素
iterator end() 返回向量尾指针，指向向量最后一个元素的下一个位置
reverse_iterator rbegin() 反向迭代器，指向最后一个元素
reverse_iterator rend() 反向迭代器，指向第一个元素之前的位置 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <iostream>
#include <vector>

using namespace std;

int main() {
    vector<int> v = { 1, 2, 3, 4, 5 };

    cout << v.at(2) << endl;
    cout << v[2] << endl;
    cout << v.front() << endl;
    cout << v.back() << endl;
    cout << *v.begin() << endl; // 数组头元素的指针
    cout << *(v.end()-1) << endl; // 数组最后一个元素的下一个位置指针
}
  • 结果如下
    1
    2
    3
    4
    5
    6
    3
    3
    1
    5
    1
    5

判断函数

函数名 说明
bool empty() const 判断向量是否为空，若为空，则向量中无元素 
1
2
3
4
5
6
7
8
9
10
11
12
#include <iostream>
#include <vector>

using namespace std;

int main() {
    vector<int> v1 = { 1, 2, 3, 4, 5 };
    vector<int> v2;

    cout << "v1 is empty : " << v1.empty() << endl;
    cout << "v2 is empty : " << v2.empty() << endl;
}
  • 结果如下
    1
    2
    v1 is empty : 0
    v2 is empty : 1

大小函数

函数名 说明
int size() const 返回向量中元素的个数
int capacity() const 返回当前向量张红所能容纳的最大元素值
int max_size() const 返回最大可允许的vector元素数量值 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
#include <vector>

using namespace std;

void show(vector<int> v) {
    cout << "vector : ";
    for (auto val : v) {
        cout << val << " ";
    }
    cout << endl;
}

int main() {
    vector<int> v1 = { 1, 2, 3, 4, 5 };

    cout << "size : " << v1.size() << endl;
    cout << "capacity : " << v1.capacity() << endl;
    cout << "max_size : " << v1.max_size() << endl;
}
  • 结果如下
    1
    2
    3
    size : 5
    capacity : 5
    max_size : 4611686018427387903

其他函数

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

小技巧

使用 C++ 11 新特性访问

1
2
3
4
5
6
7
vector<int> v = { 1, 2, 3, 4 };
//将 v 中值为奇数的元素置为 0
for (auto n : v) {
    if (n%2) 
        cout << n;
}
// 输出：1 3

查找一个元素是否在 vector 中

1
2
3
vector<int> v = { 1, 2, 3, 4 };
auto it_1 = find(v.begin(), v.end(), 1); // it_1 = v.begin();
autp it_2 = find(v.begin(), v.end(), 9); // it_2 = v.end();

倒序遍历

1
2
3
4
5
6
vector<int> nums = {1,2,3,4,5,6,7};
auto begin = nums.rbegin();
while (begin != nums.rend()) {
    cout << *begin << endl;
    begin++;
}

Vector 和 数组的区别

  • 数组是c++中类似vector的数据结构，它们都可以对一种类型进行储存，既都是容器。虽说两者有相似之处，但也有显著的区别，c++ primer的作者说到，在实际的编程中，我们作为程序员应该避免用到低级数组和指针，而更应该多用高级的vector和迭代器。
    对比图

一些使用 vector 的建议

  • 好好使用 reserve 方法（用于申请足够的空间来储存变量），可以有效的减少 容量不足->重新申请空间->copy 的过程

QinHanGame Developer & Designer

当你发现自己的才华撑不起野心时，就请安静下来学习吧！