C++ Vector的使用(上)

发布于:2025-07-02 ⋅ 阅读:(16) ⋅ 点赞:(0)

注:这里以C++ 11版本为基础,简单介绍vector的特性和常见使用。

目录

vector简介

vector特性

vector的定义

vector对象的构造和初始化

1.构造一个空的vector

2.构造一个容量大小为n的vector

3.构造一个vector,初始值为指定的数据片段

4.拷贝构造一个vector对象

5.移动构造一个vector对象

6.直接使用列表初始化&构造vector对象

vector中元素的遍历

通过下标遍历vector中的元素

通过迭代器遍历vector中的元素

使用标准算法for_each遍历vector中的元素

使用结构化绑定遍历vector中的元素

总结

vector中查找某个元素(精确查找/模糊查找)

基于范围的for循环方式查找某个元素是否存在

通过库函数检查某个元素是否存在

通过迭代器find方法检查某个元素是否存在(性能比较好)

查找满足条件的元素


vector简介

vector是C++ STL中顺序容器中的变长数组,容器的存储空间是自动管理的,按需扩张和收缩。

像array一样,vector使用连续的存储空间来存储其元素,这就意味着可以像array那样使用指向其元素的常规指针的偏移量来访问它的元素。不同于array,vector的大小可以动态调整,容器会自动处理它的存储。

在内部,vector使用一个动态分配的数组存储它的元素。当新的元素插入时,可能需要重新分配以满足空间大小动态增长的需求, 这意味着分配新的数组并将所有元素移到新数组。就处理时间而言,这是一个相对昂贵的任务,因此vector并不会在每次向容器中添加元素时重新分配。

vector容器可能会分配一些额外的存储空间,以适应可能的增长,因此容器的实际容量(capacity)可能大于严格容纳其元素所需的存储容量(例如,vector‘s size)。库可以实现不同的增长策略,以平衡内存使用的增长和重新分配。但是不管怎样,重新分配应该只能发生在对数增长的大小间隔内,以使在vector末尾插入单个元素时可以提供均摊为常数的时间复杂度(见push_back函数)。

因此,与array相比,vector消耗更多的空间以换取有效的管理存储和动态增长的能力。

与其他动态顺序容器(deque, list  and forward_list)相比,vector可以高效的访问它的元素(就像array那样),相对高效的在其末端添加或删除元素。对于在非末尾插入或删除的操作,它的表现会比其他顺序容器差,并且迭代器和引用一致性不如list和forward_list。

vector特性

特性主要是三点:

  • 顺序性

顺序容器中的元素严格按照线性顺序排列。单个元素通过它们在这个序列中的位置来访问。

  • 动态排列

允许直接访问序列中的任何元素,甚至通过指针计算,并在序列末尾提供相对快速的添加/删除元素。

  • 感知内存分配器

容器使用分配器对象动态处理其存储需求。

vector的定义

头文件 :<vector>

template <class T, class Allocator = std::allocator<T>> class vector;
namespace pmr {
    template <class T>
    using vector = std::vector<T, std::pmr::polymorphic_allocator<T>>;
}

vector对象的构造和初始化

构造一个vector并根据需要进行初始化有以下6种方式:

  • empty container constructor (default constructor)
  • fill constructor
  • range constructor
  • copy constructor (and copying with allocator)
  • move constructor (and moving with allocator)
  • initializer list constructor

1.构造一个空的vector

构造函数定义:

explicit vector(const allocator_type& alloc = allocator_type());

例子: 

vector<int> vec1;     //构造一个元素类型为T的空vector, 其size是0, capacity也是0。

2.构造一个容量大小为n的vector

构造函数定义:

explict vector(size_type n);
explict vector(size_type n, const value_type& val,
    const allocator_type& alloc = alloctor_type());

例子:

vector<int> vec2(3);    //构造一个元素类型为T的空vector, 其size是3, capacity也是3,
                        //元素初始值即默认值0.
vector<int> vec3(3, 2); //构造一个元素类型为T的空vector,其size是3,capacity也是3,
                        //元素初始值是2.

3.构造一个vector,初始值为指定的数据片段

构造函数定义:

template <class InputIterator> vector(InputIterator first, InputIterator last,
    const allocator_type& alloc = allocator_type());

