C++迈向精通:vector复现与sort复现
vector复现
思考过程
对于vector考虑如下几点:
- 底层数据结构
- 算法实现方式
- 对外表现形式
这里底层的数据结构采用了顺序表,当然,原版STL中的vector也是采用的顺序表。
算法实现的方式放在代码中去设计
对外表现形式是数组,因此需要重载 []
运算符。
对于sort考虑如下几点:
- 算法(快排)
- 模板类的实现方式(放在代码中实现)
代码
详细描述根据注释来解释。
#include <cstddef>
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <functional>// 命名空间
namespace my {
template <typename T>class vector {
public:// 迭代器typedef T * iterator;// 默认大小为2vector(size_t n = 2) {__size = n;data = (T *)malloc(sizeof(T) * __size);_Finish = data + __size;_M_pos = data;}vector(const vector &v) {__size = v.__size;data = (T *)malloc(sizeof(T) * __size);for (size_t i = 0; i < v.size(); i++) {new(data + i) T(v[i]); // 采用 new 的原地构造, 因为有的类型并没有重载 ‘=’ 运算符}_Finish = data + __size;_M_pos = data + v.size();}vector(vector &&v) {__size = v.__size;data = v.data;_M_pos = v._M_pos;_Finish = v._Finish;v.data = v._M_pos = v._Finish = v._M_pos = nullptr;}~vector() {if (data == nullptr) return ;// free(data); 存储的数据可能都有对应的析构方法,而使用free不会调用析构方法for (size_t i = 0; i < __size; i++) {data[i].~T();}free(data);return ;}iterator begin() const { return data; }iterator end() const { return _M_pos; }T &operator[](size_t ind) const { return data[ind]; }size_t size() const { return _M_pos - data; }void push_back(const T &obj) {// 如果数据到最后,但是没有成功扩展内存就报错退出if (_M_pos == _Finish && !__expand()) {std::cout << "expand failed!" << std::endl;return ;}new(_M_pos) T(obj); // 调用new的原地构造_M_pos += 1;return ;}private:size_t __size;T *data;T *_M_pos, *_Finish;bool __expand() {// 重新扩展内存T *p = (T *)realloc(data, sizeof(T) * __size * 2);if (p == nullptr) return false;size_t offset = _M_pos - data;__size *= 2;data = p;_M_pos = data + offset;_Finish = data + __size;return true;}
};// 三点取中法
template<typename T, typename Func_T>
T __median(T first, T medium, T last, Func_T cmp) {if (cmp(medium, first)) std::swap(medium, first);if (cmp(last, medium)) std::swap(medium, last);return medium;
}// 重载两个参数的sort
template<typename iterator>
void sort(iterator begin, iterator end) {sort(begin, end, std::less<decltype(*(begin))>());return ;
}// 三个参数的sort
template<typename iterator, typename _Compare>
void sort(iterator begin, iterator end, _Compare cmp) {if (end - begin < 2) return;iterator x = begin, y = end - 1;typename std::remove_reference<decltype(*begin)>::type z = __median(*x, *(begin + (end - begin) / 2), *y, cmp);do {while (cmp(*x, z)) x++;while (cmp(z, *y)) y--;if (x <= y) {std::swap(*x, *y);++x, --y;}} while (x <= y);++y;my::sort(begin, y, cmp);my::sort(x, end, cmp);return ;
}template<typename T>
void output(T *begin, T *end) {std::cout << "arr : ";for (T *p = begin; p < end; ++p) {std::cout << *p << " ";}std::cout << std::endl;
}} // end of namespace myint main() {#define MAX_N 10srand(time(0));my::vector<int> v1;for (int i = 0; i < MAX_N; ++i) {v1.push_back(rand() % 100);}for (auto x : v1) std::cout << x << " "; std::cout << std::endl;my::sort(v1.begin(), v1.end());for (auto x : v1) std::cout << x << " "; std::cout << std::endl;std::cout << "===========================" << std::endl;my::vector<float> v2;for (int i = 0; i < MAX_N; ++i) {v2.push_back(rand() % 10000 * 1.0 / 100.0);}for (auto x : v2) std::cout << x << " "; std::cout << std::endl;my::sort(v2.begin(), v2.end());for (auto x : v2) std::cout << x << " "; std::cout << std::endl;std::cout << "===========================" << std::endl;my::vector<my::vector<int>> v3;for (int i = 0; i < 3; ++i) {v3.push_back(my::vector<int> ());for (int j = 0; j < 4; ++j) {v3[i].push_back(0);}}my::vector<my::vector<int>> v4(v3);v3[1][2] = 123;for (int i = 0; i < 3; ++i) {for (int j = 0; j < 4; ++j) {std::cout << v3[i][j] << " ";}std::cout << std::endl;}std::cout << "-----------------------" << std::endl;for (int i = 0; i < 3; ++i) {for (int j = 0; j < 4; ++j) {std::cout << v4[i][j] << " ";}std::cout << std::endl;}std::cout << "===========================" << std::endl;return 0;
}
相关文章:
C++迈向精通:vector复现与sort复现
vector复现 思考过程 对于vector考虑如下几点: 底层数据结构算法实现方式对外表现形式 这里底层的数据结构采用了顺序表,当然,原版STL中的vector也是采用的顺序表。 算法实现的方式放在代码中去设计 对外表现形式是数组,因此需…...

