花心胡萝卜 花心胡萝卜工作室 stl 算法

STL之算法(三)

复习

算法中, 接受的参数基本上都是迭代器.
迭代器作为一个承接的桥梁.

分区算法

is_partitioned

• 判定指定范围的容器的元素是否被分区整理了
• 不会改变容器的内容

#include <iostream>     // std::cout
#include <algorithm>    // std::is_partitioned
#include <array>        // std::array

bool IsOdd (int i) { return (i%2)==1; }

int main () {
  std::array<int,7> foo {1,2,3,4,5,6,7};

  // print contents:
  std::cout << "foo:"; for (int& x:foo) std::cout << ' ' << x;
  if ( std::is_partitioned(foo.begin(),foo.end(),IsOdd) )
    std::cout << " (partitioned)\n";
  else
    std::cout << " (not partitioned)\n";

  // partition array:
  std::partition (foo.begin(),foo.end(),IsOdd);

  // print contents again:
  std::cout << "foo:"; for (int& x:foo) std::cout << ' ' << x;
  if ( std::is_partitioned(foo.begin(),foo.end(),IsOdd) )
    std::cout << " (partitioned)\n";
  else
    std::cout << " (not partitioned)\n";

  return 0;
}

运行结果:
foo: 1 2 3 4 5 6 7 (not partitioned)
foo: 1 7 3 5 4 6 2 (partitioned)

partition

• 给指定范围的容器元素进行给定条件的分区整理
• 会改变容器的内容

stable_partition

• 稳定的分区整理, 效果同partition
• 不同的是, 元素的相对顺序不会进行改变

#include <iostream>
#include <algorithm>
#include <vector>

int main()
{
    std::vector<int> myvector;
    myvector.resize(10);
    std::generate(myvector.begin(), myvector.end(), []() { return rand() % 10; });
    std::cout << "myvector's orig data:";
    std::for_each(myvector.begin(), myvector.end(), [](int i) {std::cout << i << ","; });
    std::cout << "\n ----------------- \n";

    std::vector<int> vecPartition, vecSPartition;
    vecPartition = myvector;
    vecSPartition = myvector;

    auto iter = std::partition(vecPartition.begin(), vecPartition.end(), 
        [](int i) { return ((i % 2) == 1); });

    std::cout << "partition odd elements:";
    std::for_each(vecPartition.begin(), iter, [](int i) {std::cout << i << ","; });
    std::cout << '\n';

    std::cout << "partition even elements:";
    std::for_each(iter, vecPartition.end(), [](int i) {std::cout << i << ","; });
    std::cout << '\n';

    std::cout << "now vecPartition's data:";
    std::for_each(vecPartition.begin(), vecPartition.end(), [](int i) {std::cout << i << ","; });
    std::cout << "\n ----------------- \n";

    auto bound = std::stable_partition(vecSPartition.begin(), vecSPartition.end(),
        [](int i) { return ((i % 2) == 1); });

    std::cout << "stable_partition odd elements:";
    std::for_each(vecSPartition.begin(), bound, [](int i) {std::cout << i << ","; });
    std::cout << '\n';

    std::cout << "stable_partition even elements:";
    std::for_each(bound, vecSPartition.end(), [](int i) {std::cout << i << ","; });
    std::cout << '\n';

    std::cout << "now vecSPartition's data:";
    std::for_each(vecSPartition.begin(), vecSPartition.end(), [](int i) {std::cout << i << ","; });
    std::cout << '\n';

    return 0;
}

partition_copy

• 对指定范围的容器元素进行指定条件的分区整理, 并将结果形成对, 分别放到给定的位置中.
• 注意, 它会返回pair

partition_point

• 获取一个已经被分区过的范围的分区点的迭代器

排序算法

sort

• 全排序
• 对给定的范围进行指定条件的排序
• 在不指定排序方式的时候, 默认要求必须实现 operator<
• 在比较的时候会对数据进行移动
• 会改变容器的内容

stable_sort

• 稳定排序
• 对给定的范围进行指定条件的排序
• 在不指定排序方式的时候, 默认要求必须实现 operator<

• 不同于 sort, 本函数在相邻相同元素的时候不会进行(移动)交换

  • 11 11 12 15 14 14 13 13
  • 11 和 11 之间不会产生交换
  • 14 和 14 之间不会产生交换
  • 13 和 13 之间不会产生交换
• 效率较 sort 要高

partial_sort

• 局部(部分)排序

• 重新排列给定范围的元素, 使得中间之前的元素是整个范围中的最小元素, 并按升序排序, 而剩余的元素没有任何特定的顺序.

  • 也就是说, 排序之后, 拿前N个, N是指定的中间值
  • 中间值之前的是排序好的, 升序排列
  • 中间值后的, 顺序不变
• 效率最高

#include <iostream>
#include <algorithm>
#include <vector>

int main()
{
    std::vector<int> demoSort, demoPSort;
    demoSort.resize(20);
    demoPSort.resize(20);
    std::generate(demoSort.begin(), demoSort.end(), []() { return rand() % 40; });
    demoPSort = demoSort;
    std::sort(demoSort.begin(), demoSort.begin() + 10);
    std::partial_sort(demoPSort.begin(), demoPSort.begin() + 10, demoPSort.end());
    std::for_each(demoSort.begin(), demoSort.end(), [](int i) {std::cout << i << ","; });
    std::cout << std::endl;
    std::for_each(demoPSort.begin(), demoPSort.end(), [](int i) {std::cout << i << ","; });
    std::cout << "\n=========================" << std::endl;
    return 0;
}

partial_sort_copy

• 同局部排序, 只不过结果复制到指定的地方

is_sorted

• 判定指定范围是否是有序序列

is_sorted_until

• 返回指定范围内的第一个未被排序的元素的迭代器
• 默认的排序为 升序
• 可以指定排序函数

nth_element

• 让第N大的元素处于第N位
• 其他元素没有任何特定的顺序
• 第 N 个元素之前的任何元素都不大于它
• 它之后的元素都不小于它

#include <iostream>
#include <algorithm>
#include <vector>

int main()
{
    std::cout << "\n=========================" << std::endl;

    std::vector<int> demo;
    demo.resize(20);
    std::generate(demo.begin(), demo.end(), []() { return rand() % 40; });
    std::nth_element(demo.begin(), demo.begin() + 8, demo.end());
    std::for_each(demo.begin(), demo.end(), [](int i) {std::cout << i << ","; });

    return 0;
}

其他算法整理中......

未完待续...

如有错误,请提出指正!谢谢.

本文由 花心胡萝卜 创作，采用 知识共享署名4.0 国际许可协议进行许可
本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名
最后编辑时间为: 2017-04-14 at 04:12 pm