【C++笔记】vector使用详解及模拟实现

🕗 发布于 2024-11-16 16:58 c++ 笔记

前言

各位读者朋友们，大家好！上期我们讲了string类的模拟实现，这期我们开启vector的讲解。

一.vector的介绍及使用

1.1 vector的介绍

vector的文档
使用STL的三个境界：能用、明理、能扩展，下面学习vector，我们也按照这个境界去学习。

1.2 vector的使用

我们在学vector的时候，一定要看文档：vector的文档vector在实际中非常重要，在实际中我们熟悉常用的接口即可，下面给出了常用的需要掌握的接口。

1.2.1vector的定义

在这里插入图片描述
vector是可以改变大小的数组序列容器，也就是数据结构的顺序表。

constructor构造函数声明	接口说明
vector()重点	无参构造
vector (size_type n, const value_type& val = value_type())	构造并初始化n个val
vector(const vector& x);重点	拷贝构造
vector(InputIterator first,InputIterator last);	使用迭代器进行初始化构造

无参构造
构造并初始化n个val
迭代器区间构造

1.2.2 vector iterator的使用

iterator的使用	接口说明
begin + end (重点)	获取第一个数据位置的iterator/const_iterator，获取最后一个数据的下一个位置的iterator/const_iterator
rbegin + rend	获取最后一个数据位置的reverse_iterator,获取第一个数据前一个位置的reverse_iterator

在这里插入图片描述

反向迭代器

1.2.3 vector空间增长的问题

容器空间	接口说明
size	获取数据个数
capacity	获取容量大小
empty	判断是否为空
resize(重点)	改变vector的size
reserve(重点)	改变vector的capacity

capacity
在这里插入图片描述

// 测试vector的默认扩容机制
void TestVectorExpand()
{
 size_t sz;
 vector<int> v;
 sz = v.capacity();
 cout << "making v grow:\n";
 for (int i = 0; i < 100; ++i) 
 {
 v.push_back(i);
 if (sz != v.capacity()) 
 {
 sz = v.capacity();
 cout << "capacity changed: " << sz << '\n';
 }
 }
}

在这里插入图片描述
可以看出在VS环境下，编译器是1.5倍扩容的，而在g++环境中是2倍扩容的。

resize
在这里插入图片描述

如果在resize时，我们没有给初值，会使用默认构造给的值。

reserve

在n>capacity时，会扩容，但是在n<capacity时，vector的reserve在任何环境中都不会缩容。但是string在这种情况下，g++环境中会进行缩容。

int main()
{
vector<int> v(10, 520);
v.reserve(20);
cout << v.size() << endl;
cout << v.capacity() << endl;

v.reserve(15);
cout << v.size() << endl;
cout << v.capacity() << endl;

v.reserve(5);
cout << v.size() << endl;
cout << v.capacity() << endl;

return 0;
}

在这里插入图片描述
g++环境：

1.2.4 vector的增删查改

vector的增删查改	接口说明
push_back	尾插
pop_back	尾删
find	查找（这个是算法模块实现，不是vector的成员接口）
insert	在pos位置之前插入的数据
erase	删除pos位置的数据
swap	交换两个vector的数据空间
operator[]	像数组一样访问

push_back

int main()
{
vector<int> v(1, 520);
v.push_back(1314);
return 0;
}

在这里插入图片描述

pop_back

int main()
{
vector<int> v(1, 520);
v.pop_back();
return 0;
}

在这里插入图片描述

find

find函数找出第一个和val相等的元素，并返回这个元素的迭代器，如果没有找到就返回last(最后一个元素下一个位置的迭代器)。

int main()
{ 
vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(520);
v.push_back(1314);
v.push_back(3);
v.push_back(7);
vector<int>::iterator it = find(v.begin(), v.end(), 520);
cout << *it << endl;

it = find(v.begin(), v.end(), 10);
if (it == v.end())
{
cout << "没找到，返回最后一个元素下一个位置的迭代器" << endl;
}
return 0;
}

在这里插入图片描述

insert

这里的插入都是使用的迭代器
iterator insert (iterator position, const value_type& val)

int main()
{
vector<int> v(5, 520);
v.insert(v.begin() + 3, 1314);
for (auto a : v)
{
cout << a << ' ';
}
cout<<endl;
return 0;
}

在第三个位置之前插入1314
在这里插入图片描述
void insert (iterator position, size_type n, const value_type& val)

int main()
{
vector<int> v(5, 520);
v.insert(v.begin() + 3, 2,1314);
for (auto a : v)
{
cout << a << ' ';
}
cout << endl;
return 0;
}

