STL入门基础【OI缩水版】

文章目录[x]
  1. 1:0x00 前言
  2. 2:0x10背景
  3. 3:0x20算法
  4. 4:0x30容器&迭代器
  5. 5:0xFF参考资料

            2018.5.21 

文章比较长,写的也比较垃圾,而且还没写完,超级占坑。。。
推荐选择性阅读您需要的,或者直接看最后的参考链接,指向其他大佬的博客。


0x00 前言

Standard Template Library(标准模板库)——简称STL,提供了一系列内置的算法和容器,可以提高编写代码的效率。NOI 系列比赛自 2011 年起允许 C++ 选手使用 STL,所以我们应该利用好 STL,发挥 C++ 语言的优势。


0x10背景

0x11分类

STL 可分为容器(containers)、迭代器(iterators)、空间配置器(allocator)、配接器(adapters)、算法(algorithms)、仿函数(functors)六个部分。

本文主要讲解容器、迭代器、算法,其他的几个部分在竞赛中很少使用到。

0x12模板

所谓模板是一种使用无类型参数来产生一系列函数或类的机制。
若一个程序的功能是对某种特定的数据类型进行处理,则可以将所处理的数据类型说明为参数,以便在其他数据类型的情况下使用,这就是模板的由来。

1.假如设计一个求两参数最大值的函数,在实践中我们可能需要定义四个函数:

int max ( int a , int b ) { return ( a > b ) ? a , b ; }
long max ( long a , long b ) { return ( a > b ) ? a , b ;}
double max ( double a , double  b ) { return ( a >b)? a , b ; }
char max ( char a , char b ) { return ( a > b ) ? a , b ;}

2.这些函数几乎相同,唯一的区别就是形参类型不同
3.求两个数最大值,使用模板

#include
template<class T>T max(T a , T b){ return (a>b) ? a : b; }//声明
int main(){
    int a, b;
    scanf("%d%d", &a, &b);
    printf("%d\n", max<int>(a,b));//调用
    return 0;
}
0x13命名空间

命名空间(namespace)是 C++ 的一个特性,它被用于解决名称冲突,比如假设 Menci 和 Fuxey 都在自己的头文件里编写了一个 work() 函数,如果这两个函数我们都要用,则名称会产生冲突,但如果两人都将自己的函数写在单独的命名空间内,就成了 Menci::work()Fuxey::work(),就不会冲突了。

1.STL 的所有内容都包含在 std 命名空间内。

2.如何使用STL的函数。
如果我们要调用 STL 中的 sort 函数(下文会有提到),要这样写:
std::sort(a, a + n);
我们也可以std::sort 这个函数“导入”到全局中,就可以直接 sort(a, a + n) 这样调用了。 使用 using 关键字来“导入”命名空间中的函数或类。
using std::sort;

3.也可以将整个命名空间导入全局,这样就可以直接访问命名空间中的所有内容,但更容易产生名称冲突(比如你可能会声明一个叫做 max 的变量,但它会覆盖 STL 中的 max 函数)。 使用 using namespace 来“导入”整个命名空间。
using namespace std;

4.你也可以写自己的命名空间来封装一些函数,使程序更加清楚。
或者把数据结构写到一个奇怪的cpp里用于调试代码。

poj3468


0x20算法

1、STL 中的算法主要包含在 头文件中,这个文件名要记住,每天念一遍。
2、STL中函数的区间都是左闭右开的:
比如 sort(a+1,a+n+1); 或者 sort(a.begin(),a.end());

0x21排序

一、介绍:

  1. STL 中提供一系列与排序有关的函数,其中最常用到的是 sortstable_sort,sort 是不稳定的排序,它的期望时间复杂度为 <span class="MathJax" id="MathJax-Element-1-Frame" tabindex="0" data-mathml="
    O(nlogn)

    " role="presentation" style="position: relative;">

    O(nlogn)

    ,stable_sort 是稳定的排序,它的时间复杂度为 <span class="MathJax" id="MathJax-Element-2-Frame" tabindex="0" data-mathml="

    O(nlogn)

    " role="presentation" style="position: relative;">

    O(nlogn)

  2. sort 使用类似与快速排序的算法,在大多数情况下能获得最高的效率,stable_sort 使用多路归并排序算法,可以在稳定的前提下取得较高的效率。一般常用 sort。

二、用法(以 sort 为例,stable_sort 相同):
如果我们要对一个数组 a 的前 n 个元素进行排序,则对应区间为 [a, a + n),因为 a 指向数组的第一个元素(下标为 0),a + n 指向数组的第 n 个元素之后。

