【C++】vector的介绍和使用

👉vector 的介绍👈

1. vector 是表示可变大小数组的序列容器。
2. 就像数组一样，vector 也采用的连续存储空间来存储元素。也就是意味着可以采用下标对 vector 的元素进行访问，和数组一样高效。但是又不像数组，它的大小是可以动态改变的，而且它的大小会被容器自动处理。
3. 本质上，vector 使用动态分配数组来存储它的元素。当新元素插入时候，这个数组需要被重新分配大小为了增加存储空间。其做法是，分配一个新的数组，然后将全部元素移到这个数组。就时间而言，这是一个相对代价高的任务，因为每当一个新的元素加入到容器的时候，vector 并不会每次都重新分配大小。
4. vector 分配空间策略：vector 会分配一些额外的空间以适应可能的增长，因为存储空间比实际需要的存储空间更大。不同的库采用不同的策略权衡空间的使用和重新分配。但是无论如何，重新分配都应该是对数增长的间隔大小，以至于在末尾插入一个元素的时候是在常数时间的复杂度完成的。
5. 因此，vector 占用了更多的存储空间，为了获得管理存储空间的能力，并且以一种有效的方式动态增 长。
6. 与其它动态序列容器相比（deque、list 和 aforward_list）， vector 在访问元素的时候更加高效，在末尾添加和删除元素相对高效。对于其它不在末尾的删除和插入操作，效率更低。比起 list 和 forward_list 统一的迭代器和引用更好。

👉vector 的使用👈

vector 学习时一定要学会查看文档：vector的文档介绍，vector在实际中非常的重要，在实际中我们熟悉常见的接口就可以，下面列出了哪些接口是要重点掌握的。

vector 的构造函数和遍历

vector的构造和遍历代码演示

void vectorTest1()
{
    vector<int> first;                                // empty vector of ints
    vector<int> second(4, 100);                       // four ints with value 100
    vector<int> third(second.begin(), second.end());  // iterating through second
    vector<int> fourth(third);                       // a copy of third
    
    // 用数组来初始化
    // the iterator constructor can also be used to construct from arrays:
    int myints[] = { 16,2,77,29 };
    vector<int> fifth(myints, myints + sizeof(myints) / sizeof(int));
    // []+下标遍历，只有string和vector支持这种方式
    for (size_t i = 0; i < fifth.size(); ++i)
    {
        cout << fifth[i] << ' ';
    }
    cout << endl;

    // 迭代器遍历
    vector<int>::iterator it = fifth.begin();
    while (it != fifth.end())
    {
        cout << *it << ' ';
            ++it;
    }
    cout << endl;

    // 范围for遍历，底层为迭代器
    for (auto e : fifth)
    {
        cout << e << ' ';
    }
    cout << endl;
}
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 iterator

为什么vector str和string str无法取代对方

1. 网络上发送一段字符串，字符串需要以'\0'结束，而 string 无法被发送。
2. string 支持比较字符串大小，比较常见；而 vector 的比较大小不常见，也没有什么意义。
3. 函数接口不完全相同。如 string 类有 +=，而 vector 没有 +=。

vector 空间增长问题

reserve 只负责开辟空间，如果确定知道需要用多少空间，reserve 可以缓解 vector 增容的代价缺陷问题。

resize 在开空间的同时还会进行初始化，影响 size。

reserve 函数接口不会使 vector 缩容，缩容一般是异地缩容，缩容比较大。

resize 的函数接口也能说明内置类型需要有构造函数。

注：在程序里看到的空间都是虚拟的进程空间，进程会提高页表映射和物理内存建立映射。只有在内核层通过页表才能找到物理地址。

注：reserve 只会修改 capacity，不会影响 size。

为什么上面的程序会报错呢？因为 reserve 函数将 capacity 改成了 10，而 size 还是 0，所以就会越界访问，触发了 [ ] 运算符重载的 assert 报错。

我们可以将上面的代码，改成下面代码的样子，就不会出现这个问题了。

void vectorTest3()
{
    vector<int> v;
    v.reserve(10);
    // 或者将v.reserve(10)换成v.resize(10)
    for (size_t i = 0; i < 10; ++i)
    {
        //v[i] = i;
        v.push_back(i);
    }
}
1
2
3
4
5
6
7
8
9
10
11

测试 vector 的默认扩容机制