在这里插入图片描述
void insert (iterator position, InputIterator first, InputIterator last)

int main() 
{
vector<int> v1(5, 520);
vector<int> v2(5, 1314);
v1.insert(v1.begin() + 3, v2.begin() + 3, v2.end());// [begin,end)
for (auto a : v1)
{
cout << a << " ";
}
cout << endl;
return 0;
}

在第三个位置之前插入迭代器区间，左闭右开
在这里插入图片描述

在这里插入图片描述

erase

erase (iterator position)

int main()
{
vector<int> v1(5, 520);
v1.push_back(1314);
for (auto a : v1)
{
cout << a << " ";
}
cout << endl;
v1.erase(v1.end() - 1);
for (auto a : v1)
{
cout << a << " ";
}
cout << endl;
return 0;
}

删除最后一个位置的元素
在这里插入图片描述
erase (iterator first, iterator last)

依旧是左闭右开区间

int main()
{ 
vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(520);
v.push_back(1314);
v.push_back(3);
v.push_back(7);
v.erase(v.begin() + 1, v.end() - 1);
for (auto a : v)
{
cout << a << " ";
}
return 0;
}

在这里插入图片描述

swap

int main() {
vector<int> v1(2, 520);
vector<int> v2(4, 1314);
cout << "交换前：" << endl;
for (auto a : v1) {
cout << a << " ";
}
cout << endl;
for (auto a : v2) {
cout << a << " ";
}
cout << endl;
v1.swap(v2);
cout << "交换前：" << endl;
for (auto a : v1) {
cout << a << " ";
}
cout << endl;
for (auto a : v2) {
cout << a << " ";
}
cout << endl;
return 0;
}

在这里插入图片描述

operator[]

int main()
{
vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(520);
v.push_back(1314);
v.push_back(3);
v.push_back(7);
for (int i = 0; i < v.size(); ++i)
{
cout << v[i] << " ";
}
cout << endl;
return 0;
}

在这里插入图片描述

流提取和流插入
vector是不支持流插入和流提取重载的

vector<int> v;
//流提取单个数据
int x;
cin >> x;
v.push_back(x);
// 多组数据
vector<int>v1(3, 0);
for (int i = 0; i < 3; ++i)
{
cin >> v1[i];
}
// 流插入
for (auto a : v1)
{
cout << v1[i] << " ";
}

1.3 vector类型存储

在这里插入图片描述
vcector可以看作顺序表，它不仅可以存储内置类型，也可以存储自定义类型。

1.3.1 vector< string >

int main()
{
vector<string> v;
string s("5201314");
v.push_back(s);

v.push_back("1314520");
for (auto a : v)
{
cout << a << " ";
}
cout << endl;
return 0;
}

但是这样在范围for遍历打印的时候会进行string类的拷贝给a，这样效率会很低，所以我们可以使用引用，不修改数据的情况下加上const。
在这里插入图片描述

1.3.2 vector<vector< int >>

vector<vector< int >>可以看成是二维数组，下面通过vector的结构看一下：
vector可以看成是顺序表：
在这里插入图片描述

其实编译器这里实例化出了两个模板，一个是vector<vector< int >> ，一个是vector< int >。

所以我们在遍历二维数组的时候实际上是调用了两次operator[]

第一次调用返回vector<vector< int >>& ，第二次调用返回int&，也就是第一次调用找到存在整个vector的对应位置的vector，第二次调用返回对应位置的vector的相应位置的元素。
在这里插入图片描述
上面理解了之后我们看一道OJ题杨辉三角

class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        vector<vector<int>> vv(numRows);// 这里未传实参，
        // 使用缺省值vector<int>
        for (int i = 0; i < numRows; ++i)
        {
            vv[i].resize(i + 1, 1); //将所有值都初始化为1
        }
        for (int i = 2; i < numRows; ++i)// 从下标为2的那一行开始
        {
            for (int j = 1; j < vv[i].size() - 1; ++j)// 不计算第一个和最后一个数据
                // vv[i].size 是当前一行的数据个数
            {
                vv[i][j] = vv[i - 1][j - 1] + vv[i - 1][j];
            }
        }
        return vv;
    }
};

二. vector深度剖析及模拟实现

在这里插入图片描述
通过vector的源码，我们看到，vector的底层实际有3个成员变量，它们分别对应

start	begin(顺序表的头)
finish	end(顺序表最后一个元素的下一个位置)
end_of_storage	capacity(顺序表的空间)

在这里插入图片描述
下面开始模拟实现vector：
vector的底层

namespace Yuey
{
template <class T>
class vector
{
public:
typedef T* iterator;

private:
iterator _start;
iterator _finish;
iterator _end_of_storage;
};
}

