STL Note

keywords{set_intersection,set_union,set_difference,find,find_if,count,count_if,binary_serach等等}

本文整理了STL中的常用算法,例如集合运算,查找元素,统计元素,查找子区间,判断区间是否相等,全排列,堆排序,稳定排序,以及复制并排序,判断是否有序等。

  • No:1 集合
  • No:2 查找
  • No:3 排序

关于迭代器

阅读前请简单了解下迭代器。文章内容可能存在疏漏,欢迎指正,如果没有特别标注,内容基本符合C++11标准,C++98标准不支持的我知道的都标注出来了,建议你使用-std=c++11编译命令。

Input Iterator:输入迭代器。具有只读性质,只能单步向前迭代元素,不允许修改由该类迭代器引用的元素。

Output Iterator:输出迭代器。具有只写性质,该类迭代器和Input Iterator极其相似,也只能单步向前迭代元素,不同的是该类迭代器对元素只有写的权力。

Forward Iterator:具有读写性质

Bidirectional Iterator:支持双向移动

Random Access Iterator:提供了算术运算能力

更多内容请参阅

集合

  • 交集(set_intersection) A∩B

OutputIt set_intersection( InputIt1 first1, InputIt1 last1,InputIt2 first2, InputIt2 last2, OutputIt d_first );

  • 并集(set_union) A∪B

OutputIt set_union( InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2, OutputIt d_first );

  • 差集(set_difference) A−B

OutputIt set_difference( InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2, OutputIt d_first );

  • 对称差集(set_symmetric_difference) A∪B−(A∩B)

OutputIt set_symmetric_difference( InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2, OutputIt d_first );

使用方法:
简单说我们只需要提供五个参数,集合1的起始和结束位置,集合2的起始和结束位置,结果存放的起始位置。

函数返回最后一个结果元素的下一个位置。唯一需要注意的是集合1和集合2必须是按照同一种规则有序的,这样我们才能进行如上的运算,使用vector必须要先保证集合有序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <iostream>     // std::cout
#include <algorithm> // std::set_difference, std::sort
#include <vector> // std::vector

int main () {
int first[] = {5,10,15,20,25};
int second[] = {50,40,30,20,10};
std::vector<int> v(10);
// 0 0 0 0 0 0 0 0 0 0
std::vector<int>::iterator it;

std::sort (first,first+5); // 5 10 15 20 25
std::sort (second,second+5); // 10 20 30 40 50

it=std::set_difference (first, first+5, second, second+5, v.begin());
// 5 15 25 0 0 0 0 0 0 0
v.resize(it-v.begin());
//改变容器大小创建对象 // 5 15 25

std::cout << "The difference has " << (v.size()) << " elements:\n";
for (it=v.begin(); it!=v.end(); ++it)
std::cout << ' ' << *it;
std::cout << '\n';

return 0;
}

查找

  • std::find

InputIterator find (InputIterator first, InputIterator last, const T& val);

参数详解
给定查找开始,结束位置,给定查找值,返回第一个匹配的值位置,查找失败返回last

  • 有条件的查找std::find_if

InputIterator find_if(InputIterator first,InputIterator last,UnaryPredicate pred);

参数详解 UnaryPredicate pred可以以函数形式指定查找条件,函数的返回值为bool值。可以简单的判断奇偶数,素数等。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// find_if example
#include <iostream> // std::cout
#include <algorithm> // std::find_if
#include <vector> // std::vector

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

int main () {
std::vector<int> myvector;

myvector.push_back(10);
myvector.push_back(25);
myvector.push_back(40);
myvector.push_back(55);

std::vector<int>::iterator it = std::find_if (myvector.begin(), myvector.end(), IsOdd);
std::cout << "The first odd value is " << *it << '\n';

return 0;
}

  • 统计元素出现的次数 std::count

count (InputIterator first, InputIterator last, const T& val);

参数详解:
给定查找范围,和查找值,返回元素出现的位置

  • 有条件的统计元素出现次数 std::count_if

count_if (InputIterator first, InputIterator last, UnaryPredicate pred);

参数详解 UnaryPredicate pred可以以函数形式指定统计规则,函数的返回值为bool值。可以简单的统计奇偶数,素数的个数。

  • 查找第一个不小于给定元素的值 lower_bound()

ForwardIterator lower_bound (ForwardIterator first, ForwardIterator last, const T& val);

ForwardIterator lower_bound (ForwardIterator first, ForwardIterator last, const T& val, Compare comp);

  • 查找第一个大于给定元素的值 upper_bound()

ForwardIterator upper_bound (ForwardIterator first, ForwardIterator last, const T& val);

ForwardIterator upper_bound (ForwardIterator first, ForwardIterator last, const T& val, Compare comp);

  • 二分查找 binary_search()

bool binary_search (ForwardIterator first, ForwardIterator last, const T& val);

