c++非变易算法-stl算法

C++ STL标准模板库在数据结构和算法的实践领域发挥着重要作用,极大的提高了开发效率。STL的三大组成部分为容器、迭代器、算法,本文主要讲解STL算法中的非变易算法。本文从实践的角度简单介绍了一下相关函数的使用。

C++ STL的非变易算法(Non-mutating algorithms)是一组不破坏函数数据的模板函数,用来对序列数据进行逐个处理、元素查找、子序列搜索、统计和匹配,基本上可用于各种容器。下面的叙述中迭代器区间默认为[first, last),迭代器具有“++”迭代和“*”访问操作。

逐个处理算法

for_each函数
该函数对迭代器区间的每个元素,执行单参数函数对象定义的操作。

下面的实例程序,将打印容器vector中的每个元素。

代码如下:

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
void print(int x) {
    cout << x << " ";
}
int main(void) {
    vector<int> v;
    for(int i = 0; i < 10; i++) {
        v.push_back(i * 2);
    }
    for_each(v.begin(), v.end(), print);
    return 0;
}

结果输出为:


代码如下:

0 2 4 6 8 10 12 14 16 18

元素查找算法

find函数
该函数用于查找等于某值的元素。如果迭代器i所指的元素满足*i == value,则返回迭代器i。未找到满足条件的元素,返回last。只要找到第一个满足条件的元素就返回迭代器位置,不再继续查找。

下面的示例程序查找容器vector中,第一个值为6的元素,打印元素位置及其前一元素。

代码如下:

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main(void) {
    vector<int> v;
    for(int i = 0; i < 10; i++) {
        v.push_back(i * 2);
    }
    vector<int>::iterator iv = find(v.begin(), v.end(), 6);
    if(iv == v.end()) {
        cout << "Find nothing." << endl;
    } else {
        cout << "The postion of " << *iv << " is " << iv - v.begin() << endl;
        cout << "The previous element of it is " << *(--iv) << endl;
    }
    return 0;
}

结果输出为:


代码如下:

The postion of 6 is 3
The previous element of it is 4

find_if函数

该函数是find的一个谓词判断版本,查找满足谓词判断函数的元素。

下面的实例程序将寻找容器vector中第一个能被3整除的元素。

代码如下:

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int divBy3(int x) {
    return x % 3 ? 0 : 1;
}
int main(void) {
    vector<int> v;
    for(int i = 1; i < 10; i++) {
        v.push_back(i * 2);
    }
    vector<int>::iterator iv = find_if(v.begin(), v.end(), divBy3);
    if(iv == v.end()) {
        cout << "None could be divided by 3 with no remaineder." << endl;
    } else {
        cout << *iv << " could be divided by 3 with no remainder." << endl;
    }
    return 0;
}

结果输出为:


代码如下:

6 could be divided by 3 with no remainder.

adjacent_find函数

该函数用于查找相等或满足条件的邻近元素对。它有两个使用原型,一个用于查找相等的两个连续元素,另一个使用二元谓词判断,查找满足条件的邻近元素对。

下面的实例程序用于寻找容器中相等的元素和奇偶性相同的元素。

代码如下:

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int parity_equal(int x, int y) {
    return (x - y) % 2 == 0 ? 1 : 0;
}
int main(void) {
    vector<int> v;
    v.push_back(1);
    v.push_back(2);
    v.push_back(3);
    v.push_back(5);
    v.push_back(5);
    v.push_back(7);
    vector<int>::iterator iv = adjacent_find(v.begin(), v.end());
    if(iv != v.end()) {
        cout << "There are two equal elements." << endl;
        cout << "It is " << *iv << endl;
    }
    iv = adjacent_find(v.begin(), v.end(), parity_equal);
    if(iv != v.end()) {
        cout << "There are two parity euqal elements." << endl;
        cout << "They are " << *iv << " and ";
        iv++;
        cout << *iv << endl;
    }
    return 0;
}

输出结果为:


代码如下:

There are two equal elements.
It is 5
There are two parity euqal elements.
They are 3 and 5

find_first_of函数

该函数用于查找某个范围之内的元素。它有两个使用原型,一个是相等,另一个是二元谓词判断。元素找到则返回迭代器,否则返回末位置。

下面的实例程序用于计算容器v2中元素在容器v中重合出现的首位置。

代码如下:

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main(void) {
    vector<int> v;
    v.push_back(1);
    v.push_back(2);
    v.push_back(2);
    v.push_back(3);
    v.push_back(5);
    v.push_back(5);
    v.push_back(7);
    vector<int> v2;
    v2.push_back(3);
    v2.push_back(3);
    v2.push_back(5);
    vector<int>::iterator iv = find_first_of(v.begin(), v.end(), v2.begin(), v2.end());
    cout << "The position of the first equal element is " << iv - v.begin() << endl;
    return 0;
}

输出结果为:


代码如下:

The position of the first equal element is 3

元素统计算法

count函数
该函数用于计算容器中某个给定值的出现次数。它有两个使用原型,区别在于计数是直接返回还是引用返回。

下面的实例程序计算了容器中5的出现次数,结果直接返回。

代码如下:

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main(void) {
    vector<int> v;
    for(int i = 0; i < 17; i++) {
        v.push_back(i % 6);
    }
    int num = count(v.begin(), v.end(), 5);
    cout << "The number of 5 is " << num << endl;
    return 0;
}

输出结果为:


代码如下:

The number of 5 is 2

count_if函数

该函数使用谓词判断函数,统计迭代器区间上满足条件的元素个数。它有两个使用原型,区别在与计数是直接返回还是引用返回。

下面的实例程序统计了容器中大于10的数字的出现次数,结果直接返回。

代码如下:

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int greaterThan10(int x) {
    return x > 10 ? 1 : 0;
}
int main(void) {
    vector<int> v;
    for(int i = 0; i < 17; i++) {
        v.push_back(i);
    }
    int num = count_if(v.begin(), v.end(), greaterThan10);
    cout << "The number of the figure that greater than 10 is " << num << endl;
    return 0;
}

输出结果为:


代码如下:

The number of the figure that greater than 10 is 6

序列匹配算法

mismatch函数
该函数用于比较两个序列,找出首个不匹配元素的位置。它有两个使用原型,分别为不相等和不满足二元谓词条件。

该函数还涉及到pair的使用。

下面的实例程序比较两个整型容器,并找出不匹配的数字。

代码如下:

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main(void) {
    vector<int> v1, v2;
    v1.push_back(3);
    v1.push_back(5);
    v1.push_back(5);
    v2.push_back(3);
    v2.push_back(5);
    v2.push_back(7);
    pair<vector<int>::iterator, vector<int>::iterator> result = mismatch(v1.begin(), v1.end(), v2.begin());
    if(result.first == v1.end() && result.second == v2.end()) {
        cout << "v1 is same as v2." << endl;
    } else {
        cout << "The dismatching figure are "
             << *(result.first) << " and "
             << *(result.second) << endl;
    }
    return 0;
}

输出结果为:


代码如下:

The dismatching figure are 5 and 7

equal函数

该函数逐一比较两个序列的元素是否相等,返回值为true/false,不返回迭代器值。它有两个使用原型,分别为元素相等和二元谓词判断条件。

下面的实例程序用于比较两容器中数字绝对值是否相等。

代码如下:

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int absEqual(int x, int y) {
    //return (x == abs(y) || y == abs(x)) ? 1 : 0;
    return abs(x) == abs(y) ? 1 : 0;
}
int main(void) {
    vector<int> v1, v2;
    v1.push_back(3);
    v1.push_back(5);
    v1.push_back(5);
    v2.push_back(3);
    v2.push_back(5);
    v2.push_back(-5);
    if(equal(v1.begin(), v1.end(), v2.begin(), absEqual)) {
        cout << "The elements of v1 and v2 are equal in abosolute value." << endl;
    } else {
        cout << "The elements of v1 and v2 are not equal in abosolute value." << endl;
    }
    return 0;
}

输出结果为:


代码如下:

The elements of v1 and v2 are equal in abosolute value.

子序列搜索算法

search函数

该函数在一个序列中搜索与另一序列匹配的子序列。它有两个使用原型,分别为完全匹配和二元谓词判断。匹配成功则返回子序列的首个元素的迭代器值。

search函数与find_first_of函数形似,但不相同。search找的是一块相同的区域,要求这块区域与后面列表的元素及其顺序相同;find_first_of找的是一个元素,只要这个元素是后面一个列表的任意一个就行。

下面的实例程序说明了search与find_first_of的不同。

代码如下:

#include <iostream>
#include <algorithm>
#include <vector>
int main(void) {
    vector<int> v1, v2;
    v1.push_back(1);
    v1.push_back(4);
    v1.push_back(2);
    v1.push_back(3);
    v1.push_back(4);
    v2.push_back(2);
    v2.push_back(3);
    v2.push_back(4);
    vector<int>::iterator ivSearch, ivFind;
    ivSearch = search(v1.begin(), v1.end(), v2.begin(), v2.end());
    ivFind = find_first_of(v1.begin(), v1.end(), v2.begin(), v2.end());
    cout << "Position of search: " << ivSearch - v1.begin() << endl;
    cout << "Position of find_first_of: " << ivFind - v1.begin() << endl;
    return 0;
}

输出结果为:


代码如下:

Position of search: 2
Position of find_first_of: 1

search_n函数

该函数用于搜索序列中是否有一系列元素值均为某个给定值的子序列。它有两个使用原型,分别为值相等和满足谓词判断条件。

下面的实例程序展示了寻找3个连续的数字8的过程。

代码如下:

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main(void) {
    vector<int> v;
    v.push_back(3);
    v.push_back(8);
    v.push_back(8);
    v.push_back(8);
    v.push_back(4);
    vector<int>::iterator iv = search_n(v.begin(), v.end(), 3, 8);
    if(iv == v.end()) {
        cout << "There are no three consecutive 8." << endl;
    } else {
        cout << "Three consecutive 8 is founded." << endl;
    }
    return 0;
}

结果输出为:


代码如下:

Three consecutive 8 is founded.

find_end函数
该函数用于在一个序列中搜索出最后一个与另一序列匹配的子序列。用search函数作用相似,方向相反。

下面的实例程序,展示了搜索容器v中最后一个与v1匹配的子序列的过程。

代码如下:

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main(void) {
    vector<int> v, v2;
    v.push_back(1);
    v.push_back(3);
    v.push_back(5);
    v.push_back(3);
    v.push_back(5);
    v.push_back(7);
    v2.push_back(3);
    v2.push_back(5);
    vector<int>::iterator iv = find_end(v.begin(), v.end(), v2.begin(), v2.end());
    if(iv != v.end()) {
        cout << "The position of last matching subsequence is " << iv - v.begin() << endl;
    }
    return 0;
}

输出结果为:


代码如下:

The position of last matching subsequence is 3

(0)

相关推荐

  • C++ STL入门教程(1) vector向量容器使用方法

    一.简介 Vectors 包含着一系列连续存储的元素,其行为和数组类似. 访问Vector中的任意元素或从末尾添加元素都可以在O(1)内完成,而查找特定值的元素所处的位置或是在Vector中插入元素则是O(N). 二.完整程序代码 /*请务必运行以下程序后对照阅读*/ #include <vector> #include <iostream> #include <algorithm> #include <stdexcept> using namespace

  • C++ STL list 遍历删除出错解决方案

    C++ STL list 遍历删除崩溃 错误用法一 下面这种用法会在for的地方崩溃,分析 第一次for循环的时候 it=0,当t.erase(it)执行完成之后 it就变成了 -17891602 表明it不能再作为迭代器进行运算,自然会报错. #include <map> #include <list> using namespace std; typedef std::list<int > TESTLIST; int _tmain(int argc, _TCHAR*

  • 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

  • C++ STL入门教程(3) deque双向队列使用方法

    一.简介 deque(Double Ended Queues,双向队列)和向量很相似,但是它允许在容器头部快速插入和删除(就像在尾部一样). 二.完整程序代码 /*请务必运行以下程序后对照阅读*/ #include <deque> #include <iostream> #include <algorithm> #include <stdexcept> using namespace std; void print(int num) { cout <&

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

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

  • C++ STL入门教程(7) multimap、multiset的使用

    一.multimap(一对多索引) C++ multimap和map所支持的操作相同(除了multimap不支持下标运算),但是multimap允许重复的元素. 完整程序代码: /*请务必运行以下程序后对照阅读*/ ///头文件依旧是map #include <map> #include <string> #include <iostream> using namespace std; int main() { ///1. 初始化 multimap<int, st

  • C++ STL入门教程(2) list双向链表使用方法(附程序代码)

    一.简介 "Unlike other standard sequence containers, list and forward_list objects are specifically designed to be efficient inserting and removing elements in any position, even in the middle of the sequence." Lists将元素按顺序储存在链表中.与向量(vector)相比, 它允许快速

  • 浅谈c++中的stl中的map用法详解

    Map是STL的一个关联容器,它提供一对一(其中第一个可以称为关键字,每个关键字只能在map中出现一次,第二个可能称为该关键字的值)的数据处理能力,由于这个特性,它完成有可能在我们处理一对一数据的时候,在编程上提供快速通道.这里说下map内部数据的组织,map内部自建一颗红黑树(一种非严格意义上的平衡二叉树),这颗树具有对数据自动排序的功能,所以在map内部所有的数据都是有序的,后边我们会见识到有序的好处. 下面举例说明什么是一对一的数据映射.比如一个班级中,每个学生的学号跟他的姓名就存在着一一

  • C++ 关于STL中sort()对struct排序的方法

    前言 一直没有系统去看过c++,因为懂得一些c的基本语法,在实际编程中用到c++,只能用到哪些看哪些,发现这样虽然能够完成大部分工作,但是有时候效率实在太低,比如说这节要讲的Std::sort()函数的使用,调了半天才调通.开通c/c++序列博客是记录在使用c++中一些难题,避免以后重犯错,当然以后会尽量挤出时间来较系统学习下c++. 开发环境:QtCreator2.5.1+OpenCV2.4.3 实验基础 首先来看看std中的快速排序算法sort的使用方法: template <class R

  • C++在成员函数中使用STL的find_if函数实例

    本文实例讲述了C++在成员函数中使用STL的find_if函数的方法.分享给大家供大家参考.具体方法分析如下: 一般来说,STL的find_if函数功能很强大,可以使用输入的函数替代等于操作符执行查找功能(这个网上有很多资料,我这里就不多说了). 比如查找一个数组中的奇数,可以用如下代码完成(具体参考这里:http://www.cplusplus.com/reference/algorithm/find_if/): #include <iostream> #include <algori

随机推荐