浅析STL中的常用算法
字体：[ ] 类型：转载 时间：
以下是对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&
void main()
int num_to_find = 6;
vector&int& v1;
for( int i = 0; i & 10; i++ )
v1.push_back(2*i);
vector&int&::
result = find( v1.begin(), v1.end(), num_to_find );
if( result == v1.end() )
cout && "未找到任何元素匹配 " && num_to_find &&
cout && "匹配元素的索引值是 " && result-v1.begin() &&
}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&
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]&&' ';
vector&int&::
ilocation=find_if(v.begin(),v.end(),divby5);
if(ilocation!=v.end())
cout&&"找到第一个能被5整除的元素："&&*ilocation&&endl&&"元素的索引位置是： "&&ilocation-v.begin()&&
}3统计等于某值的容器元素个数count
list&int&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&
void main()
vector&int& v1;
cout&&"v1:";
for(int i=0;i&5;i++)
v1.push_back(i+5);
//注意：v1定义时没有给定大小，因此这里不能直接使用赋值语句。
cout&&v1[i]&&' ';
vector&int& v2;
cout&&"v2:";
for(i=0;i&2;i++)
v2.push_back(i+7);
cout&&v2[i]&&' ';
vector&int&::
ilocation=search(v1.begin(),v1.end(),v2.begin(),v2.end());
if(ilocation!=v1.end())
cout&&"v2的元素包含在v1中，起始元素为"&&"v1["&&ilocation-v1.begin()&&']'&&
cout&&"v2的元素不包含在v1中"&&
}6重复元素子序列搜索search_n
search_n算法函数搜索序列中是否有一系列元素值均为某个给定值的子序列。函数原型：search_n(v.begin(),v.end(),3,8)，在v中找到3个连续的元素8 代码如下:#include &vector&
#include &algorithm&
#include &iostream&
void main()
vector&int&
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&::
i=search_n(v.begin(),v.end(),3,8);
if(i!=v.end())
cout&&"在v中找到3个连续的元素8"&&
cout&&"在v中未找到3个连续的元素8"&&
}7最后一个子序列搜索find_end
函数原型find_end(v1.begin(),v1.end(),v2.begin(),v2.end());在V1中要求的位置查找V2中要求的序列。 代码如下:#include &vector&
#include &algorithm&
#include &iostream&
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&::
i=find_end(v1.begin(),v1.end(),v2.begin(),v2.end());
if(i!=v1.end())
cout&&"v1中找到最后一个匹配v2的子序列，位置在" &&"v1["&&i-v1.begin()&&"]"&&
}二、变异算法
是一组能够修改容器元素数据的模板函数。copy(v.begin(),v.end(),l.begin());将v中的元素复制到l中。
1 元素复制copy 代码如下:#include &vector&
#include &list&
#include &algorithm&
#include &iostream&
void main()
vector&int&
v.push_back(1);
v.push_back(3);
v.push_back(5);
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&::
for(i=l.begin();i!=l.end();i++)
cout&&*i&&' ';
}2 元素变换transform改变
函数原型：transform(v.begin(),v.end(),l.begin(),square);也是复制，但是要按某种方案复制。 代码如下:#include &vector&
#include &list&
#include &algorithm&
#include &iostream&
int square(int x)
return x*x;
void main()
vector&int&
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&::
for(i=l.begin();i!=l.end();i++)
cout&&*i&&' ';
}3 替换replace
replace算法将指定元素值替换为新值。 代码如下:#include &vector&
#include &algorithm&
#include &iostream&
void main()
vector&int&
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&::
for(i=v.begin();i!=v.end();i++)
cout&&*i&&' ';
}输出结果为13 100 27 100 29
4 条件替换replace_if
函数原型：replace_if(v.begin(),v.end(),odd,100); 代码如下:#include &vector&
#include &algorithm&
#include &iostream&
bool odd(int x)
return x%2;
void main()
vector&int&
for(int i=1;i&10;i++)
v.push_back(i);
replace_if(v.begin(),v.end(),odd,100);
vector&int&::
for(ilocation=v.begin();ilocation!=v.end();ilocation++)
cout&&*ilocation&&' ';
}5 n次填充fill_n
函数原型fill_n(v.begin(),5,-1)；向从v.begin开始的后面5个位置跳入-1 代码如下:#include &vector&
#include &algorithm&
#include &iostream&
void main()
vector&int& v(10);
fill_n(v.begin(),5,-1);
vector&int&::
for(ilocation=v.begin();ilocation!=v.end();ilocation++)
cout&&*ilocation&&' ';
}输出结果：-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&
void main()
vector&int& v(10);
generate_n(v.begin(),5,rand);
vector&int&::
for(ilocation=v.begin();ilocation!=v.end();ilocation++)
cout&&*ilocation&&' ';
}7 条件移除remove_if
返回值相当于移除满足条件的元素后形成的新向量的end（）值。
函数原型：remove_if(v.begin(),v.end(),even); 代码如下:#include &vector&
#include &algorithm&
#include &iostream&
bool even(int x)
return x%2?0:1;
void main()
vector&int&
for(int i=1;i&=10;i++)
v.push_back(i);
vector&int&::iterator ilocation,
cout&&"移除前：";
for(ilocation=v.begin();ilocation!=v.end();ilocation++)
cout&&*ilocation&&' ';
result=remove_if(v.begin(),v.end(),even);
cout&&"移除后：";
for(ilocation=v.begin();ilocation!=ilocation++)
cout&&*ilocation&&' ';
}8 剔除连续重复元素unique
函数原型：unique(v.begin(),v.end()); 代码如下:#include &vector&
#include &algorithm&
#include &iostream&
void main()
vector&int&
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=unique(v.begin(),v.end());
for(ilocation=v.begin();ilocation!=ilocation++)
cout&&*ilocation&&' ';
}输出结果：2 6 9 6 3
三、排序算法
1、创建堆make_heap
2、元素入堆push_heap（默认插入最后一个元素）
3、元素出堆pop_heap（与push_heap一样，pop_heap必须对堆操作才有意义） 代码如下:#include &vector&
#include &algorithm&
#include &iostream&
void main()
vector&int&
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&::
for(ilocation=v.begin();ilocation!=v.end();ilocation++)
cout&&*ilocation&&' ';
pop_heap(v.begin(),v.end());
for(ilocation=v.begin();ilocation!=v.end();ilocation++)
cout&&*ilocation&&' ';
}4 堆排序sort_heap
使用： 代码如下:make_heap(v.begin(),v.end());
sort_heap(v.begin(),v.end());
#include &vector&
#include &algorithm&
#include &iostream&
void main()
vector&int&
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&::
for(ilocation=v.begin();ilocation!=v.end();ilocation++)
cout&&*ilocation&&' ';
make_heap(v.begin(),v.end());
sort_heap(v.begin(),v.end());
for(ilocation=v.begin();ilocation!=v.end();ilocation++)
cout&&*ilocation&&' ';
}输出结果：
3 9 6 3 17 20 123 3 6 9 12 17 20
5 排序sort
函数原型：sort(v.begin(),v.end()); 代码如下:#include &vector&
#include &algorithm&
#include &iostream&
void main()
vector&int&
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&::
for(ilocation=v.begin();ilocation!=v.end();ilocation++)
cout&&*ilocation&&' ';
sort(v.begin(),v.end());//比较函数默认
for(ilocation=v.begin();ilocation!=v.end();ilocation++)
cout&&*ilocation&&' ';
您可能感兴趣的文章:
大家感兴趣的内容
12345678910
最近更新的内容
常用在线小工具STL在使用算法竞赛中的使用方法 （教程+未完成） - CSDN博客
STL在使用算法竞赛中的使用方法 （教程+未完成）
本文面向已有 C 语言和部分算法基础的同学。
内容均是个人总结，由于还没有系统的学习过 C++ 的面向对象，也没有翻过 STL 的代码，均以实用的角度来讲，可能不严谨些。
接下来介绍的将是一些 C++ STL 容器的使用，特性及一些常用函数。然后还有部分好用的函数。都会以介绍加代码样例的方式写出。
Vector 可以看做是一个不定长数组，可以对其进行插入元素，删除元素，按下标访问等基本操作。
重要的一点 Vector 是一个数组 而不是一个链表，例如对 Vector 进行插入操作，是基于元素的移位进行的，是 O（n）的复杂度而不是链表的 O（1），但是在其尾部添加元素时是 O（1），应该是内部可以自动优化。
vector 包含在 &vector& 头文件中。
基本操作：
首先创建一个 装着 int 类型元素的 vector。
ps：&int&这里其实是使用了模板，具体看概念中的模板部分。
vector&int&
接下来给 vector 添加元素，这里先向尾部添加元素，也是最常用的添加元素方式。
ps：这里添加是O（1）
data.push_back(1);
data.push_back(2);
data.push_back(3);
接下来可以用下标访问 vector 里面的元素，和数组类似，输出之前插入的1,2,3
cout && data[0] &&
cout && data[1] &&
cout && data[2] &&
接下来是插入元素和删除元素。下面的插入是把 t 插入到 下标为 i 的位置上，原来 i 位置及其后面的元素，都往后移一位。删除是删除掉下标为 i 的元素，后面的元素全部前移一位。
ps：时间复杂度O（n）
data.insert(data.begin() + i, t);
data.erase(data.begin() + i);
定义 vector 数组时和普通类型一样使用即可
vector&int& example[112345];
example[233].push_back(666);
接下来是是一些常用的函数，将直接给出代码，代码中加入注释。
//返回 data 的大小，有 n 个元素即返回 n
data.size();
//清空 data，恢复 data 的初始状态
data.clear();
//重新设置 data 的长度，可用来直接截短
data.resize(len);
进阶技巧：
了解 vector 使用了模板后，其实 vector 可以用来存 vector 的，例如：
vector&vector&int& &
example.push_back(vector&int&());
example[0].push_back(1);
这里定义时 && 用空格分开是编译器可能会把这里当成其他的关键字。
vector&int&() 表示定义一个空的储存 int 类型的 vector。
这里可能和 vector 数组有点类似，概念上是不同的，使用方法上也有差异。
同理 vector 也可以储存本文将要介绍的其他 STL 容器。
map容器常用来做映射，map的实现是用了数据结构的红黑树，通常来说是O（logn）比 hash 慢些，在一些时间限制不太紧的题中还是够用。
map 实现的是一种映射关系，详细见概念部分。
map 包含在头文件 &map& 中。
基本使用：
首先创建一个map，这里需要给定两个类型，一个是用来当做访问下标（暂且这样将）的，另一个是储存的数据类型。
部分概念：
本部分内容较?嗦仅供读者更好的理解后面的 STL 如何工作，只希望了解 STL 用法可以直接略过。
关于模板这个概念。举个例子，大概意思是，如果要定义一个求两个函数和的函数，需要两个参数 a 和 b，然后返回他们的和。通常来讲我定义函数时如果参数设为 int，那么我这个函数就不可以为 double 类型求和。这时候我需要再为 double 定义一个求和函数。但是你会发现，无不需要关什么 int double 类型，只要输入进来的两个变量，只要定义了他们类型之间的加法应该是什么样子就可以了。
比如说输入两个整型和浮点型，直接返回他们的和就可以了。有了模板这个概念后，我甚至可以给这两个函数输入两个矩阵 a = [1,2,3,4], b = [2,2,3,4]，求这两个矩阵的和，只要我定义好两个矩阵相加应该是什么样的规则就好了。
这样以后更深入的话，就可以知道，这样可以实现类的多态。
意思是给我两个你自己定义的 结构体/对象 我要求他的和，你只要定义好这个数据类型相加应该是什么样的就好了，不用再去定义一个函数。
接下来的 STL 容器都用了模板的概念，大概是 [容器名]&类型名& 这样的形式，然后类型那里可以随便填了（前提是有），int 也好，自己定义的结构体也好，运用上面的概念，STL 容器不关心他存的是上面类型，只要这个类型定义了某些运算应该符合什么样的规则就可以了。
这里可以当做指针对待，不再作详细介绍，[容器名].begin() 返回指向某容器首部的迭代器。
这里用数学里面的概念好了，意思是给定一个 x，对应一个唯一的 y。
亦可把 map 理解成一个下标为任意类型的数组，比如我可以用一个字符串当下标来储存一个整数。
这里用一下 Python 字典的概念好了，map 大概也是这个东西，map 中储存的是无数个 key：value 这样的键值对，不可存在同样的 key，访问 value，通过输入他的 key 来访问。
本文已收录于以下专栏：
相关文章推荐
全排列函数next_permutation
STL 中专门用于排列的函数（可以处理存在重复数据集的排列问题）
头文件：#include 
using namespace 
调用： ne...
1题目：打印出所有的“水仙花数”，所谓“水仙花数”是指一个三位数，其各位数字立方和等于该数
本身。例如：153是一个“水仙花数”，因为153=1的三次方＋5的三次方＋3的三次方。
#include...
一：Git是什么？
       Git是目前世界上最先进的分布式版本控制系统。
二：SVN与Git的最主要的区别？
      SVN是集中式版本控制系统，版本库是集中放在中央服务...
***python2.7
https://www.python.org/download/releases/2.7/
python2.7 for
win-64下载地址
https://www.pytho...
【学习笔记】《STL使用入门教程》第一讲：STL的string类型的使用方法
map的元素都是“实值/键值”所形成的一个对组。每个元素都有一个键，是排序的准则。每个键只能出现一次，不允许重复使用。map可以被视为关联式数组，也就是具有任意索引型别的数组。map就是一种红黑树的K...
他的最新文章
讲师：王禹华
讲师：宋宝华
您举报文章：
举报原因：
原文地址：
原因补充：
(最多只允许输入30个字)