浅析STL中的常用算法

一、非变异算法

是一组不破坏操作数据的模板函数,用来对序列数据进行逐个处理、元素查找、子序列搜索、统计和匹配。非变异算法具有极为广泛的适用性,基本上可应用与各种容器。

1查找容器元素find

它用于查找等于某值的元素。它在迭代器区间[first,last)(闭开区间)上查找等于value值的元素,如果迭代器i所指的元素满足*i=value,则返回迭代器i;未找到满足条件的元素,返回last。函数原型:find( v1.begin(), v1.end(), num_to_find );


代码如下:

#include <vector>

#include <algorithm>

#include <iostream>

using namespace std;

void main()

{

int num_to_find = 6;

vector<int> v1;

for( int i = 0; i < 10; i++ )

v1.push_back(2*i);

vector<int>::iterator result;

result = find( v1.begin(), v1.end(), num_to_find );

if( result == v1.end() )

cout << "未找到任何元素匹配 " << num_to_find << endl;

else

cout << "匹配元素的索引值是 " << result-v1.begin() << endl;

}

2条件查找容器元素find_if

利用返回布尔值的谓词判断pred,检查迭代器区间[first,last)(闭开区间)上的每一个元素,如果迭代器i满足pred(*i)=true,表示找到元素并返回迭代值i(找到的第一个符合条件的元素);未找到元素,返回末位置last。函数原型:find_if(v.begin(),v.end(),divby5);


代码如下:

#include <vector>

#include <algorithm>

#include <iostream>

using namespace std;

bool divby5(int x)

{

return x%5?0:1;

}

void main()

{

vector<int> v(20);

for(int i=0;i<v.size();i++)

{

v[i]=(i+1)*(i+3);

cout<<v[i]<<' ';

}

cout<<endl;

vector<int>::iterator ilocation;

ilocation=find_if(v.begin(),v.end(),divby5);

if(ilocation!=v.end())

cout<<"找到第一个能被5整除的元素:"<<*ilocation<<endl<<"元素的索引位置是: "<<ilocation-v.begin()<<endl;

}

3统计等于某值的容器元素个数count

list<int> l;
count(l.begin(),l.end(),value)

4条件统计count_if

count_if(l.begin(),l.end(),pred)。谓词pred含义同find_if中的谓词。例子可以参考例2.

5子序列搜索search

search算法函数在一个序列中搜索与另一序列匹配的子序列。参数分别为一个序列的开始位置,结束位置和另一个序列的开始,结束位置。

函数原型:search(v1.begin(),v1.end(),v2.begin(),v2.end());


代码如下:

#include <vector>

#include <algorithm>

#include <iostream>

using namespace std;

void main()

{

vector<int> v1;

cout<<"v1:";

for(int i=0;i<5;i++)

{

v1.push_back(i+5);

//注意:v1定义时没有给定大小,因此这里不能直接使用赋值语句。

cout<<v1[i]<<' ';

}

cout<<endl;

vector<int> v2;

cout<<"v2:";

for(i=0;i<2;i++)

{

v2.push_back(i+7);

cout<<v2[i]<<' ';

}

cout<<endl;

vector<int>::iterator ilocation;

ilocation=search(v1.begin(),v1.end(),v2.begin(),v2.end());

if(ilocation!=v1.end())

cout<<"v2的元素包含在v1中,起始元素为"<<"v1["<<ilocation-v1.begin()<<']'<<endl;

else

cout<<"v2的元素不包含在v1中"<<endl;

}

6重复元素子序列搜索search_n

search_n算法函数搜索序列中是否有一系列元素值均为某个给定值的子序列。函数原型:search_n(v.begin(),v.end(),3,8),在v中找到3个连续的元素8


代码如下:

#include <vector>

#include <algorithm>

#include <iostream>

using namespace std;

void main()

{

vector<int> v;

v.push_back(1);

v.push_back(8);

v.push_back(8);

v.push_back(8);

v.push_back(6);

v.push_back(6);

v.push_back(8);

vector<int>::iterator i;

i=search_n(v.begin(),v.end(),3,8);

if(i!=v.end())

cout<<"在v中找到3个连续的元素8"<<endl;

else

cout<<"在v中未找到3个连续的元素8"<<endl;

}

