STL库vector
发表于：2024-12-20 | 分类： C++
字数统计: 1.7k | 阅读时长: 8分钟 | 阅读量：

vector ,注意模版

api

构造

推荐设置初始容量减少扩容次数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <iostream>
#include <vector> // 头文件

using namespace std;

int main()
{
    vector<int> v;                 // 默认容量是0
    vector<int> v2(10);            // 初始化10个元素，每个元素都是0
    vector<int> v3(10, 1);         // 初始化10个元素，每个元素都是1
    vector<int> v4{1, 2, 3, 4, 5}; // 初始化5个元素，每个元素分别是1, 2, 3, 4, 5
    vector<int> v5(v4);            // 使用v4初始化v5
    int a[] = {1, 2, 3, 4, 5};
    vector<int> v6(a, a + 5); // 使用数组a初始化v6
    return 0;
}

其他

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <iostream>
#include <vector>

using namespace std;

int main()
{
    vector<int> v(10);
    // 查看有效大小(有值的元素个数)
    cout << v.size() << endl;

    // 查看容量(分配的内存大小)
    cout << v.capacity() << endl;

    // 查看是否为空
    cout << v.empty() << endl; // 1为空，0不为空

    // 重新分配内存大小
    v.resize(5);
    cout << v.size() << endl;

    // v.begin()  // 返回指向vector第一个元素的迭代器
    // v.end()    // 返回指向vector尾后(最后一个元素的下一位置)的迭代器

    // (尾部)插入单个元素
    v.push_back(1); // 外部创建一个临时对象，然后拷贝到到容器

    // 高效插入单个元素
    v.emplace_back(2); // 容器内存位置直接构造对象，不需要创建临时对象

    // (头部)插入多个元素
    v.insert(v.begin(), 2, 3); // 插入2个3

    // (中间)插入元素
    v.insert(v.begin() + 1, 4); // 在第2个位置插入4

    // (尾部)插入多个元素
    v.insert(v.end(), 5, 6); // 插入5个6

    // 访问元素
    cout << v[0] << endl;    // 不推荐类似数组访问，不会检查越界
    cout << v.at(0) << endl; // 推荐使用at，会检查越界

    // 删除元素
    v.pop_back(); // 删除最后一个元素

    // 删除指定元素
    v.erase(v.begin() + 1); // 删除第二个元素(参数是迭代器)

    // 删除指定范围内的元素
    v.erase(v.begin() + 1, v.end() - 1); // 删除第二个到倒数第二个元素

    // 首元素
    cout << v.front() << endl;

    // 尾元素
    cout << v.back() << endl;

    // 清空所有元素
    v.clear(); // 只是将有效大小置为0
    cout << v.size() << endl;
    cout << v.empty() << endl;
    cout << v.capacity() << endl;
    return 0;
}

遍历

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
35
36
37
38
#include <iostream>
#include <vector>

using namespace std;

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

    // 1. 索引遍历
    for (int i = 0; i < vec.size(); i++)
    {
        cout << vec.at(i) << " ";
    }
    cout << endl;

    // 2. 迭代器遍历
    for (vector<int>::iterator it = vec.begin(); it != vec.end(); it++)
    {
        // 注意解引用
        cout << *it << " ";
    }
    cout << endl;

    // 3. auto简化迭代器
    for (auto it = vec.begin(); it != vec.end(); it++)
    {
        cout << *it << " ";
    }
    cout << endl;

    // 4. 范围for (C++11),const表示不需修改
    for (const auto &item : vec)
    {
        cout << item << " ";
    }
    return 0;
}

并发修改异常

描述

下方容器元素使用相同的做测试(使用不同元素，可能结果正确，但是实际类似数组越界【可能不报错，未定义行为】)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream>
#include <vector>

using namespace std;

int main()
{
    vector<int> vec = {3, 3, 3, 3};
    // 错误示例(迭代器失效！)
    for (auto it = vec.begin(); it != vec.end(); it++)
    {
        if (*it == 3)
        {
            vec.erase(it);
        }
    }
    return 0;
}

