C++ 的常见算法 之三

news/2024/7/8 3:32:31 标签: c++, 算法, 开发语言

C++ 的常见算法 之三

  • 合并
    • merge
      • 使用实列
    • inplace_merge
      • 使用实列
    • set_difference
      • 使用实列
  • 堆
    • make_heap
      • 使用实列
    • sort_heap
      • 使用实列

合并

merge

将排序范围 [first1,last1) 和 [first2,last2) 中的元素合并到一个新范围中，该范围从 result 开始，所有元素均已排序。

  • 第一个版本使用operator< 来比较元素，
  • 第二个版本使用comp 来比较元素。两个范围中的元素应已根据相同的标准（operator< 或 comp）进行排序。结果范围也按此排序。

使用实列

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

using namespace std;

struct personnel {
	string  name;
	int     age;
};

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 () {
  int first[] = {5,10,15,20,25};
  int second[] = {50,40,30,20,10};
  vector<int> v(10);
  vector<personnel> it_depart = {
	  {"John", 30},
	  {"Allison", 25},		  
	  {"Sam", 29},		  
	  {"Alice", 39},		  
  };
  vector<personnel> hr_depart = {
	  {"Michael", 40},
	  {"Tommy", 35},		  
	  {"Eric", 49},		  
	  {"Johnson", 59},		  
  };
  vector<personnel> all_employee(8);

  sort (first,first+5);
  sort (second,second+5);
  merge (first,first+5,second,second+5,v.begin());

  cout << "The resulting vector contains:";
  for_each(v.begin(), v.end(), [](int val)->void {cout << val << " ";}); 
  cout << '\n';

  sort (it_depart.begin(), it_depart.end(), sort_object);
  cout << "After Sorted, IT depart:" << endl;
  for_each(it_depart.begin(), it_depart.end(), 
			[](personnel emp)->void {cout << emp.name << " " << emp.age << endl;}); 
  cout << '\n';

  sort (hr_depart.begin(), hr_depart.end(), sort_object);
  cout << "After Sorted, HR depart:" << endl;
  for_each(hr_depart.begin(), hr_depart.end(), 
			[](personnel emp)->void {cout << emp.name << " " << emp.age << endl;}); 
  cout << '\n';

  merge(it_depart.begin(), it_depart.end(), 
			hr_depart.begin(), hr_depart.end(), all_employee.begin(), sort_object);
  cout << "After Merged, All employee:" << endl;

  cout << "All Employee:" << endl;
  for_each(all_employee.begin(), all_employee.end(), 
			[](personnel emp)->void {cout << emp.name << " " << emp.age << endl;}); 
  cout << '\n';

  return 0;
}

代码运行结果屏幕输出

The resulting vector contains:5 10 10 15 20 20 25 30 40 50
After Sorted, IT depart:
Allison 25
Sam 29
John 30
Alice 39

After Sorted, HR depart:
Tommy 35
Michael 40
Eric 49
Johnson 59

After Merged, All employee:
All Employee:
Allison 25
Sam 29
John 30
Tommy 35
Alice 39
Michael 40
Eric 49
Johnson 59

inplace_merge

合并两个连续的排序范围：[first,middle) 和 [middle,last)，将结果放入合并的排序范围 [first,last) 中。

  • 第一个版本使用operator< 来比较元素，
template <class BidirectionalIterator>  
void inplace_merge (BidirectionalIterator first, BidirectionalIterator middle, 
                     BidirectionalIterator last);
  • 第二个版本使用comp 来比较元素。两个范围中的元素应已根据相同的标准（operator< 或 comp）进行排序。结果范围也按此排序。
template <class BidirectionalIterator, class Compare>  
void inplace_merge (BidirectionalIterator first, BidirectionalIterator middle,         
             BidirectionalIterator last, Compare comp);

该函数保留具有等效值的元素的相对顺序，第一个范围中的元素位于第二个范围中的等效元素之前。

使用实列

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

using namespace std;

