前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >C++拾取——使用stl标准库生成等差、等比数列的方法

C++拾取——使用stl标准库生成等差、等比数列的方法

作者头像
方亮
发布2020-08-02 22:13:43
1.8K0
发布2020-08-02 22:13:43
举报
文章被收录于专栏:方亮

代码是思想的表达。阅读代码是一个猜测、求证的过程。这个过程非常费脑,所以人们都不喜欢啰啰嗦嗦的表达方式。于是在相同认知水平下,简洁高效的表达是喜闻乐见的。本文将抛砖引玉,通过一些案例讲解如何去简化代码。(转载请指明出于breaksoftware的csdn博客)

关系数列

等差数列

        比如我们要构建的序列存储的值是0,1,2,3,4……9999。

常规写法

        使用for循环

代码语言:javascript
复制
std::vector<int> vec;
for (int i = 0; i < 10000; i++) {
    vec.push_back(i);
}

简洁写法

iota

        使用std标准库的iota。

代码语言:javascript
复制
std::vector<int> vec(10);
std::iota(vec.begin(), vec.end(), 0);

generate

        使用std标准库的generate

代码语言:javascript
复制
    std::vector<int> vec(10);
    std::generate(vec.begin(), vec.end(), [] {static int i = 0; return i++;});

        或者

代码语言:javascript
复制
    std::vector<int> vec(10);
    std::generate(vec.begin(), vec.end(), [n = 0]() mutable {return n++;});

partial_sum

        使用std标准库的partial_sum,代码量减少了一半。 partial是局部、区间的意思,sum是累加的意思。第1、2个参数是需要被计算的容器起止迭代器,第3个参数是计算结果保存的起始迭代器。它还有第4个参数,用于描述怎么计算的。

代码语言:javascript
复制
std::vector<int> vec(10000, 1);
vec[0] = 0;
std::partial_sum(vec.begin(), vec.end(), vec.begin());

        std::partial_sum方法对区间数据进行累加。具体的计算规则是

代码语言:javascript
复制
template< class InputIt, class OutputIt >
OutputIt partial_sum( InputIt first, InputIt last, OutputIt d_first );
// *(d_first)   = *first;
// *(d_first+1) = *first + *(first+1);
// *(d_first+2) = *first + *(first+1) + *(first+2);
// *(d_first+3) = *first + *(first+1) + *(first+2) + *(first+3);
// ...

        上述方法有个缺点,就是需要填充10000个1之后再计算。我们可以稍微修改如下,效率会好些。

代码语言:javascript
复制
std::vector<int> vec(10000);
vec[0] = 0;
std::partial_sum(vec.begin(), vec.end(), vec.begin(), [](const int&a, int b) {return a + 1;});

        如果要生成9999,9998……0这样递减的数列,则可以把第一个元素赋值为9999后,传递一个减法lambda表达式

代码语言:javascript
复制
std::vector<int> vec(10000);
vec[0] = 9999;
std::partial_sum(vec.begin(), vec.end(), vec.begin(), [](const int& a, int b) {return a - 1;} );

等比数列

        比如我们要生成1,2,4,8,16……这样2倍关系的数列。

常规写法

代码语言:javascript
复制
std::vector<int> vec;
for (int i = 0; i < 10; i++) {
    vec.push_back(pow(2, i));
}

精简写法

 generate

代码语言:javascript
复制
    std::vector<int> vec(10);
    std::generate(vec.begin(), vec.end(), [] {static int i = 0; return pow(2, i++);});

        或者

代码语言:javascript
复制
    std::vector<int> vec(10);
    std::generate(vec.begin(), vec.end(), [n = 0]() mutable {return pow(2, n++);});

partial_sum

代码语言:javascript
复制
std::vector<int> vec(10, 2);
vec[0] = 1;
std::partial_sum(vec.begin(), vec.end(), vec.begin(), std::multiplies<int>());

        使用比值2初始化vector容器,然后给partial_sum传递乘法函数对象。

        或者使用lambda表达式

代码语言:javascript
复制
std::vector<int> vec(10);
vec[0] = 1;
std::partial_sum(vec.begin(), vec.end(), vec.begin(), [](const int& x, int y) {return x * 2;});

        如果要生成512,256……2,1这样的等比数列,则可以把容器的第一个元素设置为1024,然后给partial_sum传递除法函数对象。

代码语言:javascript
复制
std::vector<int> vec(10, 2);
vec[0] = 512;
std::partial_sum(vec.begin(), vec.end(), vec.begin(), std::divides<int>());

        或者使用lambda表达式

代码语言:javascript
复制
std::vector<int> vec(10);
vec[0] = 512;
std::partial_sum(vec.begin(), vec.end(), vec.begin(), [](const int& x, int y) {return x / 2;});

斐波那契数列

常规写法

代码语言:javascript
复制
std::vector<int> vec(10);
vec[0] = 1;
for (auto it = std::next(vec.begin()); it != vec.end(); it++) {
    auto it_prev = std::prev(it);
    if (vec.begin() != it_prev) {
        *it = *it_prev + *std::prev(it_prev);
    }
    else {
        *it = *it_prev;
    }  
}

精简写法