2.1 push_back

template <class T>
class vector
{
public:
typedef T* iterator;
size_t size()
{
return _finish - _start;// [_statr, _finish) 左闭右开相减得元素个数
}
size_t capacity()
{
return _end_of_storage - _start;// [_statr, _end_of_storage) 左闭右开相减得元素个数
}
void reserve(size_t n)
{
if (n > capacity())
{
// 开空间拷贝
T* tmp = new T[n];
memcpy(tmp, _start, size() * sizeof(T));
delete[] _start;
_start = tmp;
_finish = _start + size();
_end_of_storage = _start + n;
}
}
T& operator[](size_t n)
{
assert(n < size());
return _start[n];
}
void push_back(const T& x)
{
if (size() == capacity())
{
reserve(capacity() == 0 ? 4 : 2 * capacity());
}
*_finish = x;
++_finish;
}
private:
iterator _start = nullptr;
iterator _finish = nullptr;
iterator _end_of_storage = nullptr;
};

为了实现push_back这一功能，我们实现了size()、capacity()、reserve()函数，为了方便测试又实现了[]的重载。下面测试一下push_back这一接口：
在这里插入图片描述
发现挂了，调试看一下

void reserve(size_t n)
{
if (n > capacity())
{
// 开空间拷贝
size_t old_size = size(); //记录扩容前的size
T* tmp = new T[n];
memcpy(tmp, _start, size() * sizeof(T));
delete[] _start;
_start = tmp;
_finish = _start + old_size;
_end_of_storage = _start + n;
}
}

2.2 迭代器

typedef T* iterator;
const typedef T* const_iterator;
iterator begin()
{
return _start;
}
iterator end()
{
return _finish;
}
const_iterator begin() const
{
return _start;
}
const_iterator end() const
{
return _finish;
}

在这里插入图片描述

2.3 vector的打印

void print_vector(const vector<int>& v)
{
vector<int>::const_iterator  it = v.begin();
while (it != v.end())
{
cout << *it << " ";
++it;
}
}

这样写只能打印vector< int >类型的，没法打印存储其它类型的vector，但是打印的逻辑是一样的，因此我们还可以再套一层模板给打印函数：

template <class T>
void print_vector(const vector<T>& v)
{
    typename vector<T>::const_iterator it = v.begin();
// auto it = v.begin();
while (it != v.end())
{
cout << *it << " ";
++it;
}
cout << endl;
}

在这里插入图片描述

2.4 pop_back

bool empty()
{
return _start == _finish;
}
void pop_back() 
{
assert(!empty());// 尾删但不能为空
--_finish;
}

在这里插入图片描述

2.5 迭代器失效

1. 在指定位置插入一个数据

在这里插入图片描述
在这里插入数据的时候没有进行扩容，程序可以正常运行，但是如果我们进行扩容，程序还能正常运行吗？

程序不能正常运行，这就涉及到了迭代器失效的问题

调试发现pos是大于end的，while循环不能执行
在这里插入图片描述

void insert(iterator pos, const T& val)
{
// 扩容
if (size() == capacity())
{
size_t len = pos - _start;
reserve(capacity() == 0 ? 4 : 2 * capacity());
pos = _start + len;
}
iterator end = _finish - 1;
while (end >= pos)
{
*(end + 1) = *end;
--end;
}
*pos = val;
++_finish;
}

在这里插入图片描述
改进之后就解决了这个问题。

void test_vector6()
{
vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
int x;
cin >> x;
vector<int>::iterator p = find(v.begin(), v.end(), x);
if (p != v.end())
{
v.insert(p, 520);
(*p) *= 10;
}
print_vector(v);
}

2. insert之后的迭代器失效

想要通过find函数找一个数值，并在这个数据的位置插入520，然后让pos位置的值乘10
在这里插入图片描述

发现并没有实现需求，这是因为pos还是指向原空间的位置，没有指向扩容后的空间，虽然我们上面处理了这种情况，但是是对形参进行的修改，实参是不会改变的。那形参使用引用可不可以解决这个问题呢？答案是可以的，但是在这里插入图片描述
这种情况就是不适用了，返回值存在一个const临时对象中，调用会存在权限放大的问题，那将普通引用改为const引用不就好了？改为const引用之后pos的值就不能更改了。

库中的insert函数返回了新插入元素的迭代器，我们想修改可以对返回值进行操作后再修改。
改进的insert函数：