struct personnel {
	string  name;
	int     age;
};

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 () {
	int first[] = {5,10,15,20,25};
	int second[] = {50,40,30,2,1};

	vector<personnel> it_depart = {
	  {"John", 30},
	  {"Allison", 25},		  
	  {"Sam", 29},		  
	  {"Alice", 39},		  
	};
	vector<personnel> hr_depart = {
	  {"Michael", 40},
	  {"Tommy", 18},		  
	  {"Eric", 19},		  
	  {"Johnson", 59},		  
	};
	vector<personnel> all_employee(8);
	vector<personnel>::iterator it_emp;
  
	vector<int> v(10);
	vector<int>::iterator it;

	sort (first,first+5);
	sort (second,second+5);

	it=copy (first, first+5, v.begin());
	copy (second,second+5,it);
	cout << "Before merge:";
	for_each(v.begin(), v.end(), [](int val)->void{cout << val << " ";});
	cout << endl;
	
	inplace_merge (v.begin(),v.begin()+5,v.end());

	cout << " After merge:";
	for_each(v.begin(), v.end(), [](int val)->void{cout << val << " ";});
	cout << endl;

	sort (it_depart.begin(), it_depart.end(), sort_object);
	sort (hr_depart.begin(), hr_depart.end(), sort_object);

	it_emp=copy (it_depart.begin(), it_depart.end(), all_employee.begin());
	copy (hr_depart.begin(), hr_depart.end(), it_emp);
	cout << "Employee before merge:" << endl;
	for_each(all_employee.begin(), all_employee.end(), 
			[](personnel emp)->void {cout << emp.name << " " << emp.age << endl;});
	cout << endl;
	
	inplace_merge (all_employee.begin(), 
			all_employee.begin()+4, all_employee.end(), sort_object);

	cout << "Employee after merge:" << endl;
	for_each(all_employee.begin(), all_employee.end(), 
			[](personnel emp)->void {cout << emp.name << " " << emp.age << endl;});
	cout << endl;

	return 0;
}

代码运行结果屏幕输出

Before merge:5 10 15 20 25 1 2 30 40 50
 After merge:1 2 5 10 15 20 25 30 40 50
Employee before merge:
Allison 25
Sam 29
John 30
Alice 39
Tommy 18
Eric 19
Michael 40
Johnson 59

Employee after merge:
Tommy 18
Eric 19
Allison 25
Sam 29
John 30
Alice 39
Michael 40
Johnson 59

set_difference

构造一个排序范围，其元素是，排序范围 [first1,last1)和排序范围 [first2,last2)之间的差。

两个集合的差是由第一个集合中存在，但第二个集合中不存在的元素形成的。函数复制的元素始终来自第一个范围，且顺序相同。

对于支持值多次出现的容器，差异包括给定值在第一个范围中出现的次数减去第二个范围中匹配元素的数量（保留顺序）。

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

范围中的元素应已根据相同的标准（operator< 或 comp）进行排序。结果范围也按此排序。

使用实列

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

using namespace std;

struct personnel {
	string  name;
	int     age;
};

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;

struct equal_class {
   bool operator() (personnel lf, personnel lr) 
	{ return ((lf.name != lr.name) || (lf.age != lr.age));}
} equal_object;

int main () {
  vector<int> first = {15,10,50,20,25,2};
  vector<int> second = {50,40,30,20,10};
  
  vector<personnel> it_depart = {
	  {"John", 30},
	  {"Allison", 25},		  
	  {"Sam", 29},		  
	  {"Alice", 30},		  
  };
  vector<personnel> all_employee = {
	  {"John", 30},
	  {"Allison", 25},		  
	  {"Sam", 29},		  
	  {"Alice", 39},		  
	  {"Tommy", 35},		  
	  {"Eric", 49},		  
	  {"Johnson", 59},		  
  };
  vector<personnel> other_employee(all_employee.size());

  vector<int> v(11); 
  vector<int>::iterator it;
  vector<personnel>::iterator it_emp;

  sort (first.begin(), first.end()); 
  sort (second.begin(), second.end());

	it=set_difference (first.begin(), first.end(),
			second.begin(), second.end(), v.begin());
                                              
	v.resize(it-v.begin());

	cout << "The difference has " << (v.size()) << " elements:\n";
	for_each(v.begin(), v.end(), [](int val)->void {cout << val << " ";});
	cout << endl;
	
	sort (it_depart.begin(), it_depart.end(), sort_object); 
	sort (all_employee.begin(), all_employee.end(), sort_object);
	it_emp=set_difference (all_employee.begin(), all_employee.end(),
			it_depart.begin(), it_depart.end(), other_employee.begin(), equal_object);
	other_employee.resize(it_emp - other_employee.begin());

	cout << "Other employee:" << endl;
	for_each(other_employee.begin(), other_employee.end(), 
			[](personnel emp)->void {cout << emp.name << " " << emp.age << endl;});
	cout << endl;

  return 0;
}

代码运行结果屏幕输出

The difference has 3 elements:
2 15 25
Other employee:
Tommy 35
Alice 39
Eric 49
Johnson 59

堆

make_heap

重新排列 [first,last) 范围内的元素，使它们形成堆。

堆是一种组织元素序列的方法，它允许在任何时刻，重复地快速检索具有最高值的元素（使用 pop_heap），同时允许快速插入新元素（使用 push_heap）。

