文档章节

STL学习记录(三):算法基础简要

YourFirst
 YourFirst
发布于 2015/10/06 17:02
字数 1397
阅读 15
收藏 0

STL算法基础简要

  • 简单的算法实例
  • 算法中的范围(Ranges)

简单的算法实例

STL提供多种标准算法来处理容器中的数据,这些算法包括搜索、排序、拷贝、修改,重排等基本常用的操作。STL算法不是某个容器类的成员函数而是,通过迭代器操作的全局函数。这样的一个好处就是算法只需要实现一次,而不用为每个特定类型的容器都重新实现算法。它还支持用户自定义的容器类型。

实例代码

常用版本 :

#include <alogrithm>
#include <vector>
#include <iostream>
using namespace std;

int main(){
	vector<int> coll;
	coll.push_back(2);
	coll.push_back(5);
	coll.push_back(4);
	coll.push_back(1);
	coll.push_back(6);
	coll.push_back(3);

	vector<int>::const_iterator minpos=min_element(coll.begin(),coll.end());
	cout<<"min: "<<*minpos<<endl;

	vector<int>::const_iterator maxpos=min_element(coll.begin(),coll.end());
	cout<<"max: "<<*maxpos<<endl;

	sort(coll.begin(),coll.end());

	vector<int>::iterator pos3;
	pos3=find(coll.begin(),coll.end(),3);

    reverse(pos3,coll.end());

	vector<int>::const_iterator pos;
	for(pos=coll.begin();pos!=coll.end();++pos){
	cout<<*pos<<" ";
	}
	cout<<endl;
	return 0;
}

C++11 版本:

#include <alogrithm>
#include <vector>
#include <iostream>
using namespace std;
int main(){
	vector<int> coll={2,5,6,1,6,3};

	auto minpos=min_element(coll.cbegin(),coll.cend());
	cout<<"min: "<<*minpos<<endl;

	auto maxpos=min_element(coll.cbegin(),coll.cend());
	cout<<"max: "<<*maxpos<<endl;

	sort(coll.begin(),coll.end());

	auto pos3=find(coll.begin(),coll.end(),3);
	
	reverse(pos3,coll.end());

	for(auto elem:coll){
		cout<<elem<<" ";
	}
	cout<<endl;
	return 0;
}

**程序的输出均为: ** min: 1 max: 6 1 2 6 5 4 3

实例中min_element() 和 max_element() 算法通过两个参数来确定算法的操作范围,算法返回的是一个iterator对象,分别指向最小值和最大值。find() 算法查找所给区域内的某个值,当找到是返回第一个该值的iterator 若没有则返回的是该区域内最后一个对象的下一个对象的 iterator 该例中是 coll.end()。sort() 算法对所给区域内的对象进行排序。 reverse()对所给区域内对象进行倒置。 ##算法中的范围(Ranges)

每个算法处理的都是一个或者多个范围的数据元素。你通过两个语句将范围的开始和结尾传递给算法,而不是通过一个语句。这个接口很灵活但是同时也带来了一些问题,例如某个范围: list_1.begin() ,list_2.end() 那么当迭代器前进的时候,因为永远都无法到达范围的结尾程序将出现不可预知的问题。从这个角度来说迭代器并没有传统的指针那么安全可靠。所以在使用算法的时候,一定要确保迭代器属于同一个容器并且确保范围正确,不要将开始和结尾倒置了。当然这种错误导致的未定义行为,STL可以自行捕捉和并进行相应处理。 每个算法中的范围都是个半开区间,用数学中的定义就是左闭右开区间。所以该范围包含开始,但是不包含用于标识末尾的位置。这样的一个好处就是有效的防止了我们多余空容器的处理。 实例代码:

#include<iostream>
#include<list>
#include<algorithm>
using namespaced std:

int main(){
	list<int> coll;
	for(int i=20;i<40;++i){
		coll.push_back(i);
	}
	list<int>::iterator pos25,pos35;
	pos25=find(coll.begin(),coll.end(),25);
	pos35=find(coll.begin(),coll.end(),35);
	
	cout<<"max: "<<*max_element(pos25,pos35)<<endl;
	cout<<"max: "<<*max_element(pos25,++pos35)<<endl;
	return 0;
}

输出结果: max: 34 max: 35

需要注意的有:

  • 针对本例中的不支持随机访问的容器迭代器前进采用 ++ 而像vector 这种支持随机访问的可以采用 +1
  • 本例中我们事先就已经知道了pos25与pos35的前后关系当我们不知道两者的前后关系时该如何应对

支持随机访问容器的应对方法:

if(pos25<pos35){
	//[pos25,pos35)为有效范围
} 
else{
	//[pos35,pos25)为有效范围
}

不支持随机访问容器的常规应对方法:

pos25=find(cloo.begin(),coll.end(),25);
pos35=find(coll.begin(),pos25,35);

