什么是 STL编程？

标准模板库（Standard Template Library，STL）从广义上讲分为算法（Algorithm）、容器（Container）及迭代器（Interator）三类，包含诸多常用的基本数据结构和基本算法。

标准 C++ 语言中，STL 被组织为下面的 13 个头文件：<algorithm>、<deque>、<functional>、<iterator>、<vector>、<list>、<map>、<memory>、<numeric>、<queue>、<set>、<stack> 及 <utility> 。

sort 排序算法

STL 里的 sort 排序算法在头文件 <algorithm> 中声明，采用的是成熟的“快速排序算法”，可以保证很好的平均性能，其时间复杂度为 $n\log(n)$ ，比标准 C 语言的 qsort 要好。

下面举一个对无序整型数组排序的例子：

#include<bits/stdc++.h>
using namespace std;

void Print(int a[],int n)
{
  for(inbt i=0; i<n; i++)
    cout<<a[i]<<' ';
  cout<<endl;
}

int main()
{
  int a[]={-1,9,-34,100,45,2,98,32};
  int len=sizeof(a)/sizeof(int);
  sort(a,a+len);
  Print(a,len);
  sort(a,a+len,greater<int>());
  Print(a,len);
  return 0;
}

下面给出一道例题：导弹拦截

lower_bound/upper_bound

lower_bound（起始地址 first ，结束地址 last ，要查找的数值 val）：在 first 和 last 中的前闭后开区间进行二分查找，返回大于或等于 val 的第一个元素地址。如果区间内所有元素都小于 val ，则返回 last 的地址，且 last 的地址是越界的。

upper_bound（起始地址 first ，结束地址 last ，要查找的数值 val）：在 first 和 last 中的前闭后开区间进行二分查找，返回大于 val 的第一个元素地址。如果 val 大于区间内所有元素，则返回 last 的地址，且 last 的地址是越界的。

下面举一个使用 lower_bound/upper_bound 的升序数组的例子：

#include<bits/stdc++.h>
using namepsace std;

int main()
{
  int a[]={1,1,2,2,3,3,3,4,4,4};
  cout<<lower_bound(a,a+10,0)-a<<endl;
  cout<<lower_bound(a,a+10,1)-a<<endl;
  cout<<lower_bound(a,a+10,3)-a<<endl;
  cout<<lower_bound(a,a+10,4)-a<<endl;
  cout<<lower_bound(a,a+10,5)-a<<endl;

  cout<<upper_bound(a,a+10,0)-a<<endl;
  cout<<upper_bound(a,a+10,1)-a<<endl;
  cout<<upper_bound(a,a+10,3)-a<<endl;
  cout<<upper_bound(a,a+10,4)-a<<endl;
  cout<<upper_bound(a,a+10,5)-a<<endl;
  return 0;
}

降序数组直接使用 lower_bound/upper_bound 二分查找的结果是错误的。这是因为 lower_bound/upper_bound 默认二分查找的区间是升序序列。以查找数值 4 为例，第一步从中间开始，取中间值 $a[(0+8)/2]=a[4]=2$ ，比 4 小，于是继续向更大的值靠近，想那边靠近呢？右边，因为它以为序列是升序的，这显然是错误的。

所以，在降序序列要注意以下两点：

$1.$ lower_bound 的正确写法为 lower_bound(first,last,val,greater<int>())，或类似于 sort 排序，使用自定义比较函数。若 val 在序列中，则返回 val 第一次出现的位置，否则返回第一个插入 val 不影响原序列顺序的位置。

$2.$ upper_bound 的正确写法为upper_bound(first,last,val,greater<int>())，或类似于 sort 排序，使用自定义比较函数。若 val 在序列中，则返回第一个小于 val 的位置，否则返回第一个插入 val 不影响原序列顺序的位置。

正确的程序为：

#include<bits/stdc++.h>
using namepsace std;

int main()
{
  int a[]={4,4,3,3,2,2,1,1};
  cout<<lower_bound(a,a+10,0,greater<int>())-a<<endl;
  cout<<lower_bound(a,a+10,4,greater<int>())-a<<endl;
  cout<<lower_bound(a,a+10,1,greater<int>())-a<<endl;
  cout<<lower_bound(a,a+10,3,greater<int>())-a<<endl;
  cout<<lower_bound(a,a+10,5,greater<int>())-a<<endl;

  cout<<upper_bound(a,a+10,0,greater<int>())-a<<endl;
  cout<<upper_bound(a,a+10,4,greater<int>())-a<<endl;
  cout<<upper_bound(a,a+10,1,greater<int>())-a<<endl;
  cout<<upper_bound(a,a+10,3,greater<int>())-a<<endl;
  cout<<upper_bound(a,a+10,5,greater<int>())-a<<endl;
  return 0;
}

顺便提一下，STL 里还有一个二分查找函数 binary_search(first,last,val)，但它只能判断 val 是否在 first 和 last 的有序区间里存在，如果 val 存在则返回 true ，否则返回 false 。

vector 向量容器

vector 在头文件 <vector> 中声明，它通过一个连续的长度可变的数组存放任意类型的数据。新增数据时，如果 vector 空间已满，则扩展 vector 空间（GNU 编译器套件（GNU Compiler Collection,GCC）规定为两倍），将原来的数据复制过来，释放之前的空间再插入新增的数据；如果存放的数据不超过 vector 空间的一半，则释放一半的 vector 空间（类似于倍增算法）。

vector 在尾端插入和删除元素的时间复杂度为 $O(1)$ ，其他元素插入和删除的时间复杂度为 $O(n)$ 。

下面给出一道例题：普通平衡树

没讲完，感谢大家的阅读，如果有什么错误的地方，请在下方讨论区说出来，我会加以改正。还请大家点个赞，谢谢！

2024/10/1 16:16

什么是 STL编程 ？

sort 排序算法

lower_bound/upper_bound

vector 向量容器

什么是 STL编程？