具有最高值的元素始终是第一个元素。其他元素的顺序取决于特定的实现，但所有与堆相关的函数都是一致的。

  • 使用operator<（对于第一个版本）或
  • comp（对于第二个版本）来比较元素：具有最高值的元素是与范围中的每个其他元素进行比较时将返回 false 的元素。

标准容器适配器priority_queue自动调用make_heap、push_heap和pop_heap来维护容器的堆属性。

使用实列

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

using namespace std;

int main () {
  vector<int> v = {10,20,30,5,15};

  make_heap (v.begin(),v.end());
  cout << "Initial heap: ";
  for_each(v.begin(),v.end(), [](int val)->void {cout << val << " ";});
  cout << endl;
  cout << "initial max heap   : " << v.front() << '\n';

  pop_heap(v.begin(),v.end()); 
  cout << "after pop_head heap: ";
  for_each(v.begin(),v.end(), [](int val)->void {cout << val << " ";});
  cout << endl;
  
  v.pop_back();
  cout << "after pop_back vector: ";
  for_each(v.begin(),v.end(), [](int val)->void {cout << val << " ";});
  cout << endl;
  cout << "max heap after pop : " << v.front() << '\n';

  v.push_back(99); 
  cout << "after push_back vector: ";
  for_each(v.begin(),v.end(), [](int val)->void {cout << val << " ";});
  cout << endl;

  push_heap (v.begin(),v.end());
  cout << "after push_head heap: ";
  for_each(v.begin(),v.end(), [](int val)->void {cout << val << " ";});
  cout << endl;
  cout << "max heap after push: " << v.front() << '\n';

  return 0;
}

代码运行结果屏幕输出:

Initial heap: 30 20 10 5 15
initial max heap   : 30
after pop_head heap: 20 15 10 5 30
after pop_back vector: 20 15 10 5
max heap after pop : 20
after push_back vector: 20 15 10 5 99
after push_head heap: 99 20 10 5 15
max heap after push: 99

sort_heap

将堆范围 [first,last) 中的元素按升序或降序排序。

  • 第一个版本使用operator<来比较元素，
  • 第二个版本使用comp来比较元素，这应该与构造堆时使用的相同。

该序列失去了其作为堆的属性。

使用实列

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

using namespace std;

struct personnel {
	string  name;
	int     age;
};

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

int main () {
  vector<int> v = {10,20,30,5,15};
  vector<personnel> depart = {
	  {"John", 30},
	  {"Allison", 25},		  
	  {"Sam", 29},		  
	  {"Sam", 49},		  
	  {"Alice", 39},		  
  };
  personnel new_incomer = {"Alice", 29};
  
  make_heap (v.begin(),v.end());
  cout << "initial max heap   : " << v.front() << '\n';

  pop_heap (v.begin(),v.end());
  v.pop_back();
  cout << "max heap after pop : " << v.front() << '\n';

  v.push_back(99);
  push_heap (v.begin(),v.end());
  cout << "max heap after push: " << v.front() << '\n';

  sort_heap (v.begin(),v.end());
  cout << "final sorted range :";
  for_each(v.begin(),v.end(), [](int val)->void {cout << val << " ";});;
  cout << endl;

//
  make_heap (depart.begin(), depart.end(), sort_object);
  cout << "After make_heap:" << endl;
  cout << "initial max heap   : " << depart.front().name << " " << depart.front().age << '\n';
  for_each(depart.begin(), depart.end(), 
			[](personnel emp)->void {cout << " [ " << emp.name << " " << emp.age << " ] ";}); 
  cout << '\n';

  depart.push_back(new_incomer);
  cout << "After push_back:" << endl;
  for_each(depart.begin(), depart.end(), 
			[](personnel emp)->void {cout << " [ " << emp.name << " " << emp.age << " ] ";}); 
  cout << '\n';

  push_heap (depart.begin(), depart.end(), sort_object);
  cout << "After make_heap:" << endl;
  cout << "max heap after push: " << depart.front().name << " " << depart.front().age << '\n';
  for_each(depart.begin(), depart.end(), 
			[](personnel emp)->void {cout << " [ " << emp.name << " " << emp.age << " ] ";}); 
  cout << '\n';

  sort_heap (depart.begin(), depart.end(), sort_object);
  cout << "final sorted range :" << endl;
  for_each(depart.begin(), depart.end(), 
	[](personnel emp)->void {
		cout << " [ " << emp.name << "," << emp.age << " ] ";});
  cout << endl;
  
  return 0;
}

代码运行结果屏幕输出:

initial max heap   : 30
max heap after pop : 20
max heap after push: 99
final sorted range :5 10 15 20 99
After make_heap:
initial max heap   : Sam 49
 [ Sam 49 ]  [ John 30 ]  [ Sam 29 ]  [ Allison 25 ]  [ Alice 39 ]
After push_back:
 [ Sam 49 ]  [ John 30 ]  [ Sam 29 ]  [ Allison 25 ]  [ Alice 39 ]  [ Alice 29 ]
After make_heap:
max heap after push: Sam 49
 [ Sam 49 ]  [ John 30 ]  [ Sam 29 ]  [ Allison 25 ]  [ Alice 39 ]  [ Alice 29 ]
final sorted range :
 [ Alice,29 ]  [ Alice,39 ]  [ Allison,25 ]  [ John,30 ]  [ Sam,29 ]  [ Sam,49 ]

http://www.niftyadmin.cn/n/5536392.html

相关文章

昇思25天学习打卡营第6天|linchenfengxue

昇思25天学习打卡营第6天|linchenfengxue

​​​​​​SSD目标检测 SSD&#xff0c;全称Single Shot MultiBox Detector&#xff0c;是Wei Liu在ECCV 2016上提出的一种目标检测算法。使用Nvidia Titan X在VOC 2007测试集上&#xff0c;SSD对于输入尺寸300x300的网络&#xff0c;达到74.3%mAP(mean Average Precision)以…
阅读更多...
Dialog设置背景透明和尺寸

Dialog设置背景透明和尺寸

class TestDialog(context: Context?,var clickListener: OnClickCallBack) : Dialog(context!!) {lateinit var binding:TestDialogBindingoverride fun onCreate(savedInstanceState: Bundle?) {super.onCreate(savedInstanceState)binding TestDialogBinding.inflate(Lay…
阅读更多...
Feign：简化微服务通信的利器

Feign：简化微服务通信的利器

介绍 1.1 什么是 Feign&#xff1f; Feign 是一个声明式、模板化的 HTTP 客户端&#xff0c;它简化了编写 Web 服务客户端的过程。它的主要目的是使 HTTP API 客户端的开发变得更加简单和直观。Feign 的设计理念是将 HTTP 客户端的细节隐藏在背后&#xff0c;使开发者可以专注…
阅读更多...
GPT提示词模板

GPT提示词模板

BRTR 原则 # 背景&#xff08;Background&#xff09; - 描述任务的背景信息&#xff0c;包括任务的起因、目的、相关的历史信息或当前状况。 - 提供足够的背景信息以便让ChatGPT理解任务的上下文。 # 角色&#xff08;Role&#xff09; - 定义ChatGPT在任务中所扮演的角色&…
阅读更多...
比赛获奖的武林秘籍：01 如何看待当代大学生竞赛中“卷”“祖传老项目”“找关系”的现象？

比赛获奖的武林秘籍：01 如何看待当代大学生竞赛中“卷”“祖传老项目”“找关系”的现象？

比赛获奖的武林秘籍&#xff1a;01 如何看待当代大学生竞赛中“卷”“祖传老项目”“找关系”的现象&#xff1f; 摘要 本文主要分析了大学生电子计算机类比赛中“卷”“祖传老项目”“找关系”的现象&#xff0c;结合自身实践经验&#xff0c;给出了相应的解决方案。 正文 …
阅读更多...
高级策略：解读 SQL 中的复杂连接

高级策略：解读 SQL 中的复杂连接

了解基本连接 在深入研究复杂连接之前&#xff0c;让我们先回顾一下基本连接的基础知识。 INNER JOIN&#xff1a;根据指定的连接条件检索两个表中具有匹配值的记录。LEFT JOIN&#xff1a;从左表检索所有记录&#xff0c;并从右表中检索匹配的记录&#xff08;如果有&#x…
阅读更多...
Greenplum（一）【MPP 架构 数据类型】

Greenplum（一）【MPP 架构 数据类型】

1、Greenplum 入门 Greenplum 是基于 MPP 架构的一款分布式分析型数据库&#xff0c;具备关系型数据库的特点&#xff0c;因为它处理的是结构化的数据&#xff0c;同时具备大数据分布式的特点。 1.1、MPP 架构 MPP&#xff08;Massively Parallel Processing&#xff09;架构是…
阅读更多...
实训学习错误总结2

实训学习错误总结2

1、 "timestamp": "2024-07-04T08:43:07.15400:00", "status": 405, "error": "Method Not Allowed", "path": "/wuzi/insert" 简单的来说就是使用的方法与注释不匹配。 规定的是&#xff1a;Get&a…
阅读更多...
最新文章

Copyright @ 2022~2023