iterator insert(iterator pos, const T& val)
{
assert(pos >= _start && pos <= _finish);
// 扩容
if (size() == capacity())
{
size_t len = pos - _start;
reserve(capacity() == 0 ? 4 : 2 * capacity());
pos = _start + len;
}
iterator end = _finish - 1;
while (end >= pos)
{
*(end + 1) = *end;
--end;
}
*pos = val;
++_finish;

return pos;
}

将我们的insert函数也加上返回值之后再去实现想要的功能：
在这里插入图片描述
实现了。
上面这种情况也是迭代器失效的一种，对于使用完insert之后的迭代器就失效了，不要直接进行访问，如果需要访问就去更新迭代器的值！！！

vs下进行了强制的检查，使用insert之后的迭代器会报错，不管有没有扩容。

3. erase时迭代器失效

删除指定位置的元素：挪动数据从前往后挪动

void erase(iterator pos)
{
assert(pos >= _start && pos < _finish);
iterator it = pos + 1;
while (it < _finish)
{
*(it - 1) = *it;
++it;
}
--_finish;
}

这里我们写一个程序测试一下，要求删除偶数：

void test_vector8()
{
vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
print_Container(v);

auto it = v.begin();
while (it != v.end())
{
if (*it % 2 == 0)
{
v.erase(it);
}
++it;
}
print_Container(v);
}

在这里插入图片描述
三种情况两种不正确，我们分析一下：

对于第二种
第三种情况：

来看一下库中的erase是怎么实现的

和insert一样都带回了一个迭代器，它返回的是被函数调用擦除的最后一个元素之后的元素的新位置的迭代器，也就是pos位置

iterator erase(iterator pos)
{
assert(pos >= _start && pos < _finish);
iterator it = pos + 1;
while (it < _finish)
{
*(it - 1) = *it;
++it;
}
--_finish;
return pos;
}

这样修改之后，上面的两种情况都可以解决了

void test_vector8()
{
vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
print_Container(v);

auto it = v.begin();
while (it != v.end())
{
if (*it % 2 == 0)
{
it = v.erase(it);
}
else
{
++it;
}
}
print_Container(v);
}

几乎所有的erase之后的迭代器都失效了，要更新之后再使用

2.6 resize

在这里插入图片描述
这里的val是使用了匿名对象，调用默认构造函数，对于内置类型和自定义类型都适用，看一下内置类型的默认构造：

void resize(size_t n, T val = T())
{
if (n < size())
{
_finish = _start + n;
}
else // n >= _finish
{
reserve(n);// 自动扩容
while (_finish < _start + n)
{
*_finish = val;
++_finish;
}
}
}

2.7 构造函数

拷贝构造

vector(const vector<T>& v)
{
reserve(v.size());
for (auto& e : v)
{
push_back(e);
}
}

在这里插入图片描述
调用会报错，之前为什么没有报错呢？我们不写构造函数，编译器会帮我们生成默认构造函数，但是我们写了拷贝构造函数，也就相当于我们写了构造函数，编译器就不会帮我们生成默认构造函数了。

迭代器区间构造

这个构造支持不同容器之间的构造

template<class InputIterator>
vector(InputIterator first, InputIterator last)
{
while (first != last)
{
push_back(*first);
++first;
}
}

在这里插入图片描述
类模板的成员函数也可以作为函数模板

n个值构造

vector(size_t n,T val = T())
{
reserve(n);
for (size_t i = 0; i < n; ++i)
{
push_back(val);
}
}

在这里插入图片描述
下面多测几组：

我们可以将size_t改为int来解决这个问题。
在这里插入图片描述

2.8 赋值运算符重载

void swap(vector<T>& tmp)
{
std::swap(_start, tmp._start);
std::swap(_finish, tmp._finish);
std::swap(_end_of_storage, tmp._end_of_storage);
}
vector<T>& operator=(vector<T> tmp)
{
swap(tmp);
return *this;
}

2.9 扩容时的拷贝问题

在这里插入图片描述
上面出现的问题是扩容后出现了乱码，这是怎么导致的呢？

这里发现tmp和_start的指向的空间是同一个。

在扩容时，memcpy拷贝是一个字节一个字节的拷贝，将v1中的内容拷贝到tmp中，由于v1中存的是string类，存储的是指向字符串的指针，将指针拷贝给tmp是浅拷贝,拷贝结束后，调用delete函数， string类会调用析构函数，_str指向的空间被释放，因此tmp拷贝过来的_str被释放了就无法访问，就会出现乱码，然后_start指向的空间也被释放。想要解决这个问题就只能走深拷贝。

