C++ 的常见算法 之二

C++ 的常见算法 之二

  • 划分序列
    • partition
    • stable_partition
  • 排序
    • sort
    • nth_element
  • 二分查找
    • binary_search

划分序列

partition

重新排列 [first,last) 范围内的元素，使得 pred 返回 true 的所有元素先于所有返回 false 的元素。迭代器返回指向第二组的第一个元素的点。

每个组内的相对顺序不一定与调用之前相同。

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

bool greater50 (int i) { return (i > 50); }
void print_val(int val) { cout << val << ' '; }
int main () {
  vector<int> myvector = {30, 40, 80, 12, 19, 20, 55, 72};

  vector<int>::iterator bound;
  bound = partition (myvector.begin(), myvector.end(), greater50);

  // print out content:
  cout << "greater than 50:";
  for (vector<int>::iterator it=myvector.begin(); it!=bound; ++it)
    cout << ' ' << *it;
  cout << '\n';

  cout << "less than 50:";
  for (vector<int>::iterator it=bound; it!=myvector.end(); ++it)
    cout << ' ' << *it;
  cout << '\n';

  for_each (myvector.begin(), myvector.end(), print_val);
  cout << endl;
  
  return 0;
}

结果屏幕输出

greater than 50: 72 55 80
less than 50: 12 19 20 40 30
72 55 80 12 19 20 40 30

stable_partition

重新排列 [first,last) 范围内的元素，pred 返回 true 的所有元素排在返回 false 的所有元素之前, 但与partition函数不同，这个函数保留每个组内元素的相对顺序。

这通常使用内部临时缓冲区来实现。

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

bool greater30 (int i) { return (i > 30); }
void print_element(int val) { cout << val << " ";}

int main () {
  vector<int> myvector = {4, 80, 5, 30, 6, 9, 50, 60, 1, 15};

  vector<int>::iterator bound;
  bound = stable_partition (myvector.begin(), myvector.end(), greater30);

  // print out content:
  cout << "greater than 30 elements:";
  for (vector<int>::iterator it=myvector.begin(); it!=bound; ++it)
    cout << ' ' << *it;
  cout << '\n';

  cout << "greater than or equal 30 elements: ";
  for (vector<int>::iterator it=bound; it!=myvector.end(); ++it)
    cout << ' ' << *it;
  cout << '\n';

  cout << "all elements: ";
  for_each (myvector.begin(), myvector.end(), print_element);
  cout << '\n';

  return 0;
}

结果屏幕输出

greater than 30 elements: 80 50 60
greater than or equal 30 elements:  4 5 30 6 9 1 15
all elements: 80 50 60 4 5 30 6 9 1 15

排序

sort

将范围 [first,last) 中的元素按升序排序。
第一个版本使用operator< 来比较元素，第二个版本使用comp 来比较元素。

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>

using namespace std;

struct personnel {
	string  name;
	int     age;
};

bool myfunction (int i,int j) { return (i<j); }
void print_element(int val) { cout << val << " " ; }
void print_personnel(personnel person) { cout << person.name << " " << person.age << endl; }

struct sort_class {
   bool operator() (personnel lf, personnel lr) { return (lf.age < lr.age);}
} sort_object;

int main () {
  vector<int> myvector = {32,71,12,45,26,80,53,33}; 
  vector<personnel> persons = {
	  {"John", 30},
	  {"Allison", 25},		  
	  {"Sam", 29},		  
	  {"Alice", 39},		  
  };
  
  // using default comparison (operator <):
  sort (myvector.begin(), myvector.begin()+4);           //(12 32 45 71)26 80 53 33
  sort (myvector.begin()+4, myvector.end(), myfunction); // 12 32 45 71(26 33 53 80)

  // print out content:
  cout << "myvector contains:" << endl;
  for_each (myvector.begin(), myvector.end(), print_element);
  cout << '\n';

  // using object as comp
  sort (persons.begin(), persons.end(), sort_object); 
  // print out content:
  cout << "sorted personnel:" << endl;
  for_each (persons.begin(), persons.end(), print_personnel);
  cout << '\n';
  return 0;
}

