vector简单模拟

🕗 发布于 2024-10-16 19:26 算法

1.二维vector

下图可以看到vector<int>指向的是几个int型的，而vector<vector<int>>则指向的是几个vector<int>型的内容，而它们又指向几个int型的内容，三维就重复就可以理解。

例题：

可以得到的规律中间(假设索引为2)的等于上面索引为2和1的相加，而且第一行和第二行不用动都是1，且每一行的头尾也不动是1。

先构建二维vector，然后以i+1(列的增加)来递增，然后用俩重循环来给中间赋值。

class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        vector<vector<int>> v(numRows);
        for(size_t i=0;i<numRows;i++)
        {
            v[i].resize(i+1,1);
        }

        for(int i=0;i<v.size();i++)
        {
            for(int j=1;j<v[i].size()-1;++j)
            {
                v[i][j]=v[i-1][j]+v[i-1][j-1];
            }
        }
        return v;
    }
};

2.代码解析

1.迭代器实现

用typedef重命名T*为iterator，成员变量是_start,_finish,_end_of_storage，所以begin()获取_start指向的位置，end()获取_finish指向的位置，后面俩个在函数后面+const的是指里面的内容都是只读不可以修改。

        typedef T* iterator;
typedef const T* const_iterator;

iterator begin()
{
return _start;
}
iterator end()
{
return _finish;
}

const_iterator begin() const
{
return _start;
}

const_iterator end() const
{
return _finish;
}


private:
iterator _start = nullptr;
iterator _finish = nullptr;
iterator _end_of_storage = nullptr;

2. vector的大小容量以及判断空

vector的size可以通过首尾指针相减得到的距离值获取，容量则就使用原本容量空间-首的位置，判断是否为空看_start和_finish是否相等。


size_t size()
{
return _finish - _start;
}

size_t capacity() const
{
return _end_of_storage - _start;
}

bool empty()
{
return _start == _finish;
}

3. 容量设置

比较n和capacity的大小，因为我们是只打不小，所以只有大了才指向扩容，要保留原的size，如果不保留原来的size则在_finish=tmp+old_size这里就有问题，因为size就是_finish-_start，而不保留则用的是原来vector的size那么_finish=_finish(前一个的_finish)，那么_start指向的是新的vector，而_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());
delete[] _start;

_start = tmp;
_finish = tmp + old_size;
_end_of_storage = tmp + n;
}
}

4.尾插和尾删

在尾插时要判断容量是否足够，不够就扩容，够就在_finish处插入值，然后再把_finish指向插入处的下一个位置，尾删要想判断是否为空，有才能删除，直接把_finish-1就删除了一个数据。

void push_back(const T& x)
{
if (_finish == _end_of_storage)
{
reserve(capacity() == 0 ? 4 : capacity() * 2);
}
*_finish = x;
++_finish;
}

void pop_back()
{
assert(!empty());
--_finish;
}

5.在指定位置插入

这里len保存pos-_start是因为下面有reserve函数会改变vector，_start和_finish会去新的vector而pos还在旧的vector，接下来就是挪动数据把pos位置空出来填要插入的数据。

iterator insert(iterator pos, const T& x)
{
if (_finish == _end_of_storage)
{
size_t len = pos - _start;//怕迭代器失效

reserve(capacity() == 0 ? 4 : 2 * capacity());
pos = _start + len;
}

iterator end = _finish - 1;//因为有一个数据finish+1 但是索引0处才有数据，而finish=1处没有所以访问要-1
while (end >= pos)
{
*(end + 1) = *end;
--end;
}
*pos = x;
++_finish;

return pos;
}

6.重载函数

_start[i]=*(_start+i)，获取对应位置的解引用值，下面则是返回常量引用且是只读。

T& operator[](size_t i)
{
assert(i < size());

return _start[i];
}

const T& operator[](size_t i) const
{
assert(i < size());

return _start[i];
}

7.测试函数