【头歌】计算机网络DHCP服务器配置第二关access口配置答案
头歌计算机网络DHCP服务器配置第二关access口配置操作步骤 任务描述 本关任务:创建 vlan ,并且将与 pc 机相连接口划分 vlan 。 操作要求 在第一关的拓扑图的基础上,配置交换机,具体要求如下: 1、在特权模式下进入 vla…...

Python机器学习 Tensorflow + keras 实现CNN
一、实验目的 1. 了解SkLearn Tensorlow使用方法 2. 了解SkLearn keras使用方法 二、实验工具: 1. SkLearn 三、实验内容 (贴上源码及结果) 使用Tensorflow对半环形数据集分 #encoding:utf-8import numpy as npfrom sklearn.datasets i…...
基于事件的架构工作机制和相关产品
基于事件的架构 基于事件的架构可否这样理解,每个事件相当于传统API的一次函数调用请求,比如Add(123,456)。区别在于,基于事件的架构只是把这个请求发出,并不急于得到结果,而是等合适的子系统处理完这个请求ÿ…...

OSINT 与心理学:通过开源情报进行剖析和行为分析
在不断发展的心理学领域,人们越来越认识到通过应用开源情报 (OSINT) 方法取得进步的潜力。OSINT 主要以其在安全和情报领域的应用而闻名,并且越来越多地展示其在心理分析和行为分析方面的潜力。本文探讨了 OSINT 和心理学的迷人交叉点,研究如…...
yarn 设置淘宝镜像配置
为了提升在中国大陆地区的下载速度,你可以将Yarn的包仓库配置为淘宝镜像。最新的推荐做法是使用npmmirror.com作为镜像源,替代旧的npm.taobao.org。以下是设置Yarn使用淘宝镜像(npmmirror.com)的步骤: 查询当前镜像配置…...
debian 常用命令
Debian 是一个广泛使用的 Linux 发行版,这里列出了一些常用的 Debian 命令,适用于系统管理和日常使用: ### 文件与目录操作 1. **ls** - 列出目录内容: bash ls ls -l # 长格式显示 ls -a # 显示所有文件ÿ…...

