AI工具人

# ACM竞赛常用STL（二）之STL--algorithm

<algorithm>无疑是STL 中最大的一个头文件，它是由一大堆模板函数组成的。

adjacent_find / binary_search / copy / copy_backward / count

/ count_if / equal / equal_range / fill / fill_n / find /

find_end / find_first_of / find_if / for_each / generate /

generate_n / includes / inplace_merge / iter_swap /

lexicographical_compare / lower_bound / make_heap / max /

max_element / merge / min / min_element / mismatch /

next_permutation / nth_element / partial_sort /

partial_sort_copy / partition / pop_heap / prev_permutation

/ push_heap / random_shuffle / remove / remove_copy /

remove_copy_if / remove_if / replace / replace_copy /

replace_copy_if / replace_if / reverse / reverse_copy /

rotate / rotate_copy / search / search_n / set_difference /

set_intersection / set_symmetric_difference / set_union /

sort / sort_heap / stable_partition / stable_sort / swap /

swap_ranges / transform / unique / unique_copy / upper_bound

```#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int Visit(int v) // 遍历算子函数
{
cout << v << " ";
return 1;
}
class MultInt // 定义遍历算子类
{
private:
int factor;
public:
MultInt(int f) : factor(f){}
void operator()(int &elem) const
{
elem *= factor;
}
};
int main()
{
vector<int> L;
for (int i=0; i<10; i++)
L.push_back(i);
for_each(L.begin(), L.end(), Visit);
cout << endl;
for_each(L.begin(), L.end(), MultInt(2));
for_each(L.begin(), L.end(), Visit);
cout << endl;
return 0;
}```

0 1 2 3 4 5 6 7 8 9

0 2 4 6 8 10 12 14 16 18

```using namespace std;
int main()
{
vector<int> L;
for (int i=0; i<10; i++)
L.push_back(i);
vector<int>::iterator min_it = min_element(L.begin(),L.end());
vector<int>::iterator max_it = max_element(L.begin(),L.end());
cout << "Min is " << *min_it << endl;
cout << "Max is " << *max_it << endl;
return 1;
}```

Min is 0

Max is 9

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

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void Print(vector<int> &L)
{
for (vector<int>::iterator it=L.begin(); it!=L.end();it++)
cout << *it << " ";
cout << endl;
}
int main()
{
vector<int> L;
for (int i=0; i<5; i++)
L.push_back(i);
for (int i=9; i>=5; i--)
L.push_back(i);
Print(L);
sort(L.begin(), L.end());
Print(L);
sort(L.begin(), L.end(), greater<int>()); // 按降序排序
Print(L);
return 0;
}```

0 1 2 3 4 9 8 7 6 5

0 1 2 3 4 5 6 7 8 9

9 8 7 6 5 4 3 2 1 0

```#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
int main()
{
// 先初始化两个向量v1 和v2
vector <int> v1, v2;
for (int i=0; i<=5; i++)
v1.push_back(10*i);
for (int i=0; i<=10; i++)
v2.push_back(3*i);
cout << "v1 = ( " ;
for (vector <int>::iterator it=v1.begin(); it!=v1.end();it++)
cout << *it << " ";
cout << ")" << endl;
cout << "v2 = ( " ;
for (vector <int>::iterator it=v2.begin(); it!=v2.end();it++)
cout << *it << " ";
cout << ")" << endl;
// 将v1 的前三个元素复制到v2 的中间
copy(v1.begin(), v1.begin()+3, v2.begin()+4);
cout << "v2 with v1 insert = ( " ;
for (vector <int>::iterator it=v2.begin(); it!=v2.end();it++)
cout << *it << " ";
cout << ")" << endl;
// 在v2 内部进行复制，注意参数2 表示结束位置，结束位置不参与复制
copy(v2.begin()+4, v2.begin()+7, v2.begin()+2);
cout << "v2 with shifted insert = ( " ;
for (vector <int>::iterator it=v2.begin(); it!=v2.end();it++)
cout << *it << " ";
cout << ")" << endl;
return 1;
}```

v1 = ( 0 10 20 30 40 50 )

v2 = ( 0 3 6 9 12 15 18 21 24 27 30 )

v2 with v1 insert = ( 0 3 6 9 0 10 20 21 24 27 30 )

v2 with shifted insert = ( 0 3 0 10 20 10 20 21 24 27 30 )

STL in ACM

```begin(), //取首个元素，返回一个iterator
end(), //取末尾（最后一个元素的下一个存储空间的地址）
size(), //就是数组大小的意思
clear(), //清空
empty(), //判断vector 是否为空
[ ] //很神奇的东东，可以和数组一样操作
//举例： vector a; //定义了一个vector
//然后我们就可以用a[i]来直接访问a 中的第i + 1 个元素！和数组的下标一模一样！
push_back(), pop_back() //从末尾插入或弹出
insert() O(N) //插入元素，O(n)的复杂度
erase() O(N) //删除某个元素，O(n)的复杂度```

Iterator 用法举例:

```int main()
{
int n,i;
vector vi; //类似于我们定义一个数组，同 int vi[1000]; 但vector的大小是自动调整的
vector ::iterator itr; //两个冒号
while (scanf("%d",&n) != EOF)
vi.push_back(n);
for (i = 0 ; i < vi.size() ; i++)
printf("%d\n",vi[i]);
for (itr = vi.begin() ; itr != vi.end() ; itr++)
printf("%d\n",*itr);
return 0;
}```

类似：双端队列，两头都支持进出

