c++ | vector
前言
本篇博客讲解c++STL中的vector
💓 个人主页:普通young man-CSDN博客
⏩ 文章专栏:C++_普通young man的博客-CSDN博客
⏩ 本人giee: 普通小青年 (pu-tong-young-man) - Gitee.com
若有问题 评论区见📝
🎉欢迎大家点赞👍收藏⭐文章
目录
vector的介绍
vector的使用
构造函数
赋值operator
迭代器
容量
创建二维数组
1. 创建一维向量 v:
2. 创建二维向量 vv:
3. 修改元素:
4. 遍历二维向量:
vector实现
命名空间定义
类模板定义
公共类型定义
构造函数
析构函数
成员函数
测试函数
这篇博客我讲的不会很多,因为他和前面的string非常的像,并且更加简洁,还是一样我们根据文章来讲解,然后给一些特殊情况,然后再简单的实现一下vector.
vector的介绍
vector - C++ Reference (cplusplus.com)https://legacy.cplusplus.com/reference/vector/vector/?kw=vector这个是一个c++的文档,可以根据这里面的介绍来合理的运用接口
vector的使用
构造函数
我写一下这些构造,我相信大家其实也可以看懂
#include <iostream>
#include <vector>void test1() {// 构造一个包含10个元素的向量,所有元素初始化为0。std::vector<int> v(10, 0);// 复制构造 - 创建一个新的向量,包含与 'v' 相同的元素。std::vector<int> v1(v);// 迭代器构造 - 从 'v1' 的后五个元素创建一个新的向量。std::vector<int> v2(v1.begin() + 5, v1.end());// 初始化一个数组,并从其内容构建一个向量。int arr[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 0};std::vector<int> v3(arr, arr + sizeof(arr) / sizeof(arr[0]));// 遍历 'v3' 并打印其元素。for (int ch : v3) {std::cout << ch << " ";}std::cout << std::endl; // 打印换行符。
}// 示例用法:
int main() {test1();return 0;
}
- 初始化:创建了一个名为
v
的std::vector<int>
,其中包含10个元素,每个元素都初始化为0。- 复制构造:通过复制
v
的内容创建了一个新的向量v1
。- 子范围构造:使用
v1
的最后五个元素创建了一个新的向量v2
。- 数组到向量:声明并初始化了一个整数数组
arr
,然后从该数组的元素构建了一个向量v3
。- 迭代和打印:使用范围for循环遍历
v3
中的元素,并将它们打印到控制台。
赋值operator
#include <iostream>
#include <vector>void test2() {// 创建两个向量,v1 和 v2,分别包含5个元素,初始化为1和2。std::vector<int> v1(5, 1);std::vector<int> v2(5, 2);// 将 v2 的内容赋给 v1。v1 = v2;// 打印 v1 的内容。std::cout << "v1: ";for (auto ch : v1) {std::cout << ch << " ";}std::cout << std::endl;// 再次将 v2 的内容赋给 v1(实际上这里没有改变 v1 的内容)。v1 = v2;// 打印 v2 的内容。std::cout << "v2: ";for (auto ch : v2) {std::cout << ch << " ";}std::cout << std::endl;
}// 示例用法:
int main() {test2();return 0;
}
初始化向量:创建了两个
std::vector<int>
,v1
和v2
,分别包含了5个元素,其中v1
的所有元素被初始化为1,而v2
的所有元素被初始化为2。赋值操作:使用赋值操作符 (
=
) 将v2
的内容赋给v1
,这意味着v1
现在也包含了5个元素,每个元素的值都是2。打印内容:使用范围for循环遍历
v1
并打印其内容。因为v1
已经被赋值为v2
的内容,所以输出将会是5个数字2。再次赋值操作:再次将
v2
的内容赋给v1
,这实际上没有改变v1
的内容,因为它已经与v2
的内容相同了。打印第二个向量的内容:使用范围for循环遍历
v2
并打印其内容。输出也将是5个数字2。结束程序:函数
main
返回0,表示程序正常结束。
迭代器
#include <iostream>
#include <vector>void test3() {// 初始化数组:定义了一个整数数组 arr,并初始化了10个元素。int arr[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 0};// 构造向量:使用数组的内容创建了一个常量 std::vector<int>,命名为 v。const std::vector<int> v(arr, arr + sizeof(arr) / sizeof(arr[0]));// 使用迭代器遍历向量:// 定义了一个 std::vector<int>::const_iterator 类型的迭代器 it,并将其初始化为指向向量的第一个元素。// 使用 while 循环遍历整个向量,每次迭代输出当前迭代器所指的元素,并递增迭代器。// 输出完所有元素后,换行。for (std::vector<int>::const_iterator it = v.begin(); it != v.end(); ++it) {std::cout << *it << " ";}std::cout << std::endl;// 使用范围for循环遍历向量:// 使用范围for循环遍历向量 v,并输出每个元素。for (auto ch : v) {std::cout << ch << " ";}std::cout << std::endl;// 使用反向迭代器遍历向量:// 定义了一个 std::vector<int>::const_reverse_iterator 类型的反向迭代器 it,并将其初始化为指向向量的最后一个元素。// 使用 while 循环遍历整个向量,每次迭代输出当前反向迭代器所指的元素,并递增反向迭代器。// 输出完所有元素后,换行。for (std::vector<int>::const_reverse_iterator it = v.rbegin(); it != v.rend(); ++it) {std::cout << *it << " ";}std::cout << std::endl;// 使用引用范围for循环遍历向量:// 使用范围for循环遍历向量 v,并输出每个元素的引用。虽然这里没有修改元素的值,但是这种方式可以用来修改向量中的元素。for (auto &ch : v) {std::cout << ch << " ";}std::cout << std::endl;
}// 示例用法:
int main() {test3();return 0;
}
初始化数组:
- 定义了一个整数数组
arr
,并初始化了10个元素。构造向量:
- 使用数组的内容创建了一个常量
std::vector<int>
,命名为v
。使用迭代器遍历向量:
- 定义了一个
std::vector<int>::const_iterator
类型的迭代器it
,并将其初始化为指向向量的第一个元素。- 使用
while
循环遍历整个向量,每次迭代输出当前迭代器所指的元素,并递增迭代器。- 输出完所有元素后,换行。
使用范围for循环遍历向量:
- 使用范围for循环遍历向量
v
,并输出每个元素。使用反向迭代器遍历向量:
- 定义了一个
std::vector<int>::const_reverse_iterator
类型的反向迭代器it
,并将其初始化为指向向量的最后一个元素。- 使用
while
循环遍历整个向量,每次迭代输出当前反向迭代器所指的元素,并递增反向迭代器。- 输出完所有元素后,换行。
使用引用范围for循环遍历向量:
- 使用范围for循环遍历向量
v
,并输出每个元素的引用。虽然这里没有修改元素的值,但是这种方式可以用来修改向量中的元素。
vector 迭代器失效问题。(重点) 迭代器的主要作用就是让算法能够不用关心底层数据结构,其底层实际就是一个指针,或者是对 指针进行了封装,比如:vector的迭代器就是原生态指针T* 。因此迭代器失效,实际就是迭代器 底层对应指针所指向的空间被销毁了,而使用一块已经被释放的空间,造成的后果是程序崩溃(即 如果继续使用已经失效的迭代器,程序可能会崩溃)。
这里我举几个例子
#include <iostream>
using namespace std;
#include <vector>
int main()
{vector<int> v{1,2,3,4,5,6};auto it = v.begin();// 将有效元素个数增加到100个,多出的位置使用8填充,操作期间底层会扩容// v.resize(100, 8);// reserve的作用就是改变扩容大小但不改变有效元素个数,操作期间可能会引起底层容
量改变// v.reserve(100);// 插入元素期间,可能会引起扩容,而导致原空间被释放// v.insert(v.begin(), 0);// v.push_back(8);// 给vector重新赋值,可能会引起底层容量改变v.assign(100, 8);/*出错原因:以上操作,都有可能会导致vector扩容,也就是说vector底层原理旧空间被释
放掉,而在打印时,it还使用的是释放之间的旧空间,在对it迭代器操作时,实际操作的是一块
已经被释放的空间,而引起代码运行时崩溃。解决方式:在以上操作完成之后,如果想要继续通过迭代器操作vector中的元素,只需给
it重新赋值即可。*/while(it != v.end()){cout<< *it << " " ;++it;}cout<<endl;return 0;
}
选择了
v.assign(100, 8);
这一行来进行操作。这行代码将v
的内容替换为100个值为8的元素。由于v
的大小从6个元素增加到了100个元素,这很可能导致std::vector
需要重新分配内存以容纳更多的元素。在重新分配过程中,原有的内存会被释放,并且std::vector
会在新的内存位置上构造新元素。这意味着之前的迭代器it
指向的地址不再有效。
#include <iostream>e
/*rase删除pos位置元素后,pos位置之后的元素会往前搬移,没有导致底层空间的改变,理
论上讲迭代器不应该会失效,但是:如果pos刚好是最后一个元素,删完之后pos刚好是end
的位置,而end位置是没有元素的,那么pos就失效了。因此删除vector中任意位置上元素
时,vs就认为该位置迭代器失效了。
以下代码的功能是删除vector中所有的偶数,请问那个代码是正确的,为什么?*/
using namespace std;
#include <vector>
int main()
{int a[] = { 1, 2, 3, 4 };vector<int> v(a, a + sizeof(a) / sizeof(int));// 使用find查找3所在位置的iteratorvector<int>::iterator pos = find(v.begin(), v.end(), 3);// 删除pos位置的数据,导致pos迭代器失效。v.erase(pos);cout << *pos << endl; // 此处会导致非法访问return 0;
}
v.erase(pos);
删除了pos
所指向的元素。按照题目描述,这段代码的目标是删除所有偶数,但这里只删除了一个元素(即值为3的元素),这与题目要求不符。在删除一个元素后,
pos
迭代器确实可能失效。虽然erase
操作不会导致底层内存重新分配,但如果删除的是pos
指向的元素,那么pos
将不再指向任何有效元素。特别是,如果pos
原本指向的是最后一个元素,那么删除后它将指向v.end()
,这是无效的。删除元素后尝试访问
pos
所指向的元素会导致未定义行为,因为pos
已经失效。
还有和这个删除是一样的就是头插入,这个也会出现迭代器失效,因为pos位置没有进行映射改变
容量
#include <iostream>
#include <vector>void test4() {// 初始化一个整数数组。int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 0};// 使用数组的内容构造一个 std::vector<int>,命名为 v。std::vector<int> v(arr, arr + sizeof(arr) / sizeof(arr[0]));// 输出向量的信息。std::cout << "大小 -> " << v.size() << std::endl;std::cout << "容量 -> " << v.capacity() << std::endl;// 调整向量的大小,并填充额外的元素。v.resize(12, 1);for (auto& ch : v) {std::cout << ch << " ";}std::cout << std::endl;// 再次调整向量的大小,并填充额外的元素。v.resize(5, 2);for (auto& ch : v) {std::cout << ch << " ";}// 创建一个向量,并移除其中的偶数元素。std::vector<int> v1{1, 2, 3, 4, 5, 6};auto it = v1.begin();while (it != v1.end()) {if (*it % 2 == 0) {it = v1.erase(it); // 注意:erase 返回指向下一个元素的新迭代器。} else {++it;}}for (auto e : v1) {std::cout << e << " ";}std::cout << std::endl;
}// 示例用法:
int main() {test4();return 0;
}
下面是代码中使用的
std::vector
接口的详细解释:
构造函数:
1std::vector<int> v(arr, arr + sizeof(arr) / sizeof(arr[0]));
- 这里使用了
std::vector
的构造函数,该构造函数接受两个迭代器参数,用于指定数组的开始和结束位置。arr
是数组的起始地址,arr + sizeof(arr) / sizeof(arr[0])
是数组的结束地址。输出向量信息:
1std::cout << "大小 -> " << v.size() << std::endl; 2std::cout << "容量 -> " << v.capacity() << std::endl;
size()
函数返回向量中元素的数量。capacity()
函数返回向量当前分配的存储空间,它可以大于向量的实际大小。调整向量大小:
1v.resize(12, 1);
resize(n, val)
函数用于调整向量的大小。如果新大小大于当前大小,则在向量末尾添加val
值填充的新元素;如果新大小小于当前大小,则截断向量。遍历向量:
1for (auto& ch : v) { 2 std::cout << ch << " "; 3}
- 使用范围for循环遍历向量
v
,并输出每个元素。移除向量中的偶数元素:
1auto it = v1.begin(); 2while (it != v1.end()) { 3 if (*it % 2 == 0) { 4 it = v1.erase(it); // 注意:erase 返回指向下一个元素的新迭代器。 5 } else { 6 ++it; 7 } 8}
- 使用迭代器
it
遍历向量v1
。- 当遇到偶数元素时,使用
erase(it)
函数删除该元素,并将迭代器更新为指向下一个元素的新迭代器。- 如果元素不是偶数,则递增迭代器。
总结来说,这段代码展示了如何使用
std::vector
的构造函数、size()
、capacity()
、resize()
函数,以及如何遍历和修改向量中的元素。特别是,在删除向量中的元素时,需要注意erase()
函数返回的是指向下一个元素的新迭代器,以避免潜在的迭代器失效问题。
创建二维数组
void test5(){vector<int> v(5,0); vector<vector<int>>vv(5,v);vv[0][1] = 5;//operator[]返回//第一个[],访问的是外层的vector -- 也就是行//第二个[],访问的是里层的vector -- 也就是列//遍历二维数组for (size_t i = 0; i < vv.size(); i++){for (size_t j = 0; j < v.size();j++) {cout << vv[i][j] << " ";}cout << endl;}
}
1. 创建一维向量
v
:
vector<int> v(5,0);
创建了一个包含5个整数0的一维向量v
。这里的构造函数vector(size_t n, const T val = T())
被调用,其中n
是5,val
是0。2. 创建二维向量
vv
:
vector<vector<int>> vv(5, v);
创建了一个包含5个一维向量v
的二维向量vv
。这里也是使用了构造函数vector(size_t n, const T val = T())
,其中n
是5,val
是之前创建的一维向量v
。3. 修改元素:
vv[0][1] = 5;
这行代码修改了二维向量vv
中第一行(索引0)第二列(索引1)的元素值为5。4. 遍历二维向量:
for (size_t i = 0; i < vv.size(); i++)
:外层循环用于遍历二维向量vv
的每一行。for (size_t j = 0; j < v.size(); j++)
:内层循环用于遍历每一行中的每一个元素。cout << vv[i][j] << " ";
:输出当前元素的值,并用空格分隔。cout << endl;
:每行输出完毕后换行。
vector实现
这个实现我只会实现个别的接口
#pragma once
#include <iostream>
#include <vector>
#include <cassert>
using namespace std;namespace yang {// 定义类模板template <class T>class vector {public:typedef T* iterator; // 非常量迭代器类型定义typedef const T* const_iterator; // 常量迭代器类型定义// 默认构造函数vector() = default;// 拷贝构造函数vector(const vector<T>& v) {// 分配与原向量相同大小的空间reserve(v.size());for (const auto& it : v) {pushback(it); // 将原向量的每个元素复制到新向量}}// 迭代器范围构造函数template <class inputiterator>vector(inputiterator fast, inputiterator last) {while (fast != last) {pushback(*fast); // 将迭代器范围内的元素添加到向量中++fast;}}// 构造函数,创建指定大小的向量,并用给定值初始化vector(size_t n, const T val = T()) {reserve(n); // 分配足够大的空间for (int i = 0; i < n; i++) {pushback(val); // 添加初始化值}}// 构造函数,创建指定大小的向量,并用给定值初始化// 注意:使用 int 参数可能会导致溢出问题vector(int n, const T val = T()) {reserve(n); // 分配足够大的空间for (int i = 0; i < n; i++) {pushback(val); // 添加初始化值}}// 析构函数~vector() {delete[] _start; // 释放分配的内存_start = _finish = _end_of_storage = nullptr; // 清理指针}// 获取向量中的元素数量size_t size() const {return _finish - _start;}// 获取向量的容量size_t capacity() const {return _end_of_storage - _start;}// 判断向量是否为空bool empty() {return _finish == _start;}// 清空向量内容void clear() {_finish = _start;}// 返回向量开始迭代器iterator begin() {return _start;}// 返回向量开始的常量迭代器const_iterator begin() const {return _start;}// 返回向量结束迭代器iterator end() {return _finish;}// 返回向量结束的常量迭代器const_iterator end() const {return _finish;}// 扩容函数void reserve(size_t n) {if (n > capacity()) {// 记录原来的元素数量size_t old_size = size();// 分配新的内存空间T* tmp = new T[n];//memcpy(tmp, _start, sizeof(T) * size()); // 旧版代码使用memcpyfor (int i = 0; i < old_size; i++) {tmp[i] = _start[i]; // 复制原有元素}// 销毁旧内存delete[] _start;// 更新指针_start = tmp;_finish = tmp + old_size;_end_of_storage = tmp + n;}}// 调整向量大小void resize(size_t n, T val = T()) {if (n < size()) {_finish = _start + n; // 缩小向量} else {reserve(n); // 扩容while (_finish < _start + n) {*_finish = val; // 填充新元素++_finish;}}}// 在向量末尾添加元素void pushback(const T& val) {if (_finish == _end_of_storage) {reserve(capacity() == 0 ? 4 : capacity() * 2); // 如果空间不足则扩容}*_finish = val; // 添加新元素++_finish;}// 移除向量末尾的元素void popback() {assert(!empty()); // 断言向量非空--_finish; // 向量末尾减一}// 交换两个向量的内容void swap(vector<T>& v) {std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_end_of_storage, v._end_of_storage);}// 赋值运算符重载vector<T>& operator=(vector<T> v) {swap(v); // 使用swap函数完成赋值return *this;}// 下标访问T& operator[](size_t i) {assert(i < size()); // 断言索引在范围内return _start[i]; // 返回元素的引用}// 常量下标访问const T& operator[](size_t i) const {assert(i < size()); // 断言索引在范围内return _start[i];}// 在指定位置插入元素iterator insert(iterator pos, const T& val) {assert(pos >= _start && pos < _finish); // 断言位置合法if (_finish == _end_of_storage) {// 存储pos到_start的位置(如果扩容,地址会改变)size_t len = pos - _start;// 扩容reserve(capacity() == 0 ? 4 : capacity() * 2);// 更新位置(映射)pos = _start + len;}// 向右移动元素以留出空间iterator end = _finish - 1;while (end >= pos) {*(end + 1) = *end;--end;}*pos = val; // 插入新元素++_finish; // 更新结束指针// 返回新元素的位置(注意返回pos+1是为了不影响实参)return pos + 1;}// 删除指定位置的元素iterator erase(iterator pos) {assert(pos >= _start && pos < _finish); // 断言位置合法// 移动后面的元素向前覆盖被删除的元素iterator it = pos + 1;while (it != _finish) {*(it - 1) = *it;++it;}--_finish; // 更新结束指针return pos; // 返回删除位置}private:iterator _start = nullptr; // 开始迭代器iterator _finish = nullptr; // 结束迭代器iterator _end_of_storage = nullptr; // 存储区结束迭代器};//-- 测试函数 --void test1() {vector<int> v;v.reserve(5); // 预留5个元素的空间v.pushback(1);v.pushback(2);v.pushback(3);v.pushback(4);v.pushback(5);v.pushback(1);v.pushback(2);v.pushback(3);v.pushback(4);v.pushback(5);cout << v.size() << endl; // 输出向量的大小cout << v.capacity() << endl; // 输出向量的容量auto pos = find(v.begin(), v.end(), 2); // 查找值2的位置pos = v.insert(pos, 10); // 在找到的位置插入10*pos *= 10; // 修改插入的元素值为100// 利用迭代器打印vector<int>::iterator it = v.begin();while (it != v.end()) {cout << *it << " ";++it;}}void test2() {// 删除vector<int> v;for (int i = 0; i < 10; i++) {v.pushback(i); // 添加偶数v.pushback(i); // 添加偶数}auto it = v.begin(); // 自动类型推导while (it != v.end()) {if (*it % 2 == 0) {it = v.erase(it); // 删除偶数} else {++it;}}for (auto ch : v) {cout << ch << " "; // 输出剩余的奇数}}void test3() {vector<int> v;for (int i = 0; i < 10; i++) {v.pushback(i); // 添加0-9}cout << v.size() << endl; // 输出向量大小for (auto ch : v) {cout << ch << " "; // 输出所有元素}cout << endl;v.resize(5); // 缩小向量for (auto ch : v) {cout << ch << " "; // 输出前五个元素}cout << endl;v.resize(20); // 扩大向量for (auto ch : v) {cout << ch << " "; // 输出所有元素}}void test4() {vector<int> a1;a1.pushback(1);a1.pushback(1);a1.pushback(1);a1.pushback(1);a1.pushback(1);vector<int> a2 = a1; // 拷贝构造for (auto ch : a2) {cout << ch << " "; // 输出拷贝的内容}cout << endl;a1.clear(); // 清空a1cout << a1.size() << endl; // 输出a1的大小}void test5() {vector<string> v;v.pushback("hello"); // 添加字符串"hello"vector<string> vv(v); // 拷贝构造for (auto ch : vv) {cout << ch << " "; // 输出拷贝的内容}}
}
命名空间定义
namespace yang { ... }
: 定义了一个命名空间yang
,用来避免与其他部分的程序或标准库中的名字发生冲突。类模板定义
template<class T> class vector { ... }
: 定义了一个名为vector
的类模板,它可以为任何数据类型T
实例化。公共类型定义
typedef T* iterator;
: 定义了一个非常量迭代器的类型别名。typedef const T* const_iterator;
: 定义了一个常量迭代器的类型别名。构造函数
vector() = default;
: 默认构造函数,使用编译器提供的默认行为。vector(const vector<T>& v);
: 拷贝构造函数,用于通过拷贝另一个vector
创建新的vector
。template <class InputIterator> vector(InputIterator first, InputIterator last);
: 范围构造函数,接受两个迭代器,将它们之间的元素复制到新的vector
中,并以此初始化vector
。vector(size_t n, const T val = T());
: 构造函数,创建一个含有n
个元素的vector
,这些元素都被初始化为val
。vector(int n, const T val = T());
: 类似于上述构造函数,但参数是int
类型。这种写法通常不推荐,因为int
可能会导致溢出问题。析构函数
~vector();
: 析构函数,释放vector
占用的内存。成员函数
size_t size() const;
: 返回vector
中的元素数量。size_t capacity() const;
: 返回vector
的容量,即已分配的存储空间可以容纳的元素数量。bool empty();
: 如果vector
是空的,则返回true
。void clear();
: 清除vector
中的所有元素,但保留其分配的存储空间。iterator begin();
: 返回指向vector
第一个元素的迭代器。const_iterator begin() const;
: 返回指向vector
第一个元素的常量迭代器。iterator end();
: 返回指向vector
末尾之后位置的迭代器。const_iterator end() const;
: 返回指向vector
末尾之后位置的常量迭代器。void reserve(size_t n);
: 预先分配足够存放n
个元素的存储空间,但不一定改变vector
的大小。memcpy是内存的二进制格式拷贝,将一段内存空间中内容原封不动的拷贝到另外一段内存 空间中
如果拷贝的是自定义类型的元素,memcpy既高效又不会出错,但如果拷贝的是自定义类型 元素,并且自定义类型元素中涉及到资源管理时,就会出错,因为memcpy的拷贝实际是浅 拷贝。
void resize(size_t n, T val = T());
: 改变vector
的大小为n
,并用val
初始化新添加的元素。void push_back(const T& val);
: 在vector
的末尾添加一个新元素。void pop_back();
: 删除vector
末尾的一个元素。void swap(vector<T>& v);
: 交换两个vector
的内容。vector<T>& operator=(vector<T> v);
: 移动赋值运算符,用于从另一个vector
复制内容到当前vector
。T& operator[](size_t i);
: 返回对vector
中第i
个元素的引用。const T& operator[](size_t i) const;
: 返回对vector
中第i
个元素的常量引用。iterator insert(iterator pos, const T& val);
: 在给定的迭代器位置pos
插入一个值val
。iterator erase(iterator pos);
: 删除给定迭代器位置pos
指向的元素。测试函数
test1()
: 测试vector
的基本功能,如reserve
,push_back
,insert
, 和find
。test2()
: 测试erase
函数来删除满足特定条件的元素。test3()
: 测试resize
函数改变vector
的大小。test4()
: 测试拷贝构造函数和clear
函数。test5()
: 测试字符串类型的vector
拷贝构造函数。