当前位置 : 主页 > 编程语言 > java >

面试官都在问 | vector 基本使用

来源:互联网 收集:自由互联 发布时间:2022-10-14
vector 基本使用 vector 是 C++ STL 中最常用的容器, 也是面试中的常见考点. 以下内容向大家介绍 vector 的最常见用法. 1. 头文件 vector 是标准库中的组件. 使用时需要包含相关头文件. #includ


vector 基本使用

vector 是 C++ STL 中最常用的容器, 也是面试中的常见考点. 以下内容向大家介绍 vector 的最常见用法.

1. 头文件

vector 是标准库中的组件. 使用时需要包含相关头文件.

#include <vector>

2. 实例化

vector 是一个类模板, 在实例化的时候需要指定模板参数.

// 包含头文件
#include <vector>
#include <string>

int main() {
// 实例化时需要指定模板参数.
// C++ 98/03 要求模板参数必须是具备拷贝构造函数的.
// C++ 11 要求模板参数具有转移构造函数也可以.
std::vector<int> ivec;
std::vector<std::string> svec;
return 0;
}

注意: 啥样类型的元素可以放到 vector 中呢?

  • 在 C++98/03 标准中, 存放到 vector 中的元素必须拥有拷贝构造函数(vector中存放的是元素的副本)
  • 在 C++11 标准中, 存放在 vector 中的元素, 如果没有拷贝构造函数, 但是有转移构造函数, 也是可以的.
  • 3. 新增元素

    3.1 尾插

    #include <vector>
    #include <iostream>

    int main() {
    std::vector<int> ivec;

    // 使用 push_back 尾插元素.
    // 未触发扩容时时间复杂度 O(1).
    // 触发扩容时时间复杂度为 O(N).
    ivec.push_back(1);
    ivec.push_back(2);
    ivec.push_back(3);
    ivec.push_back(4);

    for (int x : ivec) {
    std::cout << x << std::endl;
    }

    return 0;
    }

    // 输出结果
    1
    2
    3
    4

    vector 的尾插操作比较高效, 不扩容的情况下时间复杂度为 O(1).

    一旦触发扩容(size达到capacity时), 涉及到元素搬运, 时间复杂度为 O(N)

    3.2 中间插入

    使用 insert 函数进行插入. 需要配合迭代器指定插入的位置.

    #include <vector>
    #include <iostream>

    int main() {
    std::vector<int> ivec;
    ivec.push_back(1);
    ivec.push_back(2);
    ivec.push_back(3);
    ivec.push_back(4);

    // 使用 insert 在中间位置插入元素
    auto it = ivec.begin() + 2;
    ivec.insert(it, 100);

    for (int x : ivec) {
    std::cout << x << std::endl;
    }

    return 0;
    }

    // 输出结果
    1
    2
    100
    3
    4

    中间插入元素需要进行搬运, 相对比较低效, 时间复杂度 O(N)

    4. 查看/修改元素

    4.1 通过 [ ] 按下标访问

    #include <vector>
    #include <iostream>

    int main() {
    std::vector<int> ivec;
    ivec.push_back(1);
    ivec.push_back(2);
    ivec.push_back(3);
    ivec.push_back(4);

    // 通过 [ ] 来访问元素
    std::cout << ivec[0] << std::endl;
    std::cout << ivec[1] << std::endl;
    ivec[0] = 100;
    std::cout << ivec[0] << std::endl;

    std::cout << "循环访问元素: ";

    for (size_t i = 0; i < ivec.size(); ++i) {
    std::cout << ivec[i] << " ";
    }
    std::cout << std::endl;

    return 0;
    }

    // 执行结果
    1
    2
    100
    循环访问元素: 100 2 3 4
    • 下标从 0 开始
    • 如果下标越界, 会引起未定义行为.

    4.2 通过 at 方法按下标访问

    #include <vector>
    #include <iostream>

    int main() {
    std::vector<int> ivec;
    ivec.push_back(1);
    ivec.push_back(2);
    ivec.push_back(3);
    ivec.push_back(4);

    // 通过 at 来访问元素
    std::cout << ivec.at(0) << std::endl;
    std::cout << ivec.at(1) << std::endl;

    return 0;
    }

    // 执行结果
    1
    2

    如果下标越界, 会抛出异常.

    4.3 通过迭代器访问

    #include <vector>
    #include <iostream>

    int main() {
    std::vector<int> ivec;
    ivec.push_back(1);
    ivec.push_back(2);
    ivec.push_back(3);
    ivec.push_back(4);

    // 通过 迭代器 来访问元素
    std::vector<int>::iterator it = ivec.begin();
    std::cout << *it << std::endl;

    std::cout << "遍历元素: " << std::endl;
    for (auto it = ivec.begin(); it != ivec.end(); ++it) {
    std::cout << *it << std::endl;
    }

    return 0;
    }

    // 执行结果
    1
    遍历元素:
    1
    2
    3
    4

    vector 的迭代器属于随机访问迭代器, 允许进行 + - 整数操作.

    5. 查找元素

    使用 std::find 进行查找

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

    int main() {
    std::vector<int> ivec;
    ivec.push_back(1);
    ivec.push_back(2);
    ivec.push_back(3);
    ivec.push_back(4);

    // 通过 find 查找元素
    auto pos = std::find(ivec.begin(), ivec.end(), 3);
    if (pos != ivec.end()) {
    std::cout << "找到了: " << *pos << std::endl;
    } else {
    std::cout << "没有找到!" << std::endl;
    }
    return 0;
    }
    // 执行结果
    找到了: 3

    6. 删除元素

    使用 erase 方法删除元素 (需要通过迭代器指定删除位置)

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

    int main() {
    std::vector<int> ivec;
    ivec.push_back(1);
    ivec.push_back(2);
    ivec.push_back(3);
    ivec.push_back(4);

    // 通过 erase 删除元素. 需要指定位置
    auto pos = ivec.begin() + 2; // pos 指向元素 3
    ivec.erase(pos);

    for (int x : ivec) {
    std::cout << x << std::endl;
    }

    return 0;
    }

    // 执行结果
    1
    2
    4

    7. 排序

    使用 std::sort 对 vector 进行排序 (要求 vector 中的元素支持 operator< 或者可以通过 sort 的参数指定一个 std::function 对象来约定比较规则)

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

    int main() {
    std::vector<int> ivec;
    ivec.push_back(9);
    ivec.push_back(5);
    ivec.push_back(2);
    ivec.push_back(7);

    // 使用 sort 排序. 默认为升序排序
    std::cout << "升序排序: " << std::endl;
    std::sort(ivec.begin(), ivec.end());
    for (int x : ivec) {
    std::cout << x << std::endl;
    }

    // 使用 std::greater 可以修改为降序排序
    std::cout << "降序排序: " << std::endl;
    std::sort(ivec.begin(), ivec.end(), std::greater<int>());
    for (int x : ivec) {
    std::cout << x << std::endl;
    }

    return 0;
    }

    // 执行结果
    升序排序:
    2
    5
    7
    9
    降序排序:
    9
    7
    5
    2

    小结

    以上介绍了 vector 中最基础的操作. 其他更多操作, 可以参考 vector 的官方文档.

    围绕 vector 的一些面试题通常从 vector 的内存管理策略切入, 咱们后面再详细介绍.


    上一篇:记录一下下
    下一篇:没有了
    网友评论