[C++ Library] Algorithm

Tips : Upper can see easily than stare at the lower

出于背景的明暗层次，有时候在上半页的文字会更容易分辨一些

Sort [ 2 + 1 ]

经典库函数sort，蒟蒻必备工具
Arranges the elements in a specified range into a non-descending order or according to an ordering criterion specified (指定标准) by a binary predicate (二元谓词)

形参定义如下：

The begin of Vector
The length of Vector
Comp [Optional]

通常填写数组的首地址 or Vector -> begin( )

The one being the point of the vector from where the sorting needs to begin

填写数组的长度[arr + n] or Vector -> end( )

The second parameter being the length up to which we want the vector to get sorted

可选形参，用于制定比较规则

The third parameter is optional and can be used in cases for comp

缺省值为升序

By default，the sort function sorts the elements in ascending order

If the equivalent elements exist , try stable_sort instead
It can be called as ‘Introsort’ combine QuickSort \ HeapSort \ InsertionSort
Tips: Sort by Vector’s Subscript

#include <functional> -> greater<int>( )
int arr[ ] = { 0, 1, 5, 8, 9, 6, 7, 3, 4, 2 };
int n = sizeof(arr) / sizeof(arr[0]);
sort(arr + 2, arr + n);  // default std::less<int>( ) -> ascending order 
sort(arr + 2, arr + n, greater<int>( )) -> descending order

C++

We can also write our own comparator function and pass it as a third parameter.
This comparator function also be called as ‘binary predicate’

convertible to bool
returns a value whether the passed “first” argument should be placed before the passed “second” argument or not

bool compareInterval(Interval i1, Interval i2){
    return (i1.start < i2.start);
}
...
Interval arr[] = { { 6, 8 }, { 1, 9 }, { 2, 4 }, { 4, 7 } };
int n = sizeof(arr) / sizeof(arr[0]);
sort(arr, arr + n, compareInterval);

C++

Why do we use the term “non-descending” instead of “ascending” in sort algorithm ?

non-ascending and non-descending include the possibility of adjacent equal
for [1,2,2] ‘s attribute is non-descending not ascending

Also we have these sort below

sort_heap ( make_heap first ) -> the same usage of sort ( contain non-stable )
stable_partition -> divide array by comparator with origin order
stable_sort -> same of sort but stable -> slow than sort

Swap [ 2 ]

库函数三大交换第一个，交换两个整体

vector<int> v1, v2;
swap( v1, v2 );

C++

Swap_ranges [ 3 ]

库函数三大交换第二个，将前两个形参指向的vector范围用第三个形参的对应vector范围替代

vector<int> v1;
deque<int> d1;
swap_ranges ( v1.begin( ), v1.end( ), d1.begin( ) );

C++

iter_swap [ 2 ]

库函数三大交换第三个，通过迭代器交换元素

void selection_sort(ForwardIt begin, ForwardIt end)
{
    for (ForwardIt it = begin; it != end; ++it)
        std::iter_swap(it, std::min_element(it, end));
}

C++

Unique [ 2 + 1 ]

消除相邻相同元素，可通过循环sort + unique实现全不相同
可选形参用以形容“相同”

bool mod_equal ( int elem1, int elem2 ){
	if ( elem1 < 0 )
		elem1 = - elem1;
	if ( elem2 < 0 )
		elem2 = - elem2;
	return elem1 == elem2;
};
...
v1_NewEnd1 = unique ( v1.begin( ), v1.end( ) );
v1_NewEnd2 = unique ( v1.begin( ), v1_NewEnd1 , mod_equal );
v1_NewEnd3 = unique ( v1.begin( ), v1_NewEnd2, greater<int>( ) );

vector<int> vec;
sort(vec.begin(), vec.end());
vec.erase(unique(vec.begin(), vec.end()), vec.end());

C++

Unique_copy [ 3 + 1 ]

采用copy形式的unique，适合两个容器间数据处理

bool mod_equal ( int elem1, int elem2 ){
	if ( elem1 < 0 )
		elem1 = - elem1;
	if ( elem2 < 0 )
		elem2 = - elem2;
	return elem1 == elem2;
};
...
v1_NewEnd1 = unique_copy ( v1.begin( ), v1.begin( ) + 8, v1.begin( ) + 8 );
v1_NewEnd2 = unique_copy ( v1.begin( ), v1.begin( ) + 14,
	v1.begin( ) + 14 , mod_equal );