代码语言:javascript
复制
std::vector<int> vec(10);
vec[0] = 1;
std::adjacent_difference(vec.begin(), std::prev(vec.end()), std::next(vec.begin()), std::plus<int>());

        adjacent_difference用于计算前后两个数据的差。第4个参数的默认操作是减法,其计算规则如下

代码语言:javascript
复制
template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2 >
ForwardIt2 adjacent_difference( ExecutionPolicy&& policy, ForwardIt1 first, ForwardIt1 last, ForwardIt2 d_first );
// *(d_first)   = *first;
// *(d_first+1) = *(first+1) - *(first);
// *(d_first+2) = *(first+2) - *(first+1);
// *(d_first+3) = *(first+3) - *(first+2);
// ...

累计型操作

        比较常见的累计型操作如累加、累乘

累加

常规写法

代码语言:javascript
复制
std::vector<int> vec = { 16, 8, 4 };
int sum = 0;
for (int n : vec) {
    sum += n;
}

精简写法

代码语言:javascript
复制
std::vector<int> vec = { 16, 8, 4 };
int sum = std::accumulate(vec.begin(), vec.end(), 0);

        代码也减少一半。

        accumulate第1、2个参数是需要计算的容器的起止迭代器,第3个参数是初始计算的值。它还有第4个参数,用于描述如何累计。默认是累加操作。

        我们再看个累乘操作。

代码语言:javascript
复制
std::vector<int> vec = { 16, 8, 4 };
int product = std::accumulate(vec.begin(), vec.end(), 1, std::multiplies<int>());

组合成一个字符串

常规写法

代码语言:javascript
复制
std::vector<int> vec = { 16, 8, 4 };
std::string str;
for (int n : vec) {
    if (!str.empty()) {
        str.append(",");
    }
    str.append(std::to_string(n));
}

精简写法

代码语言:javascript
复制
std::string s = std::accumulate(std::next(vec.begin()), vec.end(),
    std::to_string(vec[0]), // start with first element
    [](std::string a, int b) { return a + ',' + std::to_string(b);}
);

序列比较

两个序列中,相同偏移的元素值相等的个数

常规写法

代码语言:javascript
复制
std::vector<int> a = { 1, 2, 3, 4, 5 };
std::vector<int> b = { 5, 4, 3, 2, 1 };
int num = 0;
auto it_a = a.begin();
auto it_b = b.begin();
for (; it_a != a.end() && it_b != b.end(); it_a++, it_b++) {
    if (*it_a == *it_b) {
        num++;
    }
}

精简写法

代码语言:javascript
复制
std::vector<int> a = { 1, 2, 3, 4, 5 };
std::vector<int> b = { 5, 4, 3, 2, 1 };
int num = std::inner_product(a.begin(), a.end(), b.begin(), 0, std::plus<>(), std::equal_to<>());

        inner_product方法对两个序列中相同位置的元素使用第5个参数指向的函数对象计算,计算的结果通过第4个参数指向的函数对象进行再计算。即

代码语言:javascript
复制
template<class InputIt1, class InputIt2, class T,
         class BinaryOperation1, class BinaryOperation2> 
T inner_product( InputIt1 first1, InputIt1 last1,
                 InputIt2 first2, T init,
                 BinaryOperation1 op1,
                 BinaryOperation2 op2 );
// 以初值 init 初始化积累器 acc ,然后
// 以表达式 acc = op1(acc, op2(*first1, *first2)) 修改它,再以表达式acc = op1(acc, op2(*(first1+1), *(first2+1))) 修改它,以此类推

两个序列元素是否完全一致(顺序无关)

        比如一个序列a是1,2,3;序列b是2,1,3;序列c是1,2,1。则a和b中元素完全一致,只是顺序不一致;而c和a、b中元素不一致。可以想象这个算法不是简简单单就能写出来的。我们直接看精简写法

精简写法

代码语言:javascript
复制
std::vector<int> v1{ 1,1,2,2,5 };
std::vector<int> v2{ 5,1,2,1,2 };
bool permutation = std::is_permutation(v1.begin(), v1.end(), v2.begin(), v2.end());

        is_permutation用于判断两个序列是否是同一个序列的不同(或相同)顺序排列。

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2018/10/12 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 关系数列
    • 等差数列
      • 常规写法
      • 简洁写法
      • iota
      • generate
      • partial_sum
      • 等比数列
      • 常规写法
      • 精简写法
      •  generate
      • partial_sum
    • 斐波那契数列
      • 常规写法
      • 精简写法
  • 累计型操作
    • 累加
      • 常规写法
      • 精简写法
    • 组合成一个字符串
      • 常规写法
      • 精简写法
  • 序列比较
    • 两个序列中,相同偏移的元素值相等的个数
      • 常规写法
      • 精简写法
    • 两个序列元素是否完全一致(顺序无关)
      • 精简写法
相关产品与服务
容器服务
腾讯云容器服务(Tencent Kubernetes Engine, TKE)基于原生 kubernetes 提供以容器为核心的、高度可扩展的高性能容器管理服务,覆盖 Serverless、边缘计算、分布式云等多种业务部署场景,业内首创单个集群兼容多种计算节点的容器资源管理模式。同时产品作为云原生 Finops 领先布道者,主导开源项目Crane,全面助力客户实现资源优化、成本控制。
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档