例子:

int arr1[] = {1, 2, 3, 4};
vector<int> vec4(arr1, arr1 + sizeof(arr1) / sizeof(arr1[0]));
                                                 //构造一个元素类型为int的vector,
                                                 //并用片段arr1数据片段初始化

array<int, 3> arr2 = {3, 4, 5};             //创建一个int类型数组,长度未3,元素初始值:3,4,5
vector<int> vec4(arr2.begin(), arr2.end()); //构造一个元素类型为int的vector,
                                            //并用arr2 input iterator数据片段初始化

4.拷贝构造一个vector对象

构造函数定义:

vector(const vector& x);
vector(const vector& x, const allocator_type& alloc);

例子:

vector<int> vec5(vec4);  //通过拷贝vector vec4对象,构造一个元素类型为int的vector vec5
vector<int> vec5 = vec4;
vector<int> vec5 = {1, 2, 3};  //拷贝列表初始化&构造一个元素类型为int的vector对象vec5

5.移动构造一个vector对象

构造函数定义:

vector(vector&& x);
vector(vector&& x, const allocator_type& alloc);

例子:

vector<int> vec6(std::move(vec5));  //移动资源,vec5变为空
vector<int> vec6 = std::move(vec5); 

6.直接使用列表初始化&构造vector对象

构造函数定义:

vector(initialized_list<valut_type> il,
        const allocator_type& alloc = allocator_type());

例子:

vector<int> vec7{1 , 2, 3}; //直接列表初始化&构建一个元素类型为int的vector对象vec7

vector中元素的遍历

遍历一个vector容器中的元素有两种方法:

  • 根据元素存储的连续性,通过偏移或者下标遍历。
  • 使用迭代器遍历。
  • 使用标准算法遍历。
  • 使用结构化绑定(针对pair/tuple)遍历。 (C++ 17)

通过下标遍历vector中的元素

#include <iostream>
#include <vector>

using namespace std;

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

    printf("第一种遍历方式:通过下标访问\n");
    for (int i = 0; i < vec.size(); i++) {
        printf("%d\t", vec[i]);
    }
    printf("\n");

    return 0;
}

通过迭代器遍历vector中的元素

#include <iostream>
#include <vector>

using namespace std;

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

    printf("第二种遍历方式:迭代器访问\n");
    for (vector<int>::iterator iter = vec.begin();
        iter != vec.end(); iter++) {
        printf("%d\t", *iter);
    }
    printf("\n");

    printf("第三种遍历方式: C++ 11 auto关键字简化迭代器类型\n");
    for (auto iter = vec.begin(); iter != vec.end(); iter++) {
        printf("%d\t", *iter);
    }
    printf("\n");

    printf("第四种遍历方式: 基于范围的for循环\n");
    for (auto& iter : vec) {
        printf("%d\t", iter);
    }
    printf("\n");
    
    printf("第四种遍历方式:带索引的,基于范围的for循环(C++ 20)\n");
    for (size_t i = 0; const auto& iter : vec) {
        printf("[%d] %d\t", i++, iter);
    }
    printf("\n");

    return 0;
}

使用标准算法for_each遍历vector中的元素

#include <iostream>
#include <vector>

using namespace std;

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

    std::for_each(vec.begin(), vec.end(), [](int n) {
        printf("%d\t", n);
    });
    printf("\n");

    return 0;
}

使用结构化绑定遍历vector中的元素

这种方式对元素类型是复合的情况比较方便的一种遍历方法, 例子如下:

#include <iostream>
#include <vector>
#include <utility>  //定义pair

using namespace std;

int main()
{
    std::vector<std::pair<int, std::string>> pairs = {
        {1, "one"}, {2, "two"}, {3, "three"}
    };

    for (const auto& [num, name] : pairs) {
        printf("%d-%s\t", num, name.c_str());
    }
    printf("\n");

    return 0;
}

总结

遍历方法 优点 缺点 适用场景
下标遍历 直观,支持随机访问 需要手动管理索引 需要索引操作的场景
迭代器遍历 通用(适用于所有容器) 语法较冗长 泛型编程,算法实现
基于范围的for循环 简介安全(C++11+ 推荐) 无法直接获取索引(C++20前) 大多数遍历场景
标准算法 函数式风格,可组合操作 学习曲线较陡峭 数据转换/聚合操作
结构化绑定 结构复杂元素方便 仅适用于结构化类型 pair/tuple/struct元素
指针遍历 与C兼容 不安全,易出错 特殊兼容场景 (不推荐)

