STL算法之基本算法<stl_algobase.h>

        STL标准规格中没哟区分基本算法或复杂算法,然后SGI却把常用的一些算法定义于<stl_algobase.h>之中,其他算法定义于<stl_algo.h>之中。以下一一列举这些基本算法。

目录

运用实例

equal,fill,fill_n,iter_swap, lexicographical_compare,max,min,mismatch,swap

equal

fill

fill_n

iter_swap

lexicographical_compare

max

min

mismatch

swap


运用实例

        我们首先来看基本算法的一些运行实例

#include <algorithm>
#include <vector>
#include <functional>
#include <iostream>
#include <iterator>
#include <string>
using namespace std;template <class T> 
struct display {void operator() (const T&x) {cout << x << ' ';}
};int main() {int ia[9] = {0,1,2,3,4,5,6,7,8};vector<int> iv1(ia, ia + 5); // 0,1,2,3,4vector<int> iv2(ia, ia+9);   // 0,1,2,3,4,5,6,7,8cout << *(mismatch(iv1.begin(), iv1.end(), iv2.begin())).first << endl; // ?cout << *(mismatch(iv1.begin(), iv1.end(), iv2.begin())).second << endl; // 5cout << equal(iv1.begin(), iv1.end(), iv2.begin()) << endl; // 1cout << equal(iv1.begin(), iv1.end(), iv2.begin() + 2) << endl; //0, false// 0,1,2,3,4 不等于 2,3,4,5,6fill(iv1.begin(), iv1.end(), 9);for_each(iv1.begin(), iv1.end(), display<int>()); // 9 9 9 9 9cout << endl;fill_n(iv1.begin(), 3, 7);for_each(iv1.begin(), iv1.end(), display<int>()); // 7 7 7 9 9cout << endl;vector<int>::iterator ite1 = iv1.begin();vector<int>::iterator ite2 = ite1;advance(ite2, 3);  // plus three times?cout << *ite1 << ' ' << *ite2 << endl; // 7 9iter_swap(ite1, ite2);cout << *ite1 << ' ' << *ite2 << endl; // 9 7for_each(iv1.begin(), iv1.end(), display<int>()); // 9 7 7 7 9cout << endl;cout << max(*ite1, *ite2) << endl; // 9cout << min(*ite1, *ite2) << endl; // 7swap(*iv1.begin(), *iv2.begin());for_each(iv1.begin(), iv1.end(), display<int>()); // 0 7 7 7 9cout << endl;for_each(iv2.begin(), iv2.end(), display<int>()); // 9 1 2 3 4 5 6 7 8cout << endl;//准备两个字符串数组string stra1[] = {"Jamie", "JJHou", "Jason"};string stra2[] = {"Jamie", "JJhou", "Jerry"};cout << lexicographical_compare(stra1, stra1 + 3, stra2, stra2 + 3) << endl;     // 1 (stra1 小于stra2)cout << lexicographical_compare(stra1, stra1+3, stra2, stra2+3, greater<string>()) << endl;     // 0 (stra1 不大于 stra2)return 0;
}

equal,fill,fill_n,iter_swap, lexicographical_compare,max,min,mismatch,swap

        这一节对运用实例中实际测试的算法进行说明。

equal

        如果两个序列在[first, last)区间内相等,equal()返回true。如果第二序列的元素比较多,多出来的元素不予考虑。因此,如果,我们希望保证两个序列完全相等,必选先判断其元素个数是否相同:

(vec1.size() == vec2.size() && equal(vec1.begin(), vec1.end(), vec2.begin())

抑或使用容器所提供的quality操作符,例如vec1 == vec2.如果第二序列的元素比第一序列少,这个算法内部进行迭代行为时,会超越序列的尾端,造成不可预测的结果。

        源码如下所示:

template <class InputIterator1, class InputIterator2>
inline bool equal(InputIterator1 first1, InputIterator1 last, InputIterator2 first2)
{for (;first1 != last1; ++first1, ++first2) {if (*first1 != *first2) return false;}return true;
}template <class InputIterator1, class InputIterator2, class BinaryPredicate>
inline bool equal(InputIterator1 first1, InputIterator1 last, InputIterator2 first2, BinaryPredicate binary_pred)
{for (;first1 != last1; ++first1, ++first2) {if (!binary_pred(*first1, *first2)) return false;}return true;
}

fill

        将[first, last)内的所有元素该填新值。

template<class ForwardIterator, class T>
void fill(ForwardIterator first, ForwardIterator last, const T& value) {for(; first != last; ++first) {*first = value;}
}

fill_n

        将[first,first+n)改填为新值,返回的迭代器指向填入的最后一个元素的下一位置。

template<class OutputIterator, class Size, class T>
OutputIterator fill_n(OutputIterator first, Size n, const T& value) {for (;n > 0; --n; ++first) {*first = value;}return first;
}

如果n超越了容器的现有大小,会造成什么结果呢?我们可以很容易从fill_n()的源代码知道,如果每次迭代进行的是assignment操作,是一种覆写操作;即当迭代器已经达到end后,对齐提领(dereference)操作是未定义的,可能会产生不可预期的结果。解决办法之一是,利用inserter()产生一个具有插入(insert)而非覆写(overwrite)能力的迭代器。inserter()可产生一个用来修饰迭代器的配接器(iterator adaper),用法如下

int ia[3] = {0, 1, 2};
vector<int> iv{ia, ia + 3};
fill_n(inserter(iv, iv.begin()), 5, 7);   // 7 7 7 7 7 0 1 2

inserter(iv, iv.begin())和书中的inserter(iv.begin())略有差异

iter_swap

        将两个ForwarIterators所指的对象对调。如下图:

template<class ForwardIterator1, class ForwardIterator2>
inline void iter_swap(ForwardIterator1 a, ForwardIterator2 b) {__iter_swap(a, b, value_type(a));
}template<class ForwardIterator1, class ForwardIterator2, T*> void __iter_swap(ForwardIterator1 a, ForwardIterator2 b, T*) {T tmp = *a;*a = *b;*b = tmp;
}

        Iter_swap()是“迭代器之value type”派上用场的一个好例子。是的,该函数必须知道迭代器的value type,才能够据此声明一个对象,用来暂时存放迭代器所指对象。为此,上述源代码特别设计了一个双层构造,第一层调用第二层,并多出了一个额外参数value_type(a)。这么一来,第二层就有value type可以用了。乍见之下我们可能会对这个额外参数在调用端和接受端的型别感到讶异,调用端是value_type(a),接受端是T*。只要找出iterator::value_type()的定义瞧瞧,就一目了然了:

template <class Iterator>
inline typename iterator_traits<Iterator>::value_type* value_type(const Iterator&) {return static_cast<typename iterator_traits<Iterator>::value_type*>(0);
}

        这种双层结构在SGI STL中十分普遍,其实可以换一种写法

template<class ForwardIterator1, class ForwardIterator2>
inline void iter_swap(ForwardIterator1 a, ForwardIterator2 b) {typename iterator_traits<ForwardIterator1>::value_type tmp = *a;*a = *b;*b = tmp;
}

lexicographical_compare

        以字典排列方式对两个序列[first1,last1)和[first2,last2)进行比较。比较操作针对两个序列中对应位置上的元素进行,并持续直到(1)某一组对象元素彼此不相等;(2)同时到达了last1和last2(当两个序列的大小相同);(3)到达last1或last2(当两序列大小不同)

        当这个函数在对应位置上发现第一组不相等的元素时,有下列几种可能:

  • 如果第一个序列的元素较小,返回true,否则返回false
  • 如果达到last1而尚未达到last2,返回true
  • 如果达到last2而尚未达到last1, 返回false
  • 如果同时达到last1和last2,返回false

举个例子

string stra1[] = {"Jamie", "JJHou", "Jason"};
string stra2[] = {"Jamie", "JJhou", "Jason"};

   这个算法面对第一组元素对,判断其为相等,但面对第二

组元素对,判断其为不等。就字符串而言JJHou下雨JJhou,因为H在字典排列次序上小于h。于是这个算法再打第二组元素对停了下来。比较结果为true。

        第二个版本允许指定一个反函数comp作为比较操作之用,取代元素型别所提供的less-than操作符。

template<class InputIterator1, class InputIterator2>
bool lexicographical_compare(InputIterator1 first1, InputIterator1 last1InputIterator2 first2, InputIterator2 last2) {for (; first1!=last1 && first2!=last2;++first1;++first2) {if (*first1 < *first2) {return true;}if (*first2 < *first1) {return false;}}return first1 == last1 && first2 != last2;
}template<class InputIterator1, class InputIterator2, class Compare>
bool lexicographical_compare(InputIterator1 first1, InputIterator1 last1InputIterator2 first2, InputIterator2 last2, Compare comp) {for (; first1!=last1 && first2!=last2;++first1;++first2) {if ( comp(*first1, *first2)) {return true;}if ( comp(*first2, *first1)) {return false;}}return first1 == last1 && first2 != last2;
}

        为了增进效率,SGI还设计了一个特化版本,用于原生指针const unsigned char*:

inline bool lexicographical_compare(const unsigned char * first1, const char* last1, const char* first2, const char* last2) {const size_t len1 = last1 - first1;const size_t len2 = last2 - first2;const int result = memcmp(first1, first2, min(len1, len2));return result != 0 ? (result < 0) : len1 < len2;
}

max

        取两个对象中的较大值。有两个版本,版本一使用对象类型T所提供的greater-than操作符来判断大小,版本二使用仿函数comp判断大小。

template<class T>
inline const T& max(const T&a, const T&b) {return a < b ? b : a;
}template<class T, class comp>
inline const T& max(const T&a, const T&b, Compare comp) {return comp(a, b) ? b : a;
}

min

        取两个对象的较小值。

template<class T>
inline const T& min(const T&a, const T&b) {return b < a ? b : a;
}template<class T, class comp>
inline const T& min(const T&a, const T&b, Compare comp) {return comp(b, a) ? b : a;
}

mismatch

        用来平行比较两个序列,指出两者之间的第一个不匹配点。返回一对迭代器,分别指向两徐磊中不匹配的点。如下图所示

代码如下:

template<class InputIterator1, class InputIterator2>
pair<InputIterator1, InputIterator2> mismatch(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2) {while(first1 != last1 && *first1 == *first2) {++first1;++first2;}return pair<InputIterator1, InputIterator2>(first1, first2);
}template<class InputIterator1, class InputIterator2, class BinaryPredicate>
pair<InputIterator1, InputIterator2> mismatch(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, BinaryPredicate binary_pred) {while(first1 != last1 && binary_pred(*first1, *first2)) {++first1;++first2;}return pair<InputIterator1, InputIterator2>(first1, first2);
}

swap

        该函数用来交换两个对象

template <class T> 
inline void swap(T&a, T&b) {T tmp = a;a = b;b = tmp;
}

参考文档《STL源码剖析》---侯捷

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/480244.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

dns 服务器简单介绍

dns 服务器分类&#xff1a; 根域名服务器顶级域名服务器权威域名服务器本地域名服务器 dns 的查询过程 国内优秀公共域名 腾讯&#xff1a;DNSPod-免费智能DNS解析服务商-电信_网通_教育网,智能DNS-烟台帝思普网络科技有限公司 119.29.29.29 和 182.254.118.118 阿里&#xf…

AI智算-正式上架GPU资源监控概览 Grafana Dashboard

下载链接 https://grafana.com/grafana/dashboards/22424-ai-gpu-20241127/

CAN详解

CAN简介 • CAN 总线&#xff08; Controller Area Network Bus &#xff09;控制器局域网总线 • CAN 总线是由 BOSCH 公司开发的一种简洁易用、传输速度快、易扩展、可靠性高的串行通信总线&#xff0c;广泛应用于汽车、嵌入式、工业控制等领域 • CAN 总线特征&#xff1a; …

透视投影(Perspective projection)与等距圆柱投影(Equirectangular projection)

一、透视投影 1.方法概述 Perspective projection&#xff08;透视投影&#xff09;是一种模拟人眼观察三维空间物体时的视觉效果的投影方法。它通过模拟观察者从一个特定视点观察三维场景的方式来创建二维图像。在透视投影中&#xff0c;远处的物体看起来比近处的物体小&…

(四)Spring Boot学习——整合修改使用druid连接池

我的是使用springboot3的&#xff0c;对应的有整合的druid-spring-boot-3-starter的jar实现对springboot3的兼容。 <!--******************数据库相关配置************************--> <!-- 1.配置数据库相关的jar包,连接池使用druids上&#xff0c;并引入整合spring…

think php处理 异步 url 请求 记录

1、需求 某网站 需要 AI生成音乐&#xff0c;生成mp3文件的时候需要等待&#xff0c;需要程序中实时监听mp3文件是否生成 2、用的开发框架 为php 3、文件结构 配置路由设置 Route::group(/music, function () {Route::post(/musicLyrics, AiMusic/musicLyrics);//Ai生成歌词流式…

Linux八股积累与笔记

1、iptables 是一个用于配置Linux内核防火墙规则的工具。四表五链&#xff1a;在iptables中&#xff0c;有四个表&#xff08;tables&#xff09;和五个链&#xff08;chains&#xff09;&#xff0c;用于管理不同类型的数据包过滤规则。如下&#xff1a; 表&#xff08;Tabl…

乐鑫发布 esp-iot-solution v2.0 版本

今天&#xff0c;乐鑫很高兴地宣布&#xff0c;esp-iot-solution v2.0 版本已经发布&#xff0c;release/v2.0 分支下的正式版本组件将为用户提供为期两年的 Bugfix 维护&#xff08;直到 2027.01.25 ESP-IDF v5.3 EOL&#xff09;。该版本将物联网开发中常用的功能进行了分类整…

【爬虫框架:feapder,管理系统 feaplat】

github&#xff1a;https://github.com/Boris-code/feapder 爬虫管理系统 feaplat&#xff1a;http://feapder.com/#/feapder_platform/feaplat 爬虫在线工具库 &#xff1a;http://www.spidertools.cn &#xff1a;https://www.kgtools.cn/1、feapder 简介 对于学习 Python…

uni-app 蓝牙开发

一. 前言 Uni-App 是一个使用 Vue.js 开发&#xff08;所有&#xff09;前端应用的框架&#xff0c;能够编译到 iOS、Android、快应用以及各种小程序等多个平台。因此&#xff0c;如果你需要快速开发一款跨平台的应用&#xff0c;比如在 H5、小程序、iOS、Android 等多个平台上…

C语言——海龟作图(对之前所有内容复习)

一.问题描述 海龟作图 设想有一只机械海龟&#xff0c;他在C程序控制下在屋里四处爬行。海龟拿了一只笔&#xff0c;这支笔或者朝上&#xff0c;或者朝下。当笔朝下时&#xff0c;海龟用笔画下自己的移动轨迹&#xff1b;当笔朝上时&#xff0c;海龟在移动过程中什么也不画。 …

【Maven】继承和聚合

5. Maven的继承和聚合 5.1 什么是继承 Maven 的依赖传递机制可以一定程度上简化 POM 的配置&#xff0c;但这仅限于存在依赖关系的项目或模块中。当一个项目的多个模块都依赖于相同 jar 包的相同版本&#xff0c;且这些模块之间不存在依赖关系&#xff0c;这就导致同一个依赖…

Android 性能优化:内存优化(理论篇)

内存作为App程序运行最重要的资源之一&#xff0c;需要运行过程中做到合理的资源分配与回收&#xff0c;不合理的内存占用轻则使得用户应用程序运行卡顿、ANR、黑屏&#xff0c;重则导致用户应用程序发生 OOM&#xff08;out of memory&#xff09;崩溃。喜马直播随着近些年的业…

技能之发布自己的依赖到npm上

目录 开始 解决 步骤一&#xff1a; 步骤二&#xff1a; 步骤三&#xff1a; 运用 一直以为自己的项目在github上有了&#xff08;之传了github&#xff09;就可以进行npm install下载&#xff0c;有没有和我一样萌萌的同学。没事&#xff0c;萌萌乎乎的不犯罪。 偶然的机…

【选择排序和交换排序】直接选择排序、堆排序、冒泡排序、快速排序

【选择排序和交换排序】直接选择排序、堆排序、冒泡排序、快速排序 1. 选择排序1.1 直接选择排序1.1.1详细过程1.1.2 代码实现1.1.3 复杂度和稳定性 1.2 堆排序 2. 交换排序2.1 冒泡排序2.1.1 代码实现2.1.2 复杂度和稳定性 2.2 快速排序——挖坑法2.2.1详细过程2.2.2 代码实现…

DI依赖注入详解

DI依赖注入 声明了一个成员变量&#xff08;对象&#xff09;之后&#xff0c;在该对象上面加上注解AutoWired注解&#xff0c;那么在程序运行时&#xff0c;该对象自动在IOC容器中寻找对应的bean对象&#xff0c;并且将其赋值给成员变量&#xff0c;完成依赖注入。 AutoWire…

51c大模型~合集79

我自己的原文哦~ https://blog.51cto.com/whaosoft/12661268 #还是回谷歌好 创业一年半&#xff0c;胖了30斤&#xff0c;AI大佬感叹 回到大厂&#xff0c;和老领导重聚。 「由于工作强度和不健康的生活方式&#xff0c;我已胖了 15 公斤。」 本周一&#xff0c;知名 AI 学…

工业AI质检 AI质检智能系统 尤劲恩(上海)信息科技有限公司

来的现代化工厂&#xff0c;将逐步被无人化车间取代&#xff0c;无人工厂除了产线自动化&#xff0c;其无人质检将是绕不开的话题。尤劲恩致力于帮助工业制造领域上下游工厂减员增效、提高品质效率&#xff0c;真正实现无人质检IQC/IPQC/OQC的在线质检系统。分析生产环节真实品…

【CSS in Depth 2 精译_062】第 10 章 CSS 中的容器查询(@container)概述 + 10.1 容器查询的一个简单示例

当前内容所在位置&#xff08;可进入专栏查看其他译好的章节内容&#xff09; 【第十章 CSS 容器查询】 ✔️ 10.1 容器查询的一个简单示例 ✔️ 10.1.1 容器尺寸查询的用法 ✔️ 10.2 深入理解容器10.3 与容器相关的单位10.4 容器样式查询的用法10.5 本章小结 文章目录 第 10…

ELK(Elasticsearch + logstash + kibana + Filebeat + Kafka + Zookeeper)日志分析系统

文章目录 前言架构软件包下载 一、准备工作1. Linux 网络设置2. 配置hosts文件3. 配置免密登录4. 设置 NTP 时钟同步5. 关闭防火墙6. 关闭交换分区7. 调整内存映射区域数限制8. 调整文件、进程、内存资源限制 二、JDK 安装1. 解压软件2. 配置环境变量3. 验证软件 三、安装 Elas…