bool binary_search (ForwardIterator first, ForwardIterator last,const T& val, Compare comp);

  • 查找最小元素 min_element()

ForwardIterator min_element (ForwardIterator first, ForwardIterator last);

  • 查找最大元素 max_element()

ForwardIterator max_element (ForwardIterator first, ForwardIterator last);

  • 查找子区间首次出现的位置 search()

ForwardIterator1 search (ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2);

ForwardIterator1 search (ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate pred);

  • 查找子区间最后一次出现的位置 find_end()

ForwardIterator1 find_end (ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2);

ForwardIterator1 sfind_end (ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate pred);

  • 判断两个区间是否相等 equal()

bool equal (InputIterator1 first1, InputIterator1 last1,InputIterator2 first2);

  • 判断两个区间首次出现不同的位置 mismatch()

mismatch (InputIterator1 first1, InputIterator1 last1,InputIterator2 first2);

mismatch (InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, BinaryPredicate pred);

排序

  • 堆排序 sort_heap

void sort_heap (RandomAccessIterator first, RandomAccessIterator last);默认升序

void sort_heap (RandomAccessIterator first, RandomAccessIterator last, Compare comp);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
// range heap example
#include <iostream> // std::cout
#include <algorithm> // std::make_heap, std::pop_heap, std::push_heap, std::sort_heap
#include <vector> // std::vector

int main () {
int myints[] = {10,20,30,5,15};
std::vector<int> v(myints,myints+5);

std::make_heap (v.begin(),v.end());
std::cout << "initial max heap : " << v.front() << '\n';

std::pop_heap (v.begin(),v.end()); v.pop_back();
std::cout << "max heap after pop : " << v.front() << '\n';

v.push_back(99); std::push_heap (v.begin(),v.end());
std::cout << "max heap after push: " << v.front() << '\n';

std::sort_heap (v.begin(),v.end());

std::cout << "final sorted range :";
for (unsigned i=0; i<v.size(); i++)
std::cout << ' ' << v[i];

std::cout << '\n';

return 0;
}
  • 稳定排序 stable_sort

void stable_sort ( RandomAccessIterator first, RandomAccessIterator last );

void stable_sort ( RandomAccessIterator first, RandomAccessIterator last, Compare comp );

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
// stable_sort example
#include <iostream> // std::cout
#include <algorithm> // std::stable_sort
#include <vector> // std::vector

bool compare_as_ints (double i,double j)
{
return (int(i)<int(j));
}

int main () {
double mydoubles[] = {3.14, 1.41, 2.72, 4.67, 1.73, 1.32, 1.62, 2.58};

std::vector<double> myvector;

myvector.assign(mydoubles,mydoubles+8);

std::cout << "using default comparison:";
std::stable_sort (myvector.begin(), myvector.end());
for (std::vector<double>::iterator it=myvector.begin(); it!=myvector.end(); ++it)
std::cout << ' ' << *it;
std::cout << '\n';

myvector.assign(mydoubles,mydoubles+8);

std::cout << "using 'compare_as_ints' :";
std::stable_sort (myvector.begin(), myvector.end(), compare_as_ints);
for (std::vector<double>::iterator it=myvector.begin(); it!=myvector.end(); ++it)
std::cout << ' ' << *it;
std::cout << '\n';

return 0;
}
  • 判断是否有序 is_sorted 确保编译器支持c++11

bool is_sorted (ForwardIterator first, ForwardIterator last);

bool is_sorted (ForwardIterator first, ForwardIterator last, Compare comp);

  • 复制区间并排序 partial_sort_copy

RandomAccessIterator partial_sort_copy (InputIterator first,InputIterator last,RandomAccessIterator result_first,RandomAccessIterator result_last);

RandomAccessIterator partial_sort_copy (InputIterator first,InputIterator last,RandomAccessIterator result_first,RandomAccessIterator result_last, Compare comp);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
// partial_sort_copy example
#include <iostream> // std::cout
#include <algorithm> // std::partial_sort_copy
#include <vector> // std::vector

bool myfunction (int i,int j) { return (i<j); }

int main () {
int myints[] = {9,8,7,6,5,4,3,2,1};
std::vector<int> myvector (5);

// using default comparison (operator <):
std::partial_sort_copy (myints, myints+9, myvector.begin(), myvector.end());

// using function as comp
std::partial_sort_copy (myints, myints+9, myvector.begin(), myvector.end(), myfunction);

// print out content:
std::cout << "myvector contains:";
for (std::vector<int>::iterator it=myvector.begin(); it!=myvector.end(); ++it)
std::cout << ' ' << *it;
std::cout << '\n';

return 0;
}
Author: Junzhou Liu
Link: https://liujunzhou.top/2019/3/11/week3-4-stl-note/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.
AliPay
WechatPay