结果屏幕·输出

myvector contains:
12 32 45 71 26 33 53 80
sorted personnel:
Allison 25
Sam 29
John 30
Alice 39

nth_element

重新排序 [first,last) 范围内的元素，得到的序列是，第 n 个位置的元素位置是，完全排序后，该元素所在的位置。

在结果序列中，其他元素没有任何特定的顺序，第 n 个元素前面的所有元素，都小于或对于该元素，它后面的元素都大于或等于它。

该算法有两个版本，第一个版本使用operator< 来比较元素，第二个版本使用comp来比较元素。

#include <iostream>  
#include <algorithm> 
#include <vector> 

using namespace std;

bool myfunction (int i,int j) { return (i<j); }
void print_element(int val)  { cout << val << " "; }

struct personnel {
	string name;
	int  age;
};

struct personnel_comp {
	bool operator()(personnel lf, personnel lr) {return (lf.age < lr.age);};
} person_comp;

int main () {
  vector<int> myvector = {1, 9, 5, 8, 90, 30, 11};
  vector<int> v2 = {11, 19, 15, 18, 100, 40, 21, 130, 210};
  vector<personnel> v_persons = {
	  {"John", 30},
	  {"Allison", 25},		  
	  {"Sam", 29},		  
	  {"Alice", 39},
  };
  
  // using default comparison (operator <):
  nth_element (myvector.begin(), myvector.begin()+5, myvector.end());
  cout << "before sort:";
  for_each (myvector.begin(), myvector.end(), [](int val) ->void {cout << val << " ";});
  cout << endl;

  // using default comp
  nth_element (myvector.begin(), myvector.begin()+5, myvector.end());
 
  // print out content:
  cout << " after sort:";
  for_each (myvector.begin(), myvector.end(),  [](int val) ->void {cout << val << " ";});
  cout << '\n';

  // using function as comp
  cout << "before sort:" << endl;
  for_each (v2.begin(), v2.end(), [](int val) ->void {cout << val << " ";});
  cout << endl;
  nth_element (v2.begin(), v2.begin()+6, v2.end(), myfunction);
  cout << " after sort:";
  for_each (v2.begin(), v2.end(),  [](int val) ->void {cout << val << " ";});
  cout << '\n';

  // using function as comp
  cout << "before sort:" << endl;
  for_each (v_persons.begin(), v_persons.end(), [](personnel p) ->void {cout << p.name << " " << p.age << endl;});
  cout << endl;
  nth_element (v_persons.begin(), v_persons.begin()+3, v_persons.end(), person_comp);
  cout << " after sort:" << endl;
  for_each (v_persons.begin(), v_persons.end(),  [](personnel p) ->void {cout << p.name << " " << p.age << endl;});
  cout << '\n';

  return 0;
}

程序运行结果屏幕输出

before sort:9 1 5 8 11 30 90
 after sort:8 1 5 9 11 30 90
before sort:
11 19 15 18 100 40 21 130 210
 after sort:19 11 15 18 21 40 100 130 210
before sort:
John 30
Allison 25
Sam 29
Alice 39

 after sort:
Sam 29
Allison 25
John 30
Alice 39

二分查找

binary_search

如果范围 [first,last) 中的任何元素值等于 val，则返回 true，否则返回 false。

该算法支持两种版本。

  • 第一个版本，使用operator< 来比较元素，
  • 第二个版本，使用comp 来比较元素。如果 (!(a<b) && !(b<a)) 或 if (!comp(a,b) && !comp(b,a))，则 a 和 b 两个元素被视为相同。

范围中的元素应已根据相同的标准（operator< 或 comp）进行排序，或者至少根据 val 进行分区。

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

bool myfunction (int i,int j) { return (i<j); }

struct personnel {
	string name;
	int  age;
};