std::string s1 {"The      string    with many       spaces!"};  
std::string s2;
std::unique_copy(s1.begin(), s1.end(), std::back_inserter(s2),
                     [](char c1, char c2) { return c1 == ' ' && c2 == ' '; });

C++

Upper_bound [ 3 + 1 ]

找到给定vector中比val大的第一个数，可选参数定义“大”
Finds the position of the first element in an ordered range that has a value that’s greater than a specified value.
A binary predicate specifies the ordering criterion (指定排序标准).

Also we have lower_bound

bool mod_lesser( int elem1, int elem2 ){
	if ( elem1 < 0 )
		elem1 = - elem1;
	if ( elem2 < 0 )
		elem2 = - elem2;
	return elem1 < elem2;
}
...
sort(v1.begin(), v1.end());
sort(v2.begin(), v2.end(), greater<int>());
sort(v3.begin(), v3.end(), mod_lesser);
Result = upper_bound(v1.begin(), v1.end(), 3);
Result = upper_bound(v2.begin(), v2.end(), 3, greater<int>());
Result = upper_bound(v3.begin(), v3.end(), 3, mod_lesser);

Starting vector v1 = ( -1 0 1 2 3 4 -3 -2 -1 0 ).
Original vector v1 with range sorted by the
 binary predicate less than is v1 = ( -3 -2 -1 -1 0 0 1 2 3 4 ).
Original vector v2 with range sorted by the
 binary predicate greater is v2 = ( 4 3 2 1 0 0 -1 -1 -2 -3 ).
Original vector v3 with range sorted by the
 binary predicate mod_lesser is v3 = ( 0 0 -1 -1 1 -2 2 -3 3 4 ).
The upper_bound in v1 for the element with a value of 3 is: 4.
The upper_bound in v2 for the element with a value of 3 is: 2.
The upper_bound in v3 for the element with a value of 3 is: 4.

// 对于v1，upper_bound 在 v1 中找到第一个大于3的元素，也就是4。
// 对于v2，由于使用 greater<int>() 作为排序谓词，upper_bound 实际上在查找小于3的第一个元素的位置，即2。
// 对于v3，使用自定义的 mod_lesser 谓词进行排序，upper_bound 实际上在查找大于3的第一个元素，即4。

C++

Adjacent_find [ 2 + 1 ]

找到vector中相邻相同的数，可选形参定义“相同”
Searches for two adjacent elements that are either equal or satisfy a specified condition.

bool twice (int elem1, int elem2 ){
	return elem1 * 2 == elem2;
}
...
result1 = adjacent_find( L.begin( ), L.end( ) );
result2 = adjacent_find( L.begin( ), L.end( ), twice );

L = ( 50 40 10 20 20 )
There are two adjacent elements that are equal.
They have a value of 20.
There are two adjacent elements where the second is twice the first.
They have values of 10 & 20.

C++

Fill [ 3 ]

填充函数

vector<int> v1;
fill( v1.begin( ) + 5, v1.end( ), 2 );

C++

Fill_n [ 3 ]

填充函数，第二个形参填写填充的个数

vector<int> v1;
fill( v1.begin( ), 5, 2 );

C++

Is_permutation [ 4 + 1 ]

全相等函数
Returns true if both ranges contain the same elements, whether or not the elements are in the same order

Also, we have「 is_function」such as:
is_heap -> is_heap_until
is_partitioned
is_sorted -> is_sorted_until

cout << is_permutation(vec_3.begin(), vec_3.end(),
	vec_4.begin(), vec_4.end(),
	[](int lhs, int rhs) { return lhs % 2 == rhs % 2; }) << endl; // true

C++

Max [ 2 + 1 ]

Compare two element \ array \ expression

bool abs_greater ( int elem1, int elem2 ){
	if ( elem1 < 0 )
		elem1 = -elem1;
	if ( elem2 < 0 )
		elem2 = -elem2;
	return elem1 < elem2;
};
...
	const int& result1 = max(a, b, abs_greater);
const int& result2 = max(a, b);

vector<int> v1, v2;
v4 = max ( v1, v2 );

C++

Max_element [ 2 + 1 ]