7最后一个子序列搜索find_end

函数原型find_end(v1.begin(),v1.end(),v2.begin(),v2.end());在V1中要求的位置查找V2中要求的序列。


代码如下:

#include <vector>

#include <algorithm>

#include <iostream>

using namespace std;

void main()

{

vector<int> v1;

v1.push_back(-5);

v1.push_back(1);

v1.push_back(2);

v1.push_back(-6);

v1.push_back(-8);

v1.push_back(1);

v1.push_back(2);

v1.push_back(-11);

vector<int> v2;

v2.push_back(1);

v2.push_back(2);

vector<int>::iterator i;

i=find_end(v1.begin(),v1.end(),v2.begin(),v2.end());

if(i!=v1.end())

cout<<"v1中找到最后一个匹配v2的子序列,位置在" <<"v1["<<i-v1.begin()<<"]"<<endl;

}

二、变异算法

是一组能够修改容器元素数据的模板函数。copy(v.begin(),v.end(),l.begin());将v中的元素复制到l中。

1 元素复制copy


代码如下:

#include <vector>

#include <list>

#include <algorithm>

#include <iostream>

using namespace std;

void main()

{

vector<int> v;

v.push_back(1);

v.push_back(3);

v.push_back(5);

list<int> l;

l.push_back(2);

l.push_back(4);

l.push_back(6);

l.push_back(8);

l.push_back(10);

copy(v.begin(),v.end(),l.begin());

list<int>::iterator i;

for(i=l.begin();i!=l.end();i++)

cout<<*i<<' ';

cout<<endl;

}

2 元素变换transform改变

函数原型:transform(v.begin(),v.end(),l.begin(),square);也是复制,但是要按某种方案复制。


代码如下:

#include <vector>

#include <list>

#include <algorithm>

#include <iostream>

using namespace std;

int square(int x)

{

return x*x;

}

void main()

{

vector<int> v;

v.push_back(5);

v.push_back(15);

v.push_back(25);

list<int> l(3);

transform(v.begin(),v.end(),l.begin(),square);

list<int>::iterator i;

for(i=l.begin();i!=l.end();i++)

cout<<*i<<' ';

cout<<endl;

}

3 替换replace

replace算法将指定元素值替换为新值。


代码如下:

#include <vector>

#include <algorithm>

#include <iostream>

using namespace std;

void main()

{

vector<int> v;

v.push_back(13);

v.push_back(25);

v.push_back(27);

v.push_back(25);

v.push_back(29);

replace(v.begin(),v.end(),25,100);

vector<int>::iterator i;

for(i=v.begin();i!=v.end();i++)

cout<<*i<<' ';

cout<<endl;

}

输出结果为13 100 27 100 29

4 条件替换replace_if

函数原型:replace_if(v.begin(),v.end(),odd,100);


代码如下:

#include <vector>

#include <algorithm>

#include <iostream>

using namespace std;

bool odd(int x)

{

return x%2;

}

void main()

{

vector<int> v;

for(int i=1;i<10;i++)

v.push_back(i);

replace_if(v.begin(),v.end(),odd,100);

vector<int>::iterator ilocation;

for(ilocation=v.begin();ilocation!=v.end();ilocation++)

cout<<*ilocation<<' ';

cout<<endl;

}

5 n次填充fill_n

函数原型fill_n(v.begin(),5,-1);向从v.begin开始的后面5个位置跳入-1


代码如下:

#include <vector>

#include <algorithm>

#include <iostream>

using namespace std;

void main()

{

vector<int> v(10);

fill_n(v.begin(),5,-1);

vector<int>::iterator ilocation;

for(ilocation=v.begin();ilocation!=v.end();ilocation++)

cout<<*ilocation<<' ';

cout<<endl;

}

输出结果:-1 -1 -1 -1 -1 0 0 0 0 0

6 随机生成n个元素generate

函数原型:generate_n(v.begin(),5,rand);向从v.begin开始的后面5个位置随机填写数据。


代码如下:

#include <vector>

#include <algorithm>

#include <iostream>

using namespace std;

void main()

{

vector<int> v(10);

generate_n(v.begin(),5,rand);

vector<int>::iterator ilocation;

for(ilocation=v.begin();ilocation!=v.end();ilocation++)

cout<<*ilocation<<' ';

cout<<endl;

}

7 条件移除remove_if

返回值相当于移除满足条件的元素后形成的新向量的end()值。

函数原型:remove_if(v.begin(),v.end(),even);


代码如下:

#include <vector>

#include <algorithm>

#include <iostream>

using namespace std;

bool even(int x)

{

return x%2?0:1;

}

void main()

{

vector<int> v;

for(int i=1;i<=10;i++)

v.push_back(i);

vector<int>::iterator ilocation,result;

cout<<"移除前:";

for(ilocation=v.begin();ilocation!=v.end();ilocation++)

cout<<*ilocation<<' ';

cout<<endl;

result=remove_if(v.begin(),v.end(),even);

cout<<"移除后:";

for(ilocation=v.begin();ilocation!=result;ilocation++)

cout<<*ilocation<<' ';

cout<<endl;

}

8 剔除连续重复元素unique

函数原型:unique(v.begin(),v.end());


代码如下:

#include <vector>

#include <algorithm>

#include <iostream>

using namespace std;

void main()

{

vector<int> v;

v.push_back(2);

v.push_back(6);

v.push_back(6);

v.push_back(6);

v.push_back(9);

v.push_back(6);

v.push_back(3);

vector<int>::iterator ilocation,result;

result=unique(v.begin(),v.end());

for(ilocation=v.begin();ilocation!=result;ilocation++)

cout<<*ilocation<<' ';

cout<<endl;

}

输出结果:2 6 9 6 3

三、排序算法

1、创建堆make_heap

2、元素入堆push_heap(默认插入最后一个元素)

3、元素出堆pop_heap(与push_heap一样,pop_heap必须对堆操作才有意义)


代码如下:

#include <vector>

#include <algorithm>

#include <iostream>

using namespace std;

void main()

{

vector<int> v;

v.push_back(5);

v.push_back(6);

v.push_back(4);

v.push_back(8);

v.push_back(2);

v.push_back(3);

v.push_back(7);

v.push_back(1);

v.push_back(9);

make_heap(v.begin(),v.end());

v.push_back(20);

push_heap(v.begin(),v.end());

vector<int>::iterator ilocation;

for(ilocation=v.begin();ilocation!=v.end();ilocation++)

cout<<*ilocation<<' ';

cout<<endl;

pop_heap(v.begin(),v.end());

for(ilocation=v.begin();ilocation!=v.end();ilocation++)

cout<<*ilocation<<' ';

cout<<endl;

}

4 堆排序sort_heap

使用:


代码如下:

make_heap(v.begin(),v.end());

sort_heap(v.begin(),v.end());

#include <vector>

#include <algorithm>

#include <iostream>

using namespace std;

void main()

{

vector<int> v;

v.push_back(3);

v.push_back(9);

v.push_back(6);

v.push_back(3);

v.push_back(17);

v.push_back(20);

v.push_back(12);

vector<int>::iterator ilocation;

for(ilocation=v.begin();ilocation!=v.end();ilocation++)

cout<<*ilocation<<' ';

cout<<endl;

make_heap(v.begin(),v.end());

sort_heap(v.begin(),v.end());

for(ilocation=v.begin();ilocation!=v.end();ilocation++)

cout<<*ilocation<<' ';

cout<<endl;

}

输出结果:

3 9 6 3 17 20 12
3 3 6 9 12 17 20

5 排序sort

函数原型:sort(v.begin(),v.end());


代码如下:

#include <vector>

#include <algorithm>

#include <iostream>

using namespace std;

void main()

{

vector<int> v;

v.push_back(2);

v.push_back(8);

v.push_back(-15);

v.push_back(90);

v.push_back(26);

v.push_back(7);

v.push_back(23);

v.push_back(30);

v.push_back(-27);

v.push_back(39);

v.push_back(55);

vector<int>::iterator ilocation;

for(ilocation=v.begin();ilocation!=v.end();ilocation++)

cout<<*ilocation<<' ';

cout<<endl;

sort(v.begin(),v.end());//比较函数默认

for(ilocation=v.begin();ilocation!=v.end();ilocation++)

cout<<*ilocation<<' ';

cout<<endl;

}

(0)

相关推荐

  • c++ STL容器总结之:vertor与list的应用

    STL提供六大组件,彼此可以组合套用 1.容器(containers):各种数据结构,如vertor,list,deque,set,map.从实现的角度来看,STL容器是一种class template 2.算法(algorithms):各种算法如sort,search,copy,earse.STL算法是一种 function template. 3.迭代器(iterators):扮演容器与算法之间的胶合剂,是所谓的"泛型指针".所有STL容器都有自己的专属的迭代器. 4.仿函数(fu

  • STl中的排序算法详细解析

    1. 所有STL sort算法函数的名字列表: 函数名    功能描述 sort   对给定区间所有元素进行排序 stable_sort 对给定区间所有元素进行稳定排序 partial_sort 对给定区间所有元素部分排序 partial_sort_copy    对给定区间复制并排序 nth_element 找出给定区间的某个位置对应的元素 is_sorted               判断一个区间是否已经排好序 partition     使得符合某个条件的元素放在前面 stable_pa

  • 关于STL中vector容器的一些总结

    1.vector的简单介绍 vector作为STL提供的标准容器之一,是经常要使用的,有很重要的地位,并且使用起来也是灰常方便.vector又被称为向量,vector可以形象的描述为长度可以动态改变的数组,功能和数组较为相似.实际上更专业的描述为:vector是一个多功能的,能够操作多种数据结构和算法的模板类和函数库,vector之所以被认为是一个容器,是因为它能够像容器一样存放各种类型的对象,简单地说,vector是一个能够存放任意类型的动态数组,能够增加和压缩数据.(注:STL的容器从实现的

  • STL list链表的用法详细解析

    本文以List容器为例子,介绍了STL的基本内容,从容器到迭代器,再到普通函数,而且例子丰富,通俗易懂.不失为STL的入门文章,新手不容错过! 0 前言1 定义一个list2 使用list的成员函数push_back和push_front插入一个元素到list中3 list的成员函数empty()4 用for循环来处理list中的元素5 用STL的通用算法for_each来处理list中的元素6 用STL的通用算法count_if()来统计list中的元素个数7 使用count_if()的一个更

  • 关于STL中list容器的一些总结

    1.关于list容器 list是一种序列式容器.list容器完成的功能实际上和数据结构中的双向链表是极其相似的,list中的数据元素是通过链表指针串连成逻辑意义上的线性表,也就是list也具有链表的主要优点,即:在链表的任一位置进行元素的插入.删除操作都是快速的.list的实现大概是这样的:list的每个节点有三个域:前驱元素指针域.数据域和后继元素指针域.前驱元素指针域保存了前驱元素的首地址:数据域则是本节点的数据:后继元素指针域则保存了后继元素的首地址.其实,list和循环链表也有相似的地方

  • 关于STL中的map容器的一些总结

    一.关于map的介绍 map是STL的一个容器,和set一样,map也是一种关联式容器.它提供一对一(其中第一个可以称为关键字,每个关键字只能在map中出现一次,第二个可能称为该关键字的值)的数据处理能力,由于这个特性,有助于我们处理一对一数据.这里说下map内部数据的组织,map内部是自建一颗红黑树(一种非严格意义上的平衡二叉树),这颗树具有对数据自动排序的功能,所以在map内部所有的数据都是有序的.学习map我们一定要理解什么是一对一的数据映射?比如:一个班级中,每个学生的学号跟他的姓名就存

  • 浅析STL中的常用算法

    一.非变异算法 是一组不破坏操作数据的模板函数,用来对序列数据进行逐个处理.元素查找.子序列搜索.统计和匹配.非变异算法具有极为广泛的适用性,基本上可应用与各种容器. 1查找容器元素find 它用于查找等于某值的元素.它在迭代器区间[first,last)(闭开区间)上查找等于value值的元素,如果迭代器i所指的元素满足*i=value,则返回迭代器i:未找到满足条件的元素,返回last.函数原型:find( v1.begin(), v1.end(), num_to_find ); 复制代码

  • 浅析JavaScript中的常用算法与函数

    代码使用方法: 0001:判断一个计算结果是不是无穷大:if(isFinite(999999999*999999999) == true)----------------------------------------------------------------------------------------------------0002:判断是不是数字:if(isNaN("Blue") == true),不是数字则为true,是数字则为false.---------------

  • C++ STL中的常用遍历算法分享

    目录 1.for_each 功能描述 函数原型 2.transform 功能描述 函数原型 1.for_each 功能描述 实现容器遍历 函数原型 for_each(itertor beg,iterator end,_func);//遍历算法 遍历容器元素//beg 开始迭代器//end 结束迭代器//_func函数或者函数对象 代码 #include <iostream> using namespace std; #include <vector> #include <al

  • C++ STL中常见的算法使用方式

    目录 什么是STL? 0. < algorithm> 是什么: 1. Non-modifying sequence operations: 1.1 find:(Find value in range) 1.2 count:(Count appearances of value in range) 1.3 equal:(Test whether the elements in two ranges are equal) 1.4 search:(Search range for subsequen

  • 深入解析C++ STL中的常用容器

    STL是C/C++开发中一个非常重要的模板,而其中定义的各种容器也是非常方便我们大家使用.下面,我们就浅谈某些常用的容器.这里我们不涉及容器的基本操作之类,只是要讨论一下各个容器其各自的特点.STL中的常用容器包括:顺序性容器(vector.deque.list).关联容器(map.set).容器适配器(queue.stac). 1.顺序性容器 (1)vectorvector是一种动态数组,在内存中具有连续的存储空间,支持快速随机访问.由于具有连续的存储空间,所以在插入和删除操作方面,效率比较慢

  • JavaScript求一组数的最小公倍数和最大公约数常用算法详解【面向对象,回归迭代和循环】

    本文实例讲述了JavaScript求一组数的最小公倍数和最大公约数常用算法.分享给大家供大家参考,具体如下: 方法来自求多个数最小公倍数的一种变换算法(详见附录说明) 最小公倍数的算法由最大公约数转化而来.最大公约数可通过如下步骤求得: (1) 找到a1,a2,..,an中的最小非零项aj,若有多个最小非零项则任取一个 (2) aj以外的所有其他非0项ak用ak mod aj代替:若没有除aj以外的其他非0项,则转到(4) (3) 转到(1) (4) a1,a2,..,an的最大公约数为aj 写

  • 浅析C++中模板的那点事

    1.什么是模板 假设现在我们完成这样的函数,给定两个数x和y求式子x^2 + y^2 + x * y的值 .考虑到x和y可能是 int , float 或者double类型,那么我们就要完成三个函数: int fun(int x,int y);float fun(float x,float y);double fun(double x,double y); 并且每个fun函数内部所要完成的操作也是极其的相似.如下: 复制代码 代码如下: int fun(int x,int y){    int

  • C++ STL中五个常用算法使用教程及实例讲解

    目录 前言 sort()排序 常用遍历算法for_each() 常用遍历算法 搬运transform() 查找算法find 删除操作erase() 实例应用 前言 在C++中使用STL算法都要包含一个算法头文件 #include<algorithm> 这样我们才能使用这个STL算法函数 sort()排序 Sort函数包含在头文件为#include<algorithm>的c++标准库中,是一个专门用来排序的高效的函数,我们在解决问题时可以方便快捷的排列顺序. sort()函数中有三个

  • C++中STL的常用算法总结

    目录 1.常用遍历算法 1.1 for_each 1.2 transform 2.常用查找算法 2.1 find 2.2 find_if 2.3 adjacent_find 2.4 binary_search 2.5 count 2.6 count_if 3.常用排序算法 3.1 sort 3.2 random_shuffe 3.3 merge 3.4 reverse 4.常用拷贝和替换算法 4.1 copy 4.2 replace 4.3 replace_if 4.4 swap 5.常用算术生

随机推荐