调试查看容器是[3,3],为什么没有全部删除，为什么是3,3？

  • 开始it=0,删除第一个3，容器元素前移为[3,3,3]
  • it=1,删除此时的第二个元素，容器变为[3,3]
  • it=2,删除此时的第三个元素，显然未定义

也可能系统崩溃，总之未定义行为

解决

原因，容器元素前移导致迭代器指向问题

  • 方式1：从后遍历删除，容器不前移即可
  • 方式2：更新迭代器指向，使用 vec.erase(it)的返回值
  • 方式3：标记删除，把不删除的元素放到新容器
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
#include <iostream>
#include <vector>

using namespace std;

int main()
{
    vector<int> vec = {3, 3, 3, 3};

    // 后遍历删除，普通for
    for (int i = vec.size() - 1; i >= 0; i--)
    {
        if (vec.at(i) == 3)
        {
            vec.erase(vec.begin() + i);
        }
    }

    vector<int> vec1 = {3, 3, 3, 3};

    // 后遍历删除，迭代器
    for (auto it = vec1.end() - 1; it >= vec1.begin(); it--)
    {
        if (*it == 3)
        {
            vec1.erase(it);
        }
    }

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>
#include <vector>

using namespace std;

int main()
{
    vector<int> vec = {3, 3, 3, 3};

    // 遍历删除，更新迭代器
    for (auto it = vec.begin(); it != vec.end();)
    {
        if (*it == 3)
        {
            // 注意erase返回的是下一个元素的迭代器，注意与我们之前的it=0这样的操作区分
            it = vec.erase(it);
        }
        else
        {
            ++it;
        }
    }
    return 0;
}
  • 第一次，it=0，删除第一个=3，容器前移[3,3,3]
  • 第一次后，此时的it指向的是原来的第二个元素(之前的元素的后一个元素)，该元素就是此时【3,3,3】的第一个3，第二次满足条件删除第一个3，此时it指向第二个3，就是元素前移的第一个3
  • …
  • 即迭代器始终指向有效位置
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
#include <vector>

using namespace std;

int main()
{
    vector<int> vec = {3, 3, 3, 3, 4};

    // 遍历删除，标记
    vector<int> vec2; // 这是最终结果
    for (auto it = vec.begin(); it != vec.end(); ++it)
    {
        if (*it != 3)
        {
            // 把不等于3的元素放到vec2中
            vec2.push_back(*it);
        }
    }
    // 把vec2赋值给vec
    vec = vec2;
    return 0;
}

扩容机制

  • 底层动态数组(堆存储，连续存储，随机访问【下标】)，容量不足自动扩容
  • 扩容原理：在内存中动态创建更大的新数组，将原数组数据复制到新数组，指针指向新数组，然后释放旧数组的内存空间
  • 扩容大小：添加元素时自动检查是否需要扩容，扩容公式（n是本次要插入的元素个数）

$$
newSize=currentSize+max(currentSize,n)
$$

  • 如果从0开始，每次插入一个元素，则扩容规律为$currentSize=2^{n-1}$，n代表扩容次数。如100需要要扩容8次
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
#include <vector>

using namespace std;

int main()
{
    vector<int> v;
    v.push_back(1); // 0+max(0,1)=1
    cout << v.capacity() << endl;
    v.push_back(2); // 1+max(1,1)=2
    cout << v.capacity() << endl;
    v.push_back(3); // 2+max(2,1)=4
    cout << v.capacity() << endl;

    v.push_back(4);               // 不会触发扩容，因为capacity=4，有效元素个数也为4
    cout << v.capacity() << endl; // 4

    v.clear(); // size为0，capacity不变为4
    cout << v.size() << endl;
    cout << v.capacity() << endl;
    return 0;
}
STL库 vector
上一篇:
STL库list
下一篇:
值传递、引用、指针

    • Copyright © 2020 - 2024 SimpleWordBlog | Powered by Hexo | Theme Bamboo