void reserve(size_t n)
{
if (n > capacity())
{
// 开空间拷贝
size_t old_size = size(); //记录扩容前的size
T* tmp = new T[n];
//memcpy(tmp, _start, old_size * sizeof(T));
int i = 0;
while (i < old_size)
{
tmp[i] = _start[i];
++i;
}
delete[] _start;
_start = tmp;
_finish = _start + old_size;
_end_of_storage = _start + n;
}
// 出作用域tmp销毁
}

这里用了赋值运算符重载，完成了深拷贝，调用的是string类的赋值运算符重载
在这里插入图片描述
原空间被释放了也不影响现在的空间。

结语

以上就讲完了vector的使用及模拟实现，希望对大家有所帮助，感谢大家的阅读，欢迎大家批评指正！

原文地址：https://blog.csdn.net/A2885A/article/details/143661071

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：js像循环数组那样循环一个数字，Array.from()
下一篇：Java基础知识03(内部类)【24.11.25】

基于RK3588的移动充电机器人应用解决方案
伴随着国内新能源汽车保有量的持续增长，充电难题愈发凸显，配套充电设施的建设需求进一步扩大。可外接4G/5G、WiFi模块，用于传感数据、视频数据的上传，同时，通过网络的连接，能够远程监控机器人的状态和
阅读更多2024-11-16
开源，一天200star，解锁视频字幕生成新方式——一款轻量级开源字幕工具，免费，支持花字，剪映最新会员模式吃相太难看了
是一款基于开源的轻量级视频字幕生成工具，由开发者 @WEIFENG2333 精心打造。其主要目的是为用户提供一套免费、易用的字幕生成方案，支持各种视频格式，并结合现代化的自然语言处理技术，实现精准、高
阅读更多2024-11-16
docker：基于Dockerfile镜像制作完整案例
docker：基于Dockerfile镜像制作完整案例
阅读更多2024-11-16
【数据库系列】 Spring Boot 集成 Neo4j 的详细介绍
Spring Boot 提供了对 Neo4j 的良好支持，使得开发者可以更方便地使用图数据库。通过使用 Spring Data Neo4j，开发者可以轻松地进行数据访问、操作以及管理。本文将详细介绍如
阅读更多2024-11-16
微信小程序02-页面制作
微信小程序提供了丰富的组件，如view、image等，用于构建具有微信风格的UI界面。视口单位用于移动端页面适配，如vw和vh。表单组件用于收集用户信息，如form、button、input等。
阅读更多2024-11-16
2024 CCF中国开源大会“开源科学计算与系统建模openSCS”分论坛成功举办
目前MWORKS用户已遍及国内外295所高校，仅深圳就有41家应用验证企业，覆盖新能源、芯片、车辆、低空经济、医疗、制造、自动化、电力、航天、金融、船舶等优势行业单位，已经具备良好的生态基础。该委员会
阅读更多2024-11-16
C&C++内存管理
pChar3是指针变量，存在栈中，*pChar3是由const修饰的，pChar3指向的内容不能修改，内容具有常属性，因此pChae3存在代码段中，也就是常量区。内存泄漏并不是指内存在物理上的消失，而
阅读更多2024-11-16
单片机面试
答案：宏定义是在编译预处理阶段被处理的。预处理包含：头文件包含，宏替换，条件编译，去除注释，添加行号。
阅读更多2024-11-16
Ubuntu23.10下解决C语言调用mysql.h问题
在学习C语言和MySQL的调用的时候遇到包和版本的问题，由于使用的书很老（10年的），因此很多MySQL的包已经过时，在查找很多资料和询问gpt之后得到了解决方案
阅读更多2024-11-16
高级java每日一道面试题-2024年11月07日-Redis篇-Redis有哪些功能?
Redis 是一个功能强大且灵活的 NoSQL 数据库，广泛应用于缓存、消息队列、实时分析等多种场景。在高级 Java 面试中，了解 Redis 的数据类型、持久化、发布/订阅、事务、Lua 脚本、主
阅读更多2024-11-16

【C++笔记】vector使用详解及模拟实现

前言

一.vector的介绍及使用

1.1 vector的介绍

1.2 vector的使用

1.2.1vector的定义

1.2.2 vector iterator的使用

1.2.3 vector空间增长的问题

1.2.4 vector的增删查改

1.3 vector类型存储

1.3.1 vector< string >

1.3.2 vector<vector< int >>

二. vector深度剖析及模拟实现

2.1 push_back

2.2 迭代器

2.3 vector的打印

2.4 pop_back

2.5 迭代器失效

1. 在指定位置插入一个数据

2. insert之后的迭代器失效

3. erase时迭代器失效

2.6 resize

2.7 构造函数

2.8 赋值运算符重载

2.9 扩容时的拷贝问题

结语

相关文章