struct personnel_comp {
	bool operator()(personnel lf, personnel lr) {return (lf.name < lr.name);};
} person_comp;

int main () {
  std::vector<int> v = {1,2,40,30,3,4,5,20,10}; 
  vector<personnel> v_persons = {
	  {"John", 30},
	  {"Allison", 25},		  
	  {"Sam", 29},		  
	  {"Alice", 39},
  };

  // using default comparison:
  sort (v.begin(), v.end());
  cout << " After sort: " << endl;
  for_each (v.begin(), v.end(), [](int v)->void{cout << v << " ";});
  cout << endl;
  
  cout << "looking for a 3... ";
  if (binary_search (v.begin(), v.end(), 3))
    cout << "found!\n"; 
  else cout << "not found.\n";

  // using myfunction as comp:
  sort (v.begin(), v.end(), myfunction);
  cout << "looking for a 15... ";
  if (binary_search (v.begin(), v.end(), 15, myfunction))
    cout << "found!\n"; 
  else cout << "not found.\n";

  // using personnel_comp as comp:
  cout << " Before sort: " << endl;
  for_each (v_persons.begin(), v_persons.end(), [](personnel v)->void{cout << v.name << " " << v.age << endl;});
  
  sort (v_persons.begin(), v_persons.end(), person_comp);
  cout << " After sort: " << endl;
  for_each (v_persons.begin(), v_persons.end(), [](personnel v)->void{cout << v.name << " " << v.age << endl;});
  cout << endl;

  cout << "looking for John... ";
  personnel person = {"John", 30}; 
  if (binary_search (v_persons.begin(), v_persons.end(), person, person_comp))
    cout << "found!\n"; 
  else cout << "not found.\n";

  return 0;
}

上述代码运行后的屏幕输出

 After sort:
1 2 3 4 5 10 20 30 40
looking for a 3... found!
looking for a 15... not found.
 Before sort:
John 30
Allison 25
Sam 29
Alice 39
 After sort:
Alice 39
Allison 25
John 30
Sam 29

looking for John... found!

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

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

【MYSQL】如何解决 bin log 与 redo log 的一致性问题

【MYSQL】如何解决 bin log 与 redo log 的一致性问题

该问题问的其实就是redo log 的两阶段提交 为什么说redo log 具有崩溃恢复的能力 MySQL Server 层拥有的 bin log 只能用于归档&#xff0c;不足以实现崩溃恢复&#xff08;crash-safe&#xff09;&#xff0c;需要借助 InnoDB 引擎的 redo log 才能拥有崩溃恢复的能力。所谓崩…
阅读更多...
【AutoencoderKL】基于stable-diffusion-v1.4的vae对图像重构

【AutoencoderKL】基于stable-diffusion-v1.4的vae对图像重构

模型地址&#xff1a;https://huggingface.co/CompVis/stable-diffusion-v1-4/tree/main/vae 主要参考:Using-Stable-Diffusion-VAE-to-encode-satellite-images sd1.4 vae 下载到本地 from diffusers import AutoencoderKL from PIL import Image import torch import to…
阅读更多...
第二证券：资金抱团“高股息”，超三成A股年内创历史新低！

第二证券：资金抱团“高股息”，超三成A股年内创历史新低！

A股商场行情冰火两重天。 “预制菜榜首股”跌破发行价 7月8日&#xff0c;味知香盘中最低跌至19.26元/股&#xff0c;股价跌破发行价&#xff0c;并创前史新低。揭露资料显现&#xff0c;公司是集研发、生产、销售为一体的半成品菜企业&#xff0c;现在具有8大产品系列&#…
阅读更多...
九科bit-Worker RPA 内容学习

九科bit-Worker RPA 内容学习