if(pos25!=coll.end() && pos35!=pos25){
	//pos35在前面有效区间[pos35,pos25)
}
else{
	pos35=find(pos25,coll.end(),35);
	if(pos!=coll.end(){
		//pos25在前面有效区间[pos25,pos35)
	}
	else{
		//pos25与pos35至少有一个不存在
	}
}

不支持随机访问容器的C++11中更加有效的方法:

pos=find_if(coll.begin(),coll.end(),
			[] (int i){
				return i==25 || i==35;
				});
if(pos==coll.end()){
	//不存在值为25和35的迭代器
	....
}
else if(*pos==25){
//25在前面
pos25=pos;
pos35=find(++pos,coll.end(),35);
....
}
else {
//35在前面
pos35=pos;
pos25=find(++pos,coll.end(),25);
....
}

在这段代码中使用了lambda表达式,这是c++11标准中才开始采用的。该表达式用来确定查找时返回第一个出现的值(25 or 35),如果存在的话。

[] (int i){
				return i==25 || i==35;
				}

多个范围的处理

在某些算法中可能涉及到多个范围例如equal、copy函数,在使用这些算法的时候需要注意第二个范围的大小最起码等于第一范围的大小。当第二个范围小的时候我们需要重新设定第二个范围的大小。

#include<iostream>
#include<list>
#include<vector>
#include<deque>
using namespace std:
int main(){
	list<int> coll={1,2,3,4,5}; //c++11
	vector<int> coll2;

	//重置coll2大小调用equal算法
	coll2.resize(coll.size());
	if(equal(coll1.begin(),coll1.end(),coll2.begin()){
		cout<<"coll1 is equal coll2"<<endl;
	}

	deque<int> coll3(coll1.size());//让coll3与coll1大小一样
	copy(coll1.begin(),coll1.end(),coll3.begin());

	return 0;
}	

需要注意的是这里不管是重置大小还是初始化时就给定大小,其实都为容易创建了新的元素(元素的值由默认构造器初始化)。还有就是这里copy算法之所以需要第二个范围大是因为该算法采用重写的方式而不是插入。

© 著作权归作者所有

YourFirst
粉丝 1
博文 16
码字总数 17792
作品 0
合肥
程序员
私信 提问
如何自学成为C/C++程序员大牛

C语言是面向过程的,而C++是面向对象的 C和C++的区别: C是一个结构化语言,它的重点在于算法和数据结构。C程序的设计首要考虑的是如何通过一个过程,对输入(或环境条件)进行运算处理得到...

小辰带你看世界
2018/05/11
0
0
C#转C++的一点分享

从C#转C++有段时间了,一直想分享点什么,但又不太好意思分享,毕竟自己做C++的时间不太长,最近感觉自己已能胜任现有工作,想分享的想法又强了点,前几天看到这样一篇博客《那些年·我们读过的专业...

爱情经纬线
2014/01/17
4.1K
11
C语言编程学习:制作掷骰子小游戏

C语言是面向过程的,而C++是面向对象的 C和C++的区别: C是一个结构化语言,它的重点在于算法和数据结构。C程序的设计首要考虑的是如何通过一个过程,对输入(或环境条件)进行运算处理得到...

小辰带你看世界
2018/05/20
0
0
C语言/C++程序设计编程基础学习—经典算法

C语言是面向过程的,而C++是面向对象的 C和C++的区别: C是一个结构化语言,它的重点在于算法和数据结构。C程序的设计首要考虑的是如何通过一个过程,对输入(或环境条件)进行运算处理得到...

小辰带你看世界
2018/03/24
0
0
旅行,说走就走 Help? [C++数据类型和表达式]

旅行,说走就走 Help? [C++数据类型和表达式] 摘要: 原创出处: http://www.cnblogs.com/Alandre/ 泥沙砖瓦浆木匠 希望转载,保留摘要,谢谢! 乐天派。我却喜欢和老妈说“老妈小时候喜欢羡慕...

泥沙砖瓦浆木匠
2014/08/29
93
0

没有更多内容

加载失败,请刷新页面

加载更多

STM32进阶之串口环形缓冲区实现

队列的概念 在此之前,我们来回顾一下队列的基本概念: 队列 (Queue):是一种先进先出(First In First Out ,简称 FIFO)的线性表,只允许在一端插入(入队),在另一端进行删除(出队)。 队列...

杰杰1号
21分钟前
8
0
设计模式-建造者模式

建造者模式 定义 将一个复杂对象的构建和它的表示分离,使得同样的构建过程创建出不同的表示。这句话理解起来优点抽象,我们打个简单的比方吧,中国人都喜欢做菜,做菜的时候后会放很多配料...

木本本
25分钟前
9
0
017、xml版本代码生成器配置

1、在pom.xml文件中增加mybatis-generator-maven-plugin插件 <build> <plugins> <plugin> <groupId>org.mybatis.generator</groupId> <artifactId>......

北岩
37分钟前
6
0
用jQuery-Easy-UI编写注册页面

本文转载于:专业的前端网站➮用jQuery-Easy-UI编写注册页面 1 <!DOCTYPE html> 2 <html lang="en"> 3 4 <head> 5 <meta charset="UTF-8"> 6 <meta name="viewport" content=......

前端老手
45分钟前
5
0
Git ssh配置

生成密钥对 ssh-keygen -t rsa -C "email@email.com"邮箱替换自己邮箱在地址C:\Users\账户\.ssh下,id_rsa、id_rsa.pub两个文件复制文件id_rsa.pub内容到github\gitlab的Settings-> SSH ......

JUKE
53分钟前
6
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部