流水账(CPU设计实战)——lab3
Lab3 Rewrite V1.0 版本控制 版本描述V0V1.0相对V0变化: 修改了文件名,各阶段以_stage结尾(因为if是关键词,所以module名不能叫if,遂改为if_stage,为了统一命名,将所有module后缀加上_stage&a…...
k8s集群配置普通用户权限
集群管理员:负责管理 Kubernetes 集群的用户,拥有最高权限,可以对集群中的资源进行任何操作。 开发者:在 Kubernetes 集群中部署和管理自己的应用,可能有限制的权限,仅能管理特定的命名空间或资源。 第三…...

clickhouse——clickhouse单节点部署及基础命令介绍
clickhouse支持运行在主流的64位CPU架构的linux操作系统之上,可以通过源码编译,预编译压缩包,docker镜像和rpm等多种方式进行安装。 一、单节点部署 1、安装curl工具 yum install -y curl 2、添加clickhouse的yum镜像 curl -s https://pack…...
MATLAB基础应用精讲-【数模应用】价格敏感度PSM分析(附python代码实现)
目录 前言 算法原理 什么是价格敏感度分析? 原理 示例 PSM用途...

数据驱动的UI艺术:智能设计的视觉盛宴
数据驱动的UI艺术:智能设计的视觉盛宴 引言 在当今这个数据泛滥的时代,大数据不仅仅是一种技术手段,它更是一种艺术形式。当大数据遇上UI设计,两者的结合便催生了一种全新的艺术形式——数据驱动的UI艺术。本文将探讨如何将数据…...

栈的特性及代码实现(C语言)
目录 栈的定义 栈的结构选取 链式储存结构和顺序栈储存结构的差异 栈的代码实现 "stack.h" "stack.c" 总结 栈的定义 栈:栈是限定仅在表尾进行插入和删除操作的线性表。 我们把运行插入的和删除的一段叫做栈顶(TOPÿ…...

防火墙如何端口映射?
防火墙端口映射(Firewall Port Mapping)是一种网络技术,通过对防火墙配置进行调整,允许外部网络用户访问内部网络中的指定端口。该技术使得外部用户可以通过公共网络访问内部网络中的特定服务或应用程序,从而实现远程访…...

咖啡看书休闲时光404错误页面源码
源码介绍 咖啡看书休闲时光404错误页面源码,源码由HTMLCSSJS组成,记事本打开源码文件可以进行内容文字之类的修改,双击html文件可以本地运行效果,也可以上传到服务器里面,重定向这个界面 源码效果 源码下载 咖啡看书…...
中央事件bus
中央事件bus的使用 使用场景:当需要传递给多个组件的时候例如父组件->子组件->孙组件,甚至还得传递到更深的组件的时候中央事件就起到了作用,不需要一直传递。bus其实就是一个发布订阅模式,利用vue的自定义事件机制 // 事…...

中国上市企业行业异质性数据分析
数据简介:企业行业异质性数据是指不同行业的企业在运营、管理、财务等方面的差异性数据。这些数据可以反映不同行业企业的特点、优势和劣势,以及行业间的异质性对企业经营和投资的影响。通过对企业行业异质性数据的分析,投资者可以更好地了解…...

【全开源】防伪溯源一体化管理系统源码(FastAdmin+ThinkPHP和Uniapp)
一款基于FastAdminThinkPHP和Uniapp进行开发的多平台(微信小程序、H5网页)溯源、防伪、管理一体化独立系统,拥有强大的防伪码和溯源码双码生成功能(内置多种生成规则)、批量大量导出防伪和溯源码码数据、支持代理商管理…...

鸿蒙ArkUI-X跨语言调用说明:【平台桥接(@arkui-x.bridge)】
平台桥接(arkui-x.bridge) 简介 平台桥接用于客户端(ArkUI)和平台(Android或iOS)之间传递消息,即用于ArkUI与平台双向数据传递、ArkUI侧调用平台的方法、平台调用ArkUI侧的方法。 以Android平台为例,Ark…...
ts面试题: 面试题2
31. 计算字符串长度 // 计算字符串的长度,类似于 String#length 。答案 type test Str1<"abc123">; type Str1<T extends string, L extends any[] []> T extends ${infer f}${infer b} ? Str1<b, [...L, f]> : L[length];32. 接…...
[特殊字符] 智能合约中的数据是如何在区块链中保持一致的?
🧠 智能合约中的数据是如何在区块链中保持一致的? 为什么所有区块链节点都能得出相同结果?合约调用这么复杂,状态真能保持一致吗?本篇带你从底层视角理解“状态一致性”的真相。 一、智能合约的数据存储在哪里…...

STM32F4基本定时器使用和原理详解
STM32F4基本定时器使用和原理详解 前言如何确定定时器挂载在哪条时钟线上配置及使用方法参数配置PrescalerCounter ModeCounter Periodauto-reload preloadTrigger Event Selection 中断配置生成的代码及使用方法初始化代码基本定时器触发DCA或者ADC的代码讲解中断代码定时启动…...

2021-03-15 iview一些问题
1.iview 在使用tree组件时,发现没有set类的方法,只有get,那么要改变tree值,只能遍历treeData,递归修改treeData的checked,发现无法更改,原因在于check模式下,子元素的勾选状态跟父节…...

学习STC51单片机31(芯片为STC89C52RCRC)OLED显示屏1
每日一言 生活的美好,总是藏在那些你咬牙坚持的日子里。 硬件:OLED 以后要用到OLED的时候找到这个文件 OLED的设备地址 SSD1306"SSD" 是品牌缩写,"1306" 是产品编号。 驱动 OLED 屏幕的 IIC 总线数据传输格式 示意图 …...
【git】把本地更改提交远程新分支feature_g
创建并切换新分支 git checkout -b feature_g 添加并提交更改 git add . git commit -m “实现图片上传功能” 推送到远程 git push -u origin feature_g...

在WSL2的Ubuntu镜像中安装Docker
Docker官网链接: https://docs.docker.com/engine/install/ubuntu/ 1、运行以下命令卸载所有冲突的软件包: for pkg in docker.io docker-doc docker-compose docker-compose-v2 podman-docker containerd runc; do sudo apt-get remove $pkg; done2、设置Docker…...

dify打造数据可视化图表
一、概述 在日常工作和学习中,我们经常需要和数据打交道。无论是分析报告、项目展示,还是简单的数据洞察,一个清晰直观的图表,往往能胜过千言万语。 一款能让数据可视化变得超级简单的 MCP Server,由蚂蚁集团 AntV 团队…...

接口自动化测试:HttpRunner基础
相关文档 HttpRunner V3.x中文文档 HttpRunner 用户指南 使用HttpRunner 3.x实现接口自动化测试 HttpRunner介绍 HttpRunner 是一个开源的 API 测试工具,支持 HTTP(S)/HTTP2/WebSocket/RPC 等网络协议,涵盖接口测试、性能测试、数字体验监测等测试类型…...
比较数据迁移后MySQL数据库和OceanBase数据仓库中的表
设计一个MySQL数据库和OceanBase数据仓库的表数据比较的详细程序流程,两张表是相同的结构,都有整型主键id字段,需要每次从数据库分批取得2000条数据,用于比较,比较操作的同时可以再取2000条数据,等上一次比较完成之后,开始比较,直到比较完所有的数据。比较操作需要比较…...
Linux系统部署KES
1、安装准备 1.版本说明V008R006C009B0014 V008:是version产品的大版本。 R006:是release产品特性版本。 C009:是通用版 B0014:是build开发过程中的构建版本2.硬件要求 #安全版和企业版 内存:1GB 以上 硬盘…...