简介&#xff1a; 什么是RPA&#xff1f; RPA&#xff08;Robotic Process Automation&#xff0c;机器人流程自动化&#xff09;本质上是一种“AI数字员工”&#xff0c;针对企业中存在的大批量、重复性、机械化人工操作&#xff0c;通过模拟人的工作流程使之实现自动化。 b…
阅读更多...
Java | Leetcode Java题解之第219题存在重复元素II

Java | Leetcode Java题解之第219题存在重复元素II

题目&#xff1a; 题解&#xff1a; class Solution {public boolean containsNearbyDuplicate(int[] nums, int k) {Set<Integer> set new HashSet<Integer>();int length nums.length;for (int i 0; i < length; i) {if (i > k) {set.remove(nums[i - …
阅读更多...
【小鸡案例】表单focus和blur事件用法

【小鸡案例】表单focus和blur事件用法

input中有2个属性&#xff0c;一个是focus获取焦点&#xff0c;一个是blur失去焦点。获取焦点就是我们点击输入框时输入框被选中&#xff1b;失去焦点即点击输入框以外的区域&#xff0c;今天就用这两种属性做一个点击输入框的动画效果。 先写个输入框&#xff0c;代码如下&am…
阅读更多...
【leetcode周赛记录——405】

【leetcode周赛记录——405】

405周赛记录 #1.leetcode100339_找出加密后的字符串2.leetcode100328_生成不含相邻零的二进制字符串3.leetcode100359_统计X和Y频数相等的子矩阵数量4.leetcode100350_最小代价构造字符串 刷了一段时间算法了&#xff0c;打打周赛看看什么水平了 #1.leetcode100339_找出加密后的…
阅读更多...
源码层面学习动态代理

源码层面学习动态代理

前言 在Java中&#xff0c;动态代理主要分为CGLIB动态代理和JDK动态代理&#xff0c;我们从Hutool的源码也可一窥这两者的使用方式和区别&#xff1b; CGLIB动态代理 JDK动态代理 使用场景 CglibInterceptor和JdkInterceptor都是Hutool提供的代理工具&#xff0c;用于在运行时…
阅读更多...
Redis存储原理与数据模型

Redis存储原理与数据模型

Redis存储结构 存储转换 redis-value编码 string int&#xff1a;字符串长度小于等于20切能转成整数raw&#xff1a;字符串长度大于44embstr&#xff1a;字符串长度小于等于44 list quicklist&#xff08;双向链表&#xff09;ziplist&#xff08;压缩链表&#xff09; hash …
阅读更多...
【智能算法改进】多策略改进的蜣螂优化算法

【智能算法改进】多策略改进的蜣螂优化算法

目录 1.算法原理2.改进点3.结果展示4.参考文献5.代码获取 1.算法原理 【智能算法】蜣螂优化算法&#xff08;DBO&#xff09;原理及实现 2.改进点 混沌反向学习初始化 采用 Pwlcm 分段混沌映射&#xff0c;由于 Pwlcm 在其定义区间上具有均匀的密度函数&#xff0c;在特定的…
阅读更多...
1.从入门到环境搭建及程序基础

1.从入门到环境搭建及程序基础

目录 1.1 C督学营开营 1 老师介绍 2 学习常见问题 3 如何学习课程 1.2 程序员职业发展方向 1 前端 2 后端 3 网络安全 1.3 Windows 的 CLion 开发环境安装 1 C 语言的由来 2 安装 MinGW 编译器 3 安装 CLion 开发环境 4 运行&试用 CLion 5 新建项目​ ​6 激…
阅读更多...
基于LangChain的RAG开发教程（二）

基于LangChain的RAG开发教程（二）

v1.0官方文档&#xff1a;https://python.langchain.com/v0.1/docs/get_started/introduction/ 最新文档&#xff1a;https://python.langchain.com/v0.2/docs/introduction/ LangChain是一个能够利用大语言模型&#xff08;LLM&#xff0c;Large Language Model&#xff09;能…
阅读更多...
家里猫咪浮毛太多怎么办？值得买的猫毛空气净化器推荐