三、实例:
sort 函数默认是升序排序,如果需要降序,可以通过以下2种方法实现。
1.自定义“比较函数”来实现。bool cmp(int a, int b) { return a > b;}
下面的代码演示了读入 n(n <= 100000)个数,并降序排序后输出。

#include
#include
const int maxn = 100000;
int n, a[maxn];
bool cmp(int a, int b){return a > b;}
int main() {
    scanf("%d", &n);
    for(int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    std::sort(a+1, a + n+1, cmp);
    for(int i = 1; i <= n; i++)
        printf("%d\n", a[i]);
    return 0;
}

2.通过重载运算符或者定义比较函数的方法对结构体进行排序:

struct student_t {
    unsigned int id;
    long double score;
    bool operator<(const student_t &other) const {
        return score < other.score;
    }
} students[MAXN];

bool compare(const student_t &student1, const student_t &student2) {
    return student1.score < student2.score;
}
std::sort(students, students + n, &compare);

写在结构体中的 operator< 即为重载运算符,这让我们的结构体支持小于号的比较操作。 结构体下面的 compare 是比较函数,比较函数和重载运算符只需要写一个就够了。

3.注意两种写法中的 const& 都不能省略。

0x22去重

一、用法:
1.使用 unique 函数来去除数组中的重复元素,其调用格式与 sort类似,注意调用 unique 前必须保证数组是有序的(升序降序都可以)。
std::sort(a, a + n);
std::unique(a, a + n);
2.unique 函数返回去重后的数组的最后一个元素之后,一般通过用返回值减去首地址的方法获得不重复的元素数量:
int count = std::unique(a, a + n) - a;

二、实例
下面的代码演示了读入 n(n <= 100000)个数,并升序排序并去重后输出。

#include
#include
const int maxn = 100000;
int n, a[maxn];
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        scanf("%d", &a[i]);
    std::sort(a, a + n);
    int count = std::unique(a, a + n) - a;
    for (int i = 0; i < count; i++)
        printf("%d ", a[i]);
    return 0;
}
0x23打乱

一、用法
1.reverse:反转一个数组或向量。
调用像这样,reverse(a+1,a+n+1); 或者 reverse(a.begin(),a.end());
2.random_shuffle:随机打乱
用法与reverse完全相同。

二、实例
这两个函数往往用于测试数据生成。

0x24查找

一、用法:
1.lower_bound:返回第一个 ”大于等于 value“ 的元素位置。
另一种解释是在他前面可插入”元素值为 value“且 ”不破坏有序性“的第一个位置。
2.upper_bound:返回第一个 “大于 value ” 的元素位置;
另一种解释是在他前面可插入”元素值为 value“且 ”不破坏有序性“的最后一个位置 。
二、实例:
在有序int数组(下标1~n)中查找大于等于x的最小整数的下标:
int i = lower_bound(a+1,a+n+a,x)-a;
如果找不到,则返回指向末位元素后一个位置的迭代器。

0x24其他

1、最大值,最小值,交换。
max,min,swap
2、下一个排列,next_permutation;(上一个排列prev_permutation 同理可得)
把两个迭代器指定的部分看做一个排列,求这些元素构成的全排列中,字典序排在下一个的排列,并直接在序列上更新。另外,不存在排名更靠后的排列则返回false,否则返回trye。

#include
#include
using namespace std;
int n=5, a[5050];
int main() {
    for(int i = 1; i <= n; i++)a[i] = i;
    do{
        for(int i = 1; i <= n; i++)cout<' ';
        cout<<'\n';
    }while(next_permutation(a+1,a+n+1));
    return 0;
}

0x30容器&迭代器

容器分为三大类:
1) 顺序容器
vector:后部插入/删除,直接访问
deque:前/后部插入/删除,直接访问
list:双向链表,任意位置插入/删除
2)关联容器
set:快速查找,无重复元素
multiset :快速查找,可有重复元素
map:一对一映射,无重复元素,基于关键字查找
multimap :一对一映射,可有重复元素,基于关键字查找
3)容器适配器
stack:LIFO
queue:FIFO
priority_queue:优先级高的元素先出


0xFF参考资料

STL入门基础
Menci的博客
算法竞赛入门经典
算法竞赛进阶指南
一些奇奇怪怪的PPT

点赞

发表评论

昵称和uid可以选填一个,填邮箱必填(留言回复后将会发邮件给你)
tips:输入uid可以快速获得你的昵称和头像