void TestVectorExpand()
{
    size_t sz;
    vector<int> v;
    sz = v.capacity();
    cout << "making v grow:\n";
    for (int i = 0; i < 100; ++i)
    {
        v.push_back(i);
        if (sz != v.capacity())
        {
            sz = v.capacity();
            cout << "capacity changed: " << sz << '\n';
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

VS 的运行结果

Linux的运行结果

capacity 的代码在 VS 和 g++ 下分别运行会发现，VS 下 capacity 是按 1.5 倍增长的，g++ 是按 2 倍增长的。这个问题经常会考察，不要固化的认为，vector 增容都是 2 倍，具体增长多少是根据具体的需求定义的。VS 是 PJ 版本 STL，g++ 是 SGI 版本 STL。

为什么扩容多数是扩 2 倍？

• 2 倍比较合适。
• 每次扩少了，会导致频繁扩容。
• 每次扩多了，用不完，存在空间浪费。

如果已经确定 vector 中要存储元素大概个数，可以提前将空间设置足够，就可以避免边插入边扩容导致效率低下的问题了。

void TestVectorExpandOP()
{
    vector<int> v;
    size_t sz = v.capacity();
    v.reserve(100); // 提前将容量设置好，可以避免一遍插入一遍扩容
    cout << "making bar grow:\n";
    for (int i = 0; i < 100; ++i)
    {
        v.push_back(i);
        if (sz != v.capacity())
        {
            sz = v.capacity();
            cout << "capacity changed: " << sz << '\n';
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

shift_to_fit 缩容

释放空间由于内存管理的一些原因，不允许分段释放空间，只能整体释放，一般为异地缩容。

👉vector 动态二维数组的理解👈

LeetCode 杨辉三角

给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。

在「杨辉三角」中，每个数是它左上方和右上方的数的和。

C 语言题解

int** generate(int numRows, int* returnSize, int** returnColumnSizes) 
{
    int** ret = malloc(sizeof(int*) * numRows); // 指针数组
    *returnSize = numRows; // 指针数组元素的个数
    *returnColumnSizes = malloc(sizeof(int) * numRows); // returnColumnSizes为一级指针的地址
    for (int i = 0; i < numRows; ++i) 
    {
        ret[i] = malloc(sizeof(int) * (i + 1)); // 让指针数组里的指针都指向一块空间
        (*returnColumnSizes)[i] = i + 1;    // 每一行元素的个数
        ret[i][0] = ret[i][i] = 1;
        for (int j = 1; j < i; ++j) 
        {
            ret[i][j] = ret[i - 1][j] + ret[i - 1][j - 1];
        }
    }
    return ret;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

C++ 题解

class Solution 
{
public:
    vector<vector<int>> generate(int numRows) 
    {
        vector<vector<int>> vv;
        vv.resize(numRows);

        for(size_t i = 0; i < vv.size(); i++)
        {
        	// vv[i]的类型为vector
            vv[i].resize(i + 1); // 开辟空间
            vv[i][0] = vv[i][vv[i].size()-1] = 1;  
        }

        for(size_t i = 0; i < vv.size(); i++)
        {
            for(size_t j = 1; j < i; j++)
            {
                vv[i][j] = vv[i-1][j-1] + vv[i-1][j];
            }
        }
        return vv;
    }
};
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

👉vector 的增删查改👈

operator[ ]和 at 的相同和区别

at() 函数和 [] 运算符的重载，两者都可以得到相应下标的值，并且两者都会去做边界检查。当发生越界行为时，at 是抛异常，operator[] 是报出 assert 错误。assert 断言在 Release 版本下会被优化掉，不会起作用。

补获异常

函数接口什么时候用 const 修饰，什么时候不需要用 const 修饰。

assign

void vectorTest4()
{
    vector<int> v;
    v.push_back(1);
    v.push_back(2);
    v.push_back(3);
    v.push_back(4);

    for (auto e : v)
    {
        cout << e << ' ';
    }
    cout << endl;

    v.assign(10, 1);
    for (auto e : v)
    {
        cout << e << ' ';
    }
    cout << endl;

    string s("hello world");
    v.assign(s.begin(), s.end());
    for (auto e : v)
    {
        cout << e << ' ';
    }
    cout << endl;
}
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

注：assign 的迭代器赋值，迭代器可以是任意类型的迭代器。

insert

注：string 和 vector 可以用迭代器 + 数字的玩法，而 list 没有。因为 string 和 vector 的空间是连续的，而 list 的空间是不连续的。string 和 vector 的正向迭代器为指针，而 list 的迭代器不是指针。

find

注：find 函数是算法库里的函数，并不是 vector 的成员函数（因为每个容器有 find 函数，且功能都一样，所以就就设计成库函数了），使用时需要包algorithm头文件。

那为什么 string 类不直接复用算法库的 find 函数，要自己设计呢？因为 string 类可能要查找一个子串。

swap

注：vector 有专门的模板交换函数，只要是避免使用std::swap这个函数，因为这个函数要 3 次深拷贝。

注：编译器会调用更加匹配的函数接口。