先尾插五个数据，然后在位置2插入20，这里用auto p接收pos而不用pos是因为插入后vector跟没插入之前是不一样了，所以pos失效了，可以通过函数返回值来得到位置，进而得到想要结果，输入在insert中有修正，但是pos是在insert函数的形参，而p是在测试函数的形参，这俩是没有关系的，除非实参修正才有用。(如果insert用的是引用也不可以，因为表达式的返回是临时变量具有常性，所以要有const &才行，但是加了const就不能修改pos了，所以不可以)

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

print_vector(v);

v.insert(v.begin() + 2, 30);
print_vector(v);

int x;
cin >> x;

auto p = find(v.begin(), v.end(), x);
if (p != v.end())
{
// insert以后p就是失效，不要直接访问，要访问就要更新这个失效的迭代器的值
//v.insert(p, 40);
//(*p) *= 10;

p = v.insert(p, 40);
(*(p + 1)) *= 10;
}
print_vector(v);
}

find函数解释：

std::find 函数的原型定义在 C++ 标准库的 <algorithm> 头文件中。以下是其基本原型：
template<class ForwardIt, class T>
ForwardIt find(ForwardIt first, ForwardIt last, const T& value);

参数说明

1.ForwardIt first：范围的开始迭代器，表示要搜索的序列的第一个元素的迭代器。
2.ForwardIt last：范围的结束迭代器，表示要搜索的序列的最后一个元素后面的迭代器（不包含该位置）。
3.const T& value：要查找的值，可以是任何类型（例如基本数据类型、用户定义类型等）。

返回值

4.返回一个迭代器，指向找到的第一个匹配元素。如果在指定范围内没有找到该元素，则返回 last 迭代器。

使用示例
这里是一个简单的示例，展示如何使用 std::find 函数：
#include <iostream>
#include <vector>
#include <algorithm>

int main() {
std::vector<int> v = {1, 2, 3, 4, 5}; // 创建一个整数类型的vector
int x = 3; // 要查找的值

// 使用 std::find 查找值 x
auto p = std::find(v.begin(), v.end(), x);

// 检查查找结果
if (p != v.end()) {
std::cout << "Found " << x << " at index " << std::distance(v.begin(), p) << std::endl;
} else {
std::cout << x << " not found in the vector." << std::endl;
}

return 0;
}

总结
std::find 是一种非常方便的查找算法，能够简化在容器中查找元素的操作，并且通过使用模板支持各种数据类型。

3.总代码

vector.h

#pragma once
#include<iostream>
#include<assert.h>

namespace zym
{
template<class T>
class vector
{
public:
typedef T* iterator;
typedef const T* const_iterator;

iterator begin()
{
return _start;
}
iterator end()
{
return _finish;
}

const_iterator begin() const
{
return _start;
}

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());
delete[] _start;

_start = tmp;
_finish = tmp + old_size;
_end_of_storage = tmp + n;
}
}

size_t size()
{
return _finish - _start;
}

size_t capacity() const
{
return _end_of_storage - _start;
}

bool empty()
{
return _start == _finish;
}

void push_back(const T& x)
{
if (_finish == _end_of_storage)
{
reserve(capacity() == 0 ? 4 : capacity() * 2);
}
*_finish = x;
++_finish;
}

void pop_back()
{
assert(!empty());
--_finish;
}
iterator insert(iterator pos, const T& x)
{
if (_finish == _end_of_storage)
{
size_t len = pos - _start;//怕迭代器失效

reserve(capacity() == 0 ? 4 : 2 * capacity());
pos = _start + len;
}

iterator end = _finish - 1;//因为有一个数据finish+1 但是索引0处才有数据，而finish=1处没有所以访问要-1
while (end >= pos)
{
*(end + 1) = *end;
--end;
}
*pos = x;
++_finish;

return pos;
}
T& operator[](size_t i)
{
assert(i < size());

return _start[i];
}

const T& operator[](size_t i) const
{
assert(i < size());

return _start[i];
}




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

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

cout << endl;