家里猫咪浮毛太多怎么办？值得买的猫毛空气净化器推荐

作为一位拥有5年铲屎经验的铲屎官&#xff0c;我知道许多新手铲屎官可能听说过宠物空气净化器&#xff0c;但了解得不多。事实上&#xff0c;宠物空气净化器确实是养猫家庭必备的小家电之一。它的大面积进风口可以有效吸附空气中的微小浮毛和皮屑&#xff0c;专门的除臭技术能有…
阅读更多...
15个最佳WooCommerce商城网站及其主要功能

15个最佳WooCommerce商城网站及其主要功能

正在寻找的WooCommerce商城网站来激发灵感&#xff1f; 在动态的在线购物世界中&#xff0c;WooCommerce 就像企业的超级英雄。它帮助他们轻松创建强大而可靠的在线商店&#xff0c;并与WordPress顺畅协作。 从创新的产品展示到简化的结账流程&#xff0c;每个特色网站都拥有…
阅读更多...
Linux--线程（概念篇）

Linux--线程（概念篇）

目录 1.背景知识 再谈地址空间&#xff1a; 关于页表&#xff08;32bit机器上&#xff09; 2.线程的概念和Linux中线程的实现 概念部分&#xff1a; 代码部分&#xff1a; 问题&#xff1a; 3.关于线程的有点与缺点 4.进程VS线程 1.背景知识 再谈地址空间&#xff1a…
阅读更多...
【TB作品】51单片机 Proteus仿真00016 乒乓球游戏机

【TB作品】51单片机 Proteus仿真00016 乒乓球游戏机

课题任务 本课题任务 (联机乒乓球游戏)如下图所示: 同步显示 oo 8个LED ooooo oo ooooo 8个LED 单片机 单片机 按键 主机 从机 按键 设计题目:两机联机乒乓球游戏 图1课题任务示意图 具体说明: 共有两个单片机,每个单片机接8个LED和1 个按键,两个单片机使用串口连接。 (2)单片机…
阅读更多...
视频号矩阵管理系统：短视频内容营销的智能助手

视频号矩阵管理系统：短视频内容营销的智能助手

随着短视频行业的蓬勃发展&#xff0c;视频号矩阵管理系统应运而生&#xff0c;为内容创作者和品牌提供了一站式的短视频管理和营销解决方案。本文将深入探讨视频号矩阵管理系统的核心功能&#xff0c;以及它如何助力用户在短视频营销领域取得成功。 视频号矩阵管理系统概述 …
阅读更多...
C++语言相关的常见面试题目(一)

C++语言相关的常见面试题目(一)

1. const关键字的作用 答&#xff1a; 省流&#xff1a;&#xff08;1&#xff09;定义变量&#xff0c;主要为了防止修改 (2) 修饰函数参数&#xff1a;防止在函数内被改变 &#xff08;3&#xff09;修饰函数的返回值 &#xff08;4&#xff09;修饰类中的成员函数 2. Sta…
阅读更多...
怎样卸载电脑上自带的游戏？

怎样卸载电脑上自带的游戏？

卸载电脑上自带的游戏通常是一个简单的过程&#xff0c;以下是几种常见的方法&#xff0c;您可以根据自己的操作系统版本选择相应的步骤进行操作&#xff1a; 方法一&#xff1a;通过“设置”应用卸载&#xff08;适用于Windows 10和Windows 11&#xff09; 1. 点击开始菜单&…
阅读更多...
fastjson-1.2.24漏洞复现

fastjson-1.2.24漏洞复现

文章目录 0x01 前言0x02 环境0x03漏洞复现环境准备 0x04 漏洞分析利用链源码分析 0x05 总结0x06 可能遇到的坑 0x01 前言 影响版本 fastjson < 1.2.24 本文出于学习fastjson漏洞的目的&#xff0c;为了能更好的复现漏洞&#xff0c;需要有以下前置知识。 springbootfastj…
阅读更多...
最新文章

Copyright @ 2022~2023