取最大元素
Finds the first occurrence of largest element in a specified range where the ordering criterion may be specified by a binary predicate

Also, we have min and min_element
Even, we can use minmax and minmax_element which return pair(min(), max())

bool mod_lesser ( int elem1, int elem2 ){
	if ( elem1 < 0 )
		elem1 = - elem1;
	if ( elem2 < 0 )
		elem2 = - elem2;
	return elem1 < elem2;
};
...
v1_R1_Iter = max_element ( v1.begin( ), v1.end( ) );
v1_R2_Iter = max_element ( v1.begin( ), v1.end( ), mod_lesser);

C++

Merge [ 5 + 1 ]

将两个子vector排序合并入一个新vector，可选形参定义“大小”
Combines all of the elements from two sorted source ranges into a single, sorted destination range, where the ordering criterion may be specified by a binary predicate

merge ( v1a.begin( ), v1a.end( ), v1b.begin( ), v1b.end( ), v1.begin( ) );
merge ( v2a.begin( ), v2a.end( ), v2b.begin( ), v2b.end( ),
        v2.begin( ), greater<int>( ) );
merge ( v3a.begin( ), v3a.end( ), v3b.begin( ), v3b.end( ),
        v3.begin( ), mod_lesser );

C++

Next_permutation [ 2 + 1 ]

经典全排列函数
Reorders the elements in a range so that the original ordering is replaced by the lexicographically next greater permutation if it exists. The sense of lexicographically next may be specified with a binary predicate

bool deq1Result;
deq1Result = next_permutation ( deq1.begin( ), deq1.end( ) );
next_permutation ( v1.begin( ), v1.end( ), mod_lesser );

std::vector<int> elements = {1, 2, 3, 4};
do {
    // 在这里处理当前排列
    for (int element : elements) {
        std::cout << element << ' ';
    }
    std::cout << std::endl;
} while (std::next_permutation(elements.begin(), elements.end()));

C++

Nth_element [ 3 + 1 ]

说人话就是求第N小（缺省为小），本质上是插入排序的简化，不保证完全排序
形参为vector首地址、第N小对应位（第二小就是 v.ebgin() + 1）、末地址
可选形参定义“小”
Partitions a range of elements, correctly locating the nth element of the sequence in the range that meets these criteria: All the elements in front of it are less than or equal to it, and all the elements that follow it are greater than or equal to it

nth_element(v1.begin( ), v1.begin( ) + 3, v1.end( ) );
nth_element( v1.begin( ), v1.begin( ) + 4, v1.end( ),greater<int>( ) );
nth_element( v1.begin( ), v1.begin( ) + 5, v1.end( ), UDgreater );

std::nth_element(v.begin(), v.begin() + 1, v.end(), std::greater{});
std::cout << "\nThe second largest element is " << v[1] << '\n';
std::cout << "The largest element is " << v[0] << '\n';
printVec(v);

The second largest element is 9
The largest element is 10
v = {10, 9, 6, 7, 6, 3, 5, 4, 3, 2};

C++

Rotate [ 3 ]

本意为旋转，指定从第二形参作为新的头部，将1 – 2之间的内容拼接到尾部
Exchanges the elements in two adjacent ranges

rotate ( d1.begin( ), d1.begin( ) + 1 , d1.end( ) );
( 1 2 3 4 5 0 ) -> ( 2 3 4 5 0 1 )

C++

[C++ Library] Algorithm

Sort [ 2 + 1 ]

The begin of Vector

The length of Vector

Comp [Optional]

通常填写数组的首地址 or Vector -> begin( )

填写数组的长度[arr + n] or Vector -> end( )

可选形参，用于制定比较规则

缺省值为升序

Why do we use the term “non-descending” instead of “ascending” in sort algorithm ?

Swap [ 2 ]

Swap_ranges [ 3 ]

iter_swap [ 2 ]

Unique [ 2 + 1 ]

Unique_copy [ 3 + 1 ]

Upper_bound [ 3 + 1 ]

Adjacent_find [ 2 + 1 ]

Fill [ 3 ]

Fill_n [ 3 ]

Is_permutation [ 4 + 1 ]

Max [ 2 + 1 ]

Max_element [ 2 + 1 ]

Merge [ 5 + 1 ]

Next_permutation [ 2 + 1 ]

Nth_element [ 3 + 1 ]

Rotate [ 3 ]