for (auto e : v)
{
cout << e << "";
}
cout << endl;
}
void test_vector2()
{
vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
v.push_back(5);

print_vector(v);

v.insert(v.begin() + 2, 30);
print_vector(v);

int x;
cin >> x;

auto p = find(v.begin(), v.end(), x);
if (p != v.end())
{
// insert以后p就是失效，不要直接访问，要访问就要更新这个失效的迭代器的值
//v.insert(p, 40);
//(*p) *= 10;

p = v.insert(p, 40);
(*(p + 1)) *= 10;
}
print_vector(v);
}
}

test.cpp


#include<iostream>

using namespace std;
#include"vector.h"


int main()
{
zym::test_vector2();
}

原文地址：https://blog.csdn.net/2302_80378107/article/details/142982415

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

上一篇：AI核身-金融场景凭证篡改检测YOLO原理
下一篇：Vulhub BlackMarket: 1靶机详解

纯HTML实现标签页切换
ul><li><a>#tab1<div>:target总结：使用纯HTML和CSS实现标签页切换是一种简洁有效的方法，特别适合简单的内容展示需求。它提供了良
阅读更多2024-10-18
MySQL中的增查操作：探索数据的奥秘，开启数据之门
在MySQL中，增加数据可以通过INSERT INTO语句来实现。INSERT INTO语句可以将数据插入到表中的一行或多行中。可以通过指定列名和相应的值来插入数据，也可以省略列名，但必须按照表的列顺
阅读更多2024-10-18
鸿蒙网络编程系列3-TCP客户端通讯示例
TCP协议是传输层最重要的协议，提供了可靠、有序的数据传输，是多个广泛使用的表示层协议的运行基础，相对于UDP来说，TCP需要经过三次握手后才能建立连接，建立连接后才能进行数据传输，所以效率差了一些，
阅读更多2024-10-18
群晖前面加了雷池社区版，安装失败，然后无法识别出用户真实访问IP
有nas的相信对公网都不模式，在现在基础上传带宽能有100兆的时代，有公网代表着家里有一个小服务器，像百度网盘，优酷这种在线服务都能部署为私有化服务。但现在运营商几乎不可能提供公网ip，要么自己买个云
阅读更多2024-10-18
Day11-数据库服务主从扩展
1、数据库过滤复制实践2、数据库半同步复制实践（数据库同步一致性）3、数据库GTID复制实践（GTID方式实现主从）4、数据库克隆复制实践5、数据库多源复制实践（将多个主库的数据
阅读更多2024-10-18
CTFHUB技能树之SQL——MySQL结构
1 and 1=2 union select 1,2#或者-1 union select 1,2#都行。没有发现数据，猜测数据可能不存在数据库中，修改注入语句。知道字段数量为2后，可以查看数据库位置。
阅读更多2024-10-18
关于编程小白如何成为大神？
爱我的我爱的都不能选，应该是我爱她她也爱我的（这个相对比较正确，但是很难的，现在我看到女孩，有的时候，就觉得这个女孩很好看，妈的！我的零碎时间都是用来进行单词的背诵，也是在不断地背单词中，我找到了自
阅读更多2024-10-18
【Linux线程】Linux多线程编程：深入理解线程互斥与同步机制
在当今这个数据驱动、高性能计算盛行的时代，多线程编程已经成为软件开发中不可或缺的一部分。Linux，作为开源世界的领头羊，其强大的多线程支持为开发者提供了广阔的舞台，让高并发、高性能的应用得以实现。然
阅读更多2024-10-18
从零开始实现大语言模型（十二）：文本生成策略
本文介绍大语言模型`GPTModel`预测生成连续自然语言文本的流程，以及4种从概率分布中选择下一个token的策略，并实现文本生成函数`generate_text`。
阅读更多2024-10-18
modbus poll监控抗凝秤通信err提示有crc校验错误等原因
一、CRC错误原因及解决方法CRC（循环冗余校验）错误是数据传输过程中常见的错误类型之一，可能由以下原因引起：噪声干扰：在数据传输过程中，噪声干扰可能导致数据位的改变，从而引发CRC校验错误。通过波形
阅读更多2024-10-18