本节我们将学习vector容器的使用和操作,让我们学习起来吧! 库函数网址查询:https://legacy.cplusplus.com/reference/vector/vector/?kw=vector
C++ 标准库中的 std::vector
是一个动态数组容器,能够存储并管理元素的集合。它提供了动态调整大小的能力,并且在底层维护一个连续的存储区域,使得元素可以通过索引进行快速访问。
std::vector
是一个类模板,它的定义如下:
模板参数
T
:向量中存储的元素的类型。Allocator
:用于分配内存的分配器类型,默认是 std::allocator<T>
。就像数组一样,向量对其元素使用连续的存储位置,这意味着也可以使用指向其元素的常规指针上的偏移量来访问其元素,并且与数组中的元素一样高效。但与数组不同的是,它们的大小可以动态变化,它们的存储由容器自动处理。
在内部,向量使用动态分配的数组来存储其元素。当插入新元素时,可能需要重新分配此数组才能增大大小,这意味着分配一个新数组并将所有元素移动到该数组。就处理时间而言,这是一项相对昂贵的任务,因此,每次将元素添加到容器时,向量都不会重新分配。
相反,矢量容器可能会分配一些额外的存储来适应可能的增长,因此容器的实际容量可能大于包含其元素(即其大小)严格需要的存储。库可以实施不同的增长策略,以平衡内存使用和重新分配之间的平衡,但无论如何,重新分配应该只在大小的对数增长间隔下发生,以便在向量末尾插入单个元素时可以提供摊销的恒定时间复杂度(参见push_back)。
因此,与数组相比,向量消耗更多的内存,以换取以有效的方式管理存储和动态增长的能力。
与其他动态序列容器(deques
、lists
和 forward_lists
)相比,向量非常有效地访问其元素(就像数组一样),并且相对有效地从其末端添加或删除元素。对于涉及在末尾以外的位置插入或删除元素的操作,它们的性能比其他操作差,并且迭代器和引用的一致性低于列表和forward_lists
。
成员类型 | 定义 |
value_type | 第一个模板参数 |
allocator_type | 第二个模板参数 (Alloc) |
size_type | 一个无符号的整数类型,可以表示 difference_type 的任何非负值 |
std::vector
的四种不同构造函数分别是:
这个构造函数创建一个空的 std::vector
,allocator_type
是用来分配内存的分配器类型,默认使用 std::allocator<T>
,构造函数是 explicit
的,这意味着它不能进行隐式转换或复制初始化。
示例:
这个构造函数创建一个包含 n
个 val
值的 std::vector
, size_type
是一个无符号整数类型,通常是 std::size_t
, value_type
是存储在 std::vector
中的元素的类型, allocator_type
是分配器类型,默认值为 std::allocator<T>
。
示例:
这个构造函数使用范围 [first, last)
中的元素创建 std::vector
,InputIterator
是输入迭代器类型,可以是指向数组的指针、其他容器的迭代器等。
示例:
这个构造函数使用另一个 std::vector
x
的内容创建一个新的 std::vector
,它会复制 x
中所有的元素,并且新创建的 std::vector
会有与 x
相同的大小和容量。
示例:
综合测试代码:
迭代器基本使用方法大致相同,这里讲解基础的两个使用:
begin
函数:
作用: 返回指向容器开头的迭代器。
非 const 版本:
iterator
,这是一个指向容器第一个元素的迭代器。const 版本:
const_iterator
,这是一个指向容器第一个元素的常量迭代器。end
函数:
作用: 返回指向容器末尾的迭代器。
非 const 版本:
iterator
,这是一个指向容器末尾(即最后一个元素的下一个位置)的迭代器。const 版本:
const_iterator
,这是一个指向容器末尾的常量迭代器。例子:
函数定义:
示例
输出:
函数定义:
探索capaccity()
的扩容机制
vs:运行结果:vs下使用的STL基本是按照1.5倍方式扩容
g++运行结果:linux下使用的STL基本是按照2倍方式扩容
如果已经确定vector
中要存储元素大概个数,可以提前将空间设置足够 就可以避免边插入边扩容导致效率低下的问题了
小结:
capacity
的代码在vs
和g++
下分别运行会发现,vs
下capacity
是按1.5倍增长的,g++是按2倍增长的。这个问题经常会考察,不要固化的认为,vector增容都是2倍,具体增长多少是根据具体的需求定义的。vs是PJ版本STL,g++是SGI版本STL。
resize
成员函数用于调整向量的大小。根据新大小,可以增加或减少向量中的元素。如果新大小大于当前大小,新的元素将被添加到向量的末尾。如果新大小小于当前大小,向量将被截断。
std::vector::reserve
是一个成员函数,用于请求将向量的容量增加到至少指定的大小。这与 resize
不同,reserve
只改变容量(即预分配的存储空间),而不改变实际存储的元素数量。通过预先分配足够的存储空间,可以避免频繁的重新分配,从而提高性能,特别是在知道将要存储的大量元素时。
函数定义:
如果 new_cap
大于当前容量,向量的容量将增加到至少 new_cap
。如果 new_cap
小于或等于当前容量,则容量保持不变。
使用示例:
输出:
使用注意事项:
reserve
可以提高性能,避免在添加大量元素时频繁重新分配内存。reserve
,向量在需要更多容量时通常会自动增长,大多数实现使用倍增策略(即每次需要更多空间时,容量翻倍)。
reserve
只负责开辟空间,如果确定知道需要用多少空间,reserve可以缓解vector增容的代价缺陷问题。resize
在开空间的同时还会进行初始化,影响size
注意std::find
是 C++ 标准库中 <algorithm>
头文件中的一个函数模板,而不是vector
的find
,vector
中没有find
,用于在给定范围内查找指定的值。
函数原型如下:
返回一个迭代器,指向范围内第一个等于 val
的元素。如果在给定范围内没有找到该值,则返回 last
迭代器。
示例:
输出:
std::find
函数的时间复杂度为 O(n),其中 n 是给定范围的大小。它会顺序遍历整个范围,直到找到目标元素或者到达范围末尾。因此,它适用于小型数据集,但对于大型数据集可能性能较差。在这种情况下,可以考虑使用更高效的算法,如 std::binary_search
或者基于哈希表的查找。
std::vector::insert
是 C++ 标准库中 <vector>
头文件中的一个成员函数,用于在给定位置插入元素。
它有三种重载形式:
单元素插入:
该形式在迭代器 position
指向的位置插入一个值为 val
的元素,并返回指向新插入元素的迭代器。
区间插入:
该形式在迭代器 position
指向的位置插入 n
个值为 val
的元素。
范围插入:
该形式在迭代器 position
指向的位置插入 [first, last)
范围内的元素。
需要注意的是,在调用
insert
函数时,如果vector
的大小需要扩张以容纳新的元素,则会自动分配新的内存空间。这可能会导致迭代器、指针和引用失效,因此在使用这些元素时需要格外小心。(这里我们在学习vector的模拟实现中可以看出)
下面是一个示例:
输出:
std::vector::erase
是 C++ 标准库中 <vector>
头文件中的一个成员函数,用于删除 vector
中的元素。它有两种重载形式:
单个元素删除:
该形式删除迭代器 position
指向的元素,并返回指向被删除元素之后的下一个元素的迭代器。
范围删除:
该形式删除 [first, last)
范围内的所有元素,并返回指向被删除元素之后的下一个元素的迭代器。
需要注意的是,在调用
erase
函数时,如果vector
的大小需要收缩以适应被删除的元素,则会自动缩小内存空间。这可能会导致迭代器、指针和引用失效,因此在使用这些元素时需要格外小心(这就是她为什么要有返回值,返回值是iterator)。
下面是一个示例:
输出: