精华内容
下载资源
问答
  • C++ STL算法

    2019-12-22 16:37:51
    ,使用STL算法时,常常用到函数对象和函数适配器,因此需要<functional> 算法概述 两个特殊后缀: 1.后缀_if 2.后缀_copy 按照功能来分类: 1.非更易型算法 2.更易型算法 3.移除型算法 4...

    头文件<algorithm>、<numeric>、<functional>

    某些算法需要数值处理,因此需要<numeric>,使用STL算法时,常常用到函数对象和函数适配器,因此需要<functional>

    算法概述

    两个特殊后缀:

    1.后缀_if

    2.后缀_copy

    按照功能来分类:

    1.非更易型算法

    2.更易型算法

    3.移除型算法

    4.变序型算法

    5.排序算法

    6.已排序区间算法

    7.数值算法

    非更易型算法

    非更易型算法既不改动元素次序,也不改动元素值.通过input迭代器和forward迭代器完成工作.渴作用域所有标准容器身上

    在这里插入图片描述

    更易型算法

    更易型算法,要么直接改变元素值,就是在复制元素到另一区间的过程中改变元素值.

    在这里插入图片描述

    最基本的更易型算法是for_each()和transform():

    移除型算法

    在这里插入图片描述

    注意,移除型算法只是逻辑上移除元素,其手段是:将不应移除的元素往前覆盖应被移除的元素,因此它并不改变操作区间内的元素个数,而是返回逻辑上的新终点位置.

    变序型算法

    在这里插入图片描述

    所谓的变序指的是通过元素值的赋值和互换,改变元素顺序,但不改变元素值

    排序算法

    在这里插入图片描述

    排序算法是一种特殊的变序型算法,它们也改变元素的顺序.但它们更复杂,也花费更多时间

    如果要考虑对所有元素排序,可考虑以下算法:

    sort():采用快速排序算法,保证了很好的平均效能,复杂度为n x log(n)

    partial_sort():一般采用的是堆排序算法,在任何情况下保证n x log(n)的复杂度,然而很多实际情况中比堆排序比快速排序慢2~5倍.

    partial_sort()的优点是它在任何时候都保证n x log(n)复杂度,绝不会变成二次复杂度,

    sort()在最差情况下有可能编程二次复杂度

    partial_sort()还有一种特殊能力:如果你只需要前n个元素排序,它可以在任务完成立即停止.如果想对所有元素排序,可以将序列重点作为第二实参是最后一个实参:

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

    stable_sort():传统上采用了归并排序,它对所有元素进行了排序,只有在内存充足的前提下它才有n x log(n)复杂度,否则复杂度为 n x log(n) x log(n),它的优点是保持相等元素之间的相对次序

    检验是否排序算法

    在这里插入图片描述

    已排序区间算法

    已排序区间算法指的是:其作用的区间在某种排序准则下已经排序

    在这里插入图片描述

    数值算法

    数值算法以各种不同的方式结合数值元素:

    在这里插入图片描述

    展开全文
  • C++ STL 算法

    2018-09-19 23:36:53
    STL算法种类: 1.非修改式序列操作,find(),for_each() 2.修改式序列操作,transform(),random_shuffle(),copy() 3.排序和相关操作,sort() 4.通用数字运算 前3种在头文件algorithm中,最...

    STL中所谓算法是用来处理容器的非成员函数,有两个通用部分:

    1.模板:提供数据的泛型

    2.迭代器:提供访问容器值的通用表示

    STL算法种类:

    1.非修改式序列操作,find(),for_each()

    2.修改式序列操作,transform(),random_shuffle(),copy()

    3.排序和相关操作,sort()

    4.通用数字运算

    前3种在头文件algorithm中,最后一种在头文件numeric中

    就地算法:结果放在原始数据的位置,例如sort

    复制算法:将结果发送到其他位置,例如copy

    很多算法有两个版本,STL规定,以_copy结尾的是复制版本,复制版本返回一个迭代器,指向最后一次复制的值的后面一个位置,例如对于replace算法:

    /* 将old用new替换,同时读写,所以至少是正向迭代器 */
    template<typename ForwardIterator, typename T>
    void replace(ForwardIterator first, ForwardIterator last, 
            const T & old, const T & new);
    
    /* 复制到另一个地址,所以区分输入迭代器和输出迭代器,注意返回值 */
    template<typename InputIterator, typename OutputIterator, typename T>
    OutputIterator replace_copy(InputIterator first, InputIterator last,
            OutputIterator result, const T & old, const T & new);

    _if后缀:有些算法根据提供的函数符对容器元素进行操作的结果来执行操作,例如replace_if,如下:

    /* Predicate是一元谓词,这里对旧值应用这个谓词,若返回true,那么替换成新值 */
    template<typename ForwardIterator, typename Predicate, typename T>
    void remove_if(ForwardIterator first, ForwardIterator last, Predicate pred,
            const T & new_value);

    next_permutation()算法:提供唯一的排列组合,顺序是字典序

    算法和容器的成员函数:应该尽量使用容器的成员函数,两个原因:

    1.成员函数对特定容器性能好

    2.成员函数有权力管理容器的内存,可以动态管理大小

    使用算法的场景:混合容器,例如将vector容器存储到链表或集合中

    展开全文
  • C++STL算法

    2012-02-29 22:37:18
    说完了排序算法接下来就剩下数值算法(numeric algorithms)了. iota 将一组递增的值赋值给迭代器区间内的元素 #include #include #include using namespace std; void print(int x){  cout } int main...

    说完了排序算法接下来就剩下数值算法(numeric algorithms).

    iota

    将一组递增的值赋值给迭代器区间内的元素

    #include <numeric>

    #include <algorithm>

    #include <iostream>

    using namespace std;

    void print(int x){

           cout << x << ' ';

    }

    int main(void){

           int iArray[10];

           iota(iArray, iArray+10, 0);

           for_each(iArray, iArray+10, print);

           cout << endl;

           return 0;

    }

    accumulate

    可以将区间的元素进行累计求和,或者你可以DIY一个累计求积之类的功能

    #include <numeric>

    #include <iostream>

    using namespace std;

    int multiply(int x, int y){

           return x * y;

    }

    int main(void){

           int iArray[5]={1, 2, 3, 4, 5};

           cout << "数组iArray的元素和为"

                  << accumulate(iArray, iArray+5, 0)

                  << endl;

           cout << "数组iArray的元素乘积为"

                  << accumulate(iArray, iArray+5, 1, multiply)

                  << endl;

           return 0;

    }

    inner_product

    对两个区间内的元素进行累积计算,类似于上面也可以自己DIY一些功能出来

    #include <numeric>

    #include <iostream>

    int add(int x, int y){

           return x + y;

    }

    int mul(int x, int y){

           return x * y;

    }

    int main(void){

           using namespace std;

           int iArray1[3]={2, 5, 4};

           int iArray2[3]={10, 6, 5};

           //用原型1计算内积

           int result=inner_product(iArray1, iArray1 + 3, iArray2, 0);

           cout << "数组iArray1与数组iArray2的内积为" << result << endl;

           //用原型2计算内积

           result=inner_product(iArray1, iArray1 +3, iArray2, 0, add, mul);

           cout << "数组iArray1与数组iArray2的内积为" << result << endl;

           return 0;

    }

    partial_sum

    对区间元素进行局部求和,当然也支持DIY

    #include <numeric>

    #include <algorithm>

    #include <iostream>

    using namespace std;

    void print(int x){

           cout << x << ' ';

    }

    int multiply(int x, int y){

           return x * y;

    }

    int main(void){

           int iArray[5]={1, 2, 3, 4, 5};

           int iResult[5];

           //求和

           partial_sum(iArray, iArray+5, iResult);

           for_each(iResult, iResult+5, print);

           cout << endl;

           //计算阶乘

           partial_sum(iArray, iArray+5, iResult, multiply);

           for_each(iResult, iResult+5, print);

           cout << endl;

           return 0;

    }

    adjacent_difference

    对相邻元素求差

    power

    用于进行n次方的计算


    v1.insert(v1.end(), v2.begin(), v2.end() );


    转载:http://hi.baidu.com/642168618/blog/item/70b59460a67cded38cb10d02.html

    展开全文
  • C++ stl算法汇总 STL 各种算法 应用 大全
  • C++ STL算法实现大数计算,VS2005可编译通过,解决溢出问题
  • C++ STL算法系列之swap

    2016-08-19 20:49:06
    转载出处:简单的程序诠释C++ STL算法系列之十五:swap  相信大家看到swap这个词都一定不会感到陌生,甚至会有这样想法:这不就是简单的元素交换嘛。的确,swap交换函数是仅次于Hello word这样老得不能老的词,...

    转载出处:简单的程序诠释C++ STL算法系列之十五:swap

     相信大家看到swap这个词都一定不会感到陌生,甚至会有这样想法:这不就是简单的元素交换嘛。的确,swap交换函数是仅次于Hello word这样老得不能老的词,然而,泛型算法东风,这个小小的玩意儿却在C++ STL中散发着无穷的魅力。本文不仅详细地阐述STL泛型算法swap,并借助泛型算法这股东风,展现STL容器中swap成员函数的神奇魅力。注意哦,泛型算法swap和容器中的swap成员函数,这是两个不同角度和概念哦!

         一、泛型算法swap

          老规矩,我们先来看看swap的函数原型:

    [cpp] view plain copy
    1. template <class T> void swap ( T& a, T& b )  
    2. {  
    3.   T c(a); a=b; b=c;  
    4. }  
    5.    
          函数原型超级简单吧,这里我们就不做过多的解释啦,下面我们还是通过一个简单的示例来熟悉熟悉它的使用吧。

          程序示例:

    [cpp] view plain copy
    1. /******************************************************************* 
    2.  * Copyright (C) Jerry Jiang 
    3.  *                
    4.  * File Name   : swap.cpp 
    5.  * Author      : Jerry Jiang 
    6.  * Create Time : 2012-3-24 4:19:31 
    7.  * Mail        : jbiaojerry@gmail.com 
    8.  * Blog        : http://blog.csdn.net/jerryjbiao  
    9.  *                
    10.  * Description : 简单的程序诠释C++ STL算法系列之十五                   
    11.  *               变易算法 : 元素交换swap    
    12.  *                
    13.  ******************************************************************/  
    14.   
    15. #include <iostream>  
    16. #include <algorithm>  
    17. #include <vector>  
    18. #include <iterator>  
    19.   
    20. using namespace std;  
    21.   
    22. int main ()   
    23. {  
    24.       
    25.     int x = 10, y = 20;                         // x:10 y:20  
    26.     swap(x, y);                              // x:20 y:10  
    27.       
    28.     vector<int> first (4, x), second (6, y);  // first:4x20 second:6x10  
    29.     swap(first, second);                     // first:6x10 second:4x20  
    30.       
    31.     cout << "first contains:";  
    32.     //使用一般的iterator方式输出first  
    33.     for (vector<int>::iterator it=first.begin();  it != first.end(); ++it)  
    34.     {  
    35.         cout << " " << *it;  
    36.     }  
    37.     cout << endl;  
    38.   
    39.     cout << "second contains: ";  
    40.     //使用copy()来实现second的输出  
    41.     copy(second.begin(), second.end(), ostream_iterator<int>(cout, " "));  
    42.     cout << endl;  
    43.       
    44.     return 0;  
    45. }  
              上面示例程序十分简单,只是为了巩固前文中copy算法的使用,我在程序中采用了两种方式进行输出,好了,泛型算法swap我们就不再废话了,现在我们来看看本文中的重头戏吧。

            二、容器中的成员函数swap

            在容器vector中,其内存占用的空间是只增不减的,比如说首先分配了10,000个字节,然后erase掉后面9,999个,则虽然有效元素只有一个,但是内存占用仍为10,000个。所有内存空间在vector析构时回收。

         一般,我们都会通过vector中成员函数clear进行一些清除操作,但它清除的是所有的元素,使vector的大小减少至0,却不能减小vector占用的内存。要避免vector持有它不再需要的内存,这就需要一种方法来使得它从曾经的容量减少至它现在需要的容量,这样减少容量的方法被称为“收缩到合适(shrink to fit)”。(节选自《Effective STL》)如果做到“收缩到合适”呢,嘿嘿,这就要全仰仗“Swap大侠”啦,即通过如下代码进行释放过剩的容量:

    [cpp] view plain copy
    1. vector< T >().swap(X)  
            下面我们通过一个简单的示例来show一下:

    [cpp] view plain copy
    1. /******************************************************************* 
    2.  * Copyright (C) Jerry Jiang 
    3.  *                
    4.  * File Name   : swap.cpp 
    5.  * Author      : Jerry Jiang 
    6.  * Create Time : 2012-3-24 4:19:31 
    7.  * Mail        : jbiaojerry@gmail.com 
    8.  * Blog        : http://blog.csdn.net/jerryjbiao  
    9.  *                
    10.  * Description : 简单的程序诠释C++ STL算法系列之十五                   
    11.  *               成员函数swap实现容器的内存释放    
    12.  *                
    13.  ******************************************************************/  
    14.   
    15. #include <iostream>  
    16. #include <algorithm>  
    17. #include <vector>  
    18. #include <iterator>  
    19.   
    20. using namespace std;  
    21.   
    22. int main ()   
    23. {  
    24.     int x = 10;  
    25.     vector<int> myvector(10000, x);    
    26.   
    27.     //这里打印仅仅是元素的个数不是内存大小  
    28.     cout << "myvector size:"  
    29.          << myvector.size()  
    30.          << endl;  
    31.   
    32.     //swap交换函数释放内存:vector<T>().swap(X);  
    33.     //T:int ; myvertor代表X  
    34.     vector<int>().swap(myvector);  
    35.   
    36.     //两个输出仅用来表示swap前后的变化  
    37.     cout << "after swap :"  
    38.          << myvector.size()  
    39.          << endl;  
    40.   
    41.     return 0;  
    42. }  
    swap交换技巧实现内存释放思想:vector()使用vector的默认构造函数建立临时vector对象,再在该临时对象上调用swap成员,swap调用之后对象myvector占用的空间就等于一个默认构造的对象的大小,临时对象就具有原来对象v的大小,而该临时对象随即就会被析构,从而其占用的空间也被释放。

    std::vector<T>().swap(X)

    作用相当于:

    {

    std::vector<T>  temp(X);

    temp.swap(X);

    }

        注意:并不是所有的STL容器的clear成员函数的行为都和vector一样。事实上,其他容器的clear成员函数都会释放其内存。比如另一个和vector类似的顺序容器deque。

     

    展开全文
  • 原创链接:C++ STL算法系列count函数 count和count_if函数是计数函数,先来看一下count函数:count函数的功能是:统计容器中等于value元素的个数。先看一下函数的参数:count(first,last,value); first是容器的首...
  • C++ STL 算法精选之查找篇

    千次阅读 2013-08-19 16:56:55
    C++ STL 算法精选之查找篇
  • C++ STL算法之:copy

    千次阅读 2016-04-26 11:16:38
    C++ STL算法:copy 目录(?)[+]  前面十二个算法所展现的都属于非变易算法(Non-mutating algorithms)系列,现在我们来看看变易算法。所谓变易算法(Mutating algorithms)就是一组能够修改...
  • c++STL算法总结

    千次阅读 2020-02-15 19:49:09
    算法函数 numeric 数值算法 functiona 函数对象/仿函数 分类 No. 分类 说明 解释 1 非可变序列算法 Non-modifying sequence operations 不直接修改容器内容的算法。 2 可变序列算法 Modifying ...
  • c++stl算法技术

    2013-04-11 23:16:10
    非变异算法是一组不破坏操作数据的模板函数,用来对序列数据进行逐个处理、元素查找、子序列搜索、统计和匹配。非变异算法具有极为广泛的适用性,基本上可应用与各种容器。
  • C++ STL算法系列6---copy函数   现在我们来看看变易算法。所谓变易算法(Mutating algorithms)就是一组能够修改容器元素数据的模板函数,可进行序列数据的复制,变换等。 我们现在来看看第一个变易算法:元素...
  • unique的作用 答:去除相邻的重复元素。所以使用前最好先对容器内容进行排序,使用时应包含头文件algorithm,打开命名空间std unique(iterator1,iterator2)的使用例子 #include<iostream> ...
  • C++ STL算法系列3---求和:accumulate    该算法在numeric头文件中定义。 假设vec是一个int型的vector对象,下面的代码: //sum the elements in vec starting the summation with the value 42 int sum =...
  • 函数swap()用来交换两对象的值,其泛型版本定义于algorithm头文件中,使用时需要打开命名空间std。 template<class T> inline void swap(T&a,T&b) { T temp(a);...注意:swap()中T所依赖的构造函数和...
  • C++STL算法简述

    2016-12-15 19:36:37
    标准库定义了超过100个算法,想要高效的使用这些算法需要了解他们的结构而不是单纯记忆每个算法的细节,以下是算法框架的描述和理解:1、beg和end是表示元素范围的迭代器,几乎每个算法都对应一个由beg和end表示的...
  • C++ STL算法系列1---count函数   一.count函数 algorithm头文件定义了一个count的函数,其功能类似于find。这个函数使用一对迭代器和一个值做参数,返回这个值出现次数的统计结果。 编写程序读取一系列int型...
  • C++ stl算法——partition

    千次阅读 2018-02-06 11:28:32
    函数声明template, class UnaryPredicate > ForwardIt partition( ForwardIt first, ForwardIt last, UnaryPredicate p );作用对[first, last)元素进行处理,使得满足p的元素移到[first, last)前部,不满足的移到...
  • C++ STL 算法简介

    2015-02-16 10:52:22
    1、100多种算法 2、函数对象(function objects):重载函数调用操作符的类,其对象常称为函数对象(function object),即它们是行为类似函数的对象。 3、函数适配器(function adapters):标准库提供了一组函数...
  • 一、swap_ranges(b,e,b2) 例: swap_ranges(ivec.begin(), ivec.end(), ideq.begin()); swap_ranges(ideq.begin(), ideq....二、注意: 下列两种方法也是交换算法 1.容器的swap()成员函数 ivec1.swap(ivec2);//
  • 1、replace(b,e,ov,nv) replace(ilist.begin(), ilist.end(), 6, 42); 2、replace_if(b,e,p,v) replace_if(ilist.begin(), ilist.end(),bind2nd(less(),5),0); 3、replace_copy(b1,e1,b2,ov,nv...replace_copy
  • equal(beg,end,cmpbeg)和equal(beg,end,cmpbeg,op)的特点 1:迭代器类型:输入迭代器 2:无op版本,判断区间[beg,end)内的元素是否都与cmpbeg开头的区间内的对应元素相等,注意cmpbeg开头的区间内的元素不能少于[beg...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 9,968
精华内容 3,987
关键字:

c++stl算法

c++ 订阅