vector中查找某个元素(精确查找/模糊查找)

检查vector中是不是包含某个元素主要有三种方法:

  • 基于范围的for循环,遍历元素并进行比较
  • 使用库函数检查是不是存在
    • std::find()      某个元素是否存在,最常用
    • std::count()   某元素出现的次数
    • std::any_of() 带条件检查的,需要C++11起
    • std::binary_search()  仅适用于已经排序的vector
  • 通过迭代器的find方法

检查vector中是不是包含满足某个条件的方法:

  • find_if() 返回序列中第一个满足条件的元素的迭代器。
  • any_of()  如果任何元素满足条件返回true,否则返回false。
  • none_of() 如果给定的条件在范围内所有元素都返回false,则返回true; 否则返回false。

基于范围的for循环方式查找某个元素是否存在

#include <iostream>
#include <vector>

int main()
{
    std::vector<std::string> names = {"Alice", "Bob", "Charlie"};
    std::string target = "Bob";
    bool found = false;

    for (const auto& name : names) {
        if (name == target) {
            found = true;
            break;
        }
    }

    printf("Found : %s", found == true ? "true" : "false");
    return 0;
}

通过库函数检查某个元素是否存在

#include <iostream>
#include <vector>
#include <altorithm>

int main()
{
    std::vector<int> vec = {10, 20, 30, 40, 50};
    int target = 30;     //要检查的元素
    bool found = false;  //是否存在

    printf("方法1:查找某个元素是否存在\n");
    size_t index = -1;      //索引
    auto it = std::find(vec.begin(), vec.end(), target);
    if (it != vec.end()) {
        found = true;
        index = std::distance(vec.begin(), it);  //获取这个元素在vec中的索引位置
    }
    printf("Found : %s  index: %u\n", found == true ? "true" : "false", index);

    printf("方法2:统计某个元素出现的次数\n");
    size_t count = 0;
    count = std::count(vec.begin(), vec.end(), target);
    if (count > 0) {
        found = true;
    }
    printf("Found : %s count : %u\n", found == true ? "true" : "false", count);

    printf("方法3:带条件检查的遍历\n");
    found = std::any_of(vec.begin(), vec.end(), [target](int value) {
        return value == target;
    });
    printf("Found : %s\n", found == true ? "true" : "false");

    printf("方法3:二分查找\n");
    found = std::binary_search(vec.begin(), vec.end(), target);  //存在的时候不返回位置
    auto lb = std::lower_bound(vec.begin(), vec.end(), target);  //存在的时候能返回位置
    if (lb != vec.end() && *lb == target) {
        index = lb - vec.begin();
    }
    printf("Found : %s index : %d\n", found == true ? "true" : "false", index);

    return 0;
}

通过迭代器find方法检查某个元素是否存在(性能比较好)

#include <iostream>
#include <vector>
#include <unordered_set>

int main()
{
    std::vector<int> vec = {10, 20, 30, 40, 50};
    int target = 30;     //要检查的元素
    bool found = false;  //是否存在

    std::unordered_set<int> set(vec.begin(), vec.end());
    if (set.find(value) != set.end()) {
        found = true;
    }
    printf("Found : %s\n", found == true ? "true" : "false");

    return 0;
}

查找满足条件的元素

#include <iostream>
#include <vector>
#include <altorithm>

int main()
{
    std::vector<int> vec = {10, 20, 30, 40, 50};
    int target = 30;     //要检查的元素
    bool found = false;  //是否存在

    found = std::find_if(vec.begin(), vec.end(), [](int x) {
        return x > 25;
    });
    printf("Found : %s\n", found == true ? "true" : "false");


    found = false;
    found = std::any_of(vec.begin(), vec.end(), [](int v) {
        if (v % 5 == 0)
            return true;
        else
            return false;
    });
    printf("Found : %s\n", found == true ? "true" : "false");

    return 0;
}

网站公告

今日签到

点亮在社区的每一天
去签到