```是的精简版:) //栈，只支持从末尾进出

list

begin(), end(), size(), clear(), empty()
push_back(), pop_back() //从末尾插入或删除元素
push_front(), pop_front()
insert() O(1) //链表实现，所以插入和删除的复杂度的O(1)
erase() O(1)
sort() O(nlogn),不同于中的sort
//不支持[ ]操作！

set //又是一个Compare 函数，类似于qsort 函数里的那个Compare 函数，

insert() O(logn)
erase() O(logn)
find() O(logn) 找不到返回a.end()
lower_bound() O(logn) 查找第一个不小于k 的元素
upper_bound() O(logn) 查找第一个大于k 的元素
equal_range() O(logn) 返回pair
42

struct SS {int x,y;};
struct ltstr {
bool operator() (SS a, SS b)
{return a.x < b.x;} //注意，按C 语言习惯，double 型要写成这样：
return a.x < b.x ? 1 : 0;
};
int main() {
set st;
…
}

map //就是很多pair 组成一个红黑树
insert() O(logn)
erase() O(logn)
find() O(logn) 找不到返回a.end()
lower_bound() O(logn) 查找第一个不小于k 的元素
upper_bound() O(logn) 查找第一个大于k 的元素
equal_range() O(logn) 返回pair
[key]运算符 O(logn) *** //这个..太猛了，怎么说呢，数组有一个下标，如a[i],这里i 是int 型的。数组可以认为是从int 印射到另一个类型的印射，而map 是一个任意的印射，所以i 可以是任何类型的！允许重复元素, 没有[]运算符

priority_queue

push() O(n)
pop() O(n)
top() O(1)

priority_queue maxheap; //int 最大堆
struct ltstr { //又是这么个Compare 函数，重载运算符？？？不明白为什么要这么写...反正这个Compare 函数对我来说是相当之神奇。RoBa

bool operator()(int a,int b)
{return a > b;}
};
priority_queue <INT,VECTOR,ltstr> minheap; //int 最小堆
1.sort()
void sort(RandomAccessIterator first, RandomAccessIterator
last);
void sort(RandomAccessIterator first, RandomAccessIterator
last, StrictWeakOrdering comp);

Quicksort,复杂度O(nlogn)
(n=last-first,平均情况和最坏情况)

1.从小到大排序(int, double, char, string, etc)
const int N = 5;
int main()
{
int a[N] = {4,3,2,6,1};
string str[N] = {“TJU”,”ACM”,”ICPC”,”abc”,”kkkkk”};
sort(a,a+N);
sort(str,str+N);
return 0;
}
2.从大到小排序（需要自己写comp 函数)
const int N = 5;
int cmp(int a,int b)
{
return a > b;
}
int main()
{
int a[N] = {4,3,2,6,1};
sort(a,a+N,cmp);
return 0;
}
3. 对结构体排序
struct SS {int first,second;};
int cmp(SS a,SS b)
{
if (a.first != b.first)
return a.first < b.first;
return a.second < b.second;
}
v.s. qsort() in C (平均情况O(nlogn)，最坏情况
O(n^2)) //qsort 中的cmp 函数写起来就麻烦多了！
int cmp(const void *a,const void *b) {
if (((SS*)a)->first != ((SS*)b)->first)
return ((SS*)a)->first – ((SS*)b)->first;
return ((SS*)a)->second – ((SS*)b)->second;
}
qsort(array,n,sizeof(array[0]),cmp);
sort()系列:
stable_sort(first,last,cmp); //稳定排序
partial_sort(first,middle,last,cmp);//部分排序

e.g.
int A[12] = {7, 2, 6, 11, 9, 3, 12, 10, 8, 4, 1, 5};
partial_sort(A, A + 5, A + 12);
// 结果是 "1 2 3 4 5 11 12 10 9 8 7 6".
Detail: Heapsort ,
O((last-first)*log(middle-first))
sort()系列:
partial_sort_copy(first, last, result_first, result_last,
cmp);
//输入到另一个容器，不破坏原有序列
bool is_sorted(first, last, cmp);
//判断是否已经有序
nth_element(first, nth, last, cmp);
//使[first,nth)的元素不大于[nth,last), O(N)
e.g. input: 7, 2, 6, 11, 9, 3, 12, 10, 8, 4, 1, 5
nth_element(A,A+6,A+12);
Output: 5 2 6 1 4 3 7 8 9 10 11 12
2. binary_search()
bool binary_search(ForwardIterator first, ForwardIterator
last, const LessThanComparable& value);
bool binary_search(ForwardIterator first, ForwardIterator
last, const T& value, StrictWeakOrdering comp);

v.s. bsearch() in C
Binary_search()系列
itr upper_bound(first, last, value, cmp);
//itr 指向大于value 的第一个值(或容器末尾)
itr lower_bound(first, last, value, cmp);
//itr 指向不小于valude 的第一个值(或容器末尾)
pair equal_range(first, last, value, cmp);
//找出等于value 的值的范围 O(2*log(last – first))
int A[N] = {1,2,3,3,3,5,8}
*upper_bound(A,A+N,3) == 5
*lower_bound(A,A+N,3) == 3
make_heap(first,last,cmp) O(n)
push_heap(first,last,cmp) O(logn)
pop_heap(first,last,cmp) O(logn)
is_heap(first,last,cmp) O(n)
e.g:
vector vi;
while (scanf(“%d”,&n) != EOF)
{
vi.push_back(n);
push_heap(vi.begin(),vi.end());
}
Others interesting:
next_permutation(first, last, cmp)
prev_permutation(first, last, cmp)
//both O(N)
min(a,b);
max(a,b);
min_element(first, last, cmp);
max_element(first, last, cmp);
Others interesting:
fill(first, last, value)
reverse(first, last)
rotate(first,middle,last);
itr unique(first, last);
//返回指针指向合并后的末尾处
random_shuffle(first, last, rand)
//头文件
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
using namespace std;```