STL 初入门

本文介绍了C++的STL的入门知识点

STL初入门

STL 主要由迭代器算法容器、仿函数、内存配置器和配接器六部分组成,可帮助程序员完成许多

功能完善、形式多样的程序。

这篇博文主要是起大纲与引导作用,也请各位先行对大致内容有了了解后再查询相关详细内容

STL简要介绍

容器

容器即用来存储并管理数据的地方。

迭代器

迭代器用于在一个对象群集的元素上进行遍历动作。
迭代器的主要用途是为容器提供一组很小的公共接口。利用这个接口,某项操作可以行进至群集内的下一个元素。

算法

STL提供能在各种容器中通用的算法(大约有70种),如插入、删除、查找、排序等。算法就是函数模板。算法通过迭代器来操纵容器中的元素。

许多算法操作的是容器上的一个区间(也可以是整个容器),因此需要两个参数,一个是区间起点元素的迭代器,另一个是区间终点元素的后面一个元素的迭代器。

例如,排序和查找算法都需要这两个参数来指明待排序或待查找的区间。

有的算法返回一个迭代器。例如,find 算法在容器中查找一个元素,并返回一个指向该元素的迭代器。

算法可以处理容器,也可以处理普通的数组。

容器介绍

顺序容器

顺序容器有以下三种:可变长动态数组$ vector$ 、双端队列 $ deque$ 、双向链表$ list$ 。

它们之所以被称为顺序容器,是因为元素在容器中的位置同元素的值无关,即容器不是排序的。

将元素插入容器时,指定在什么位置(尾部、头部或中间某处)插入,元素就会位于什么位置。

关联容器

关联容器有以下四种:$ set、multiset、map、multimap$ 。

关联容器内的元素是排序的。

插入元素时,容器会按一定的排序规则将元素放到适当的位置上,因此插入元素时不能指定位置。
默认情况下,关联容器中的元素是从小到大排序(或按关键字从小到大排序)的,而且用运算符比较元素或关键字大小。

因为是排好序的,所以关联容器在查找时具有非常好的性能。

为称呼方便起见,本教程后面将容器和容器适配器统称为容器。

容器都是类模板。它们实例化后就成为容器类。用容器类定义的对象称为容器对象。

容器对象

vector是一个容器类的名字,vector<int> a;就定义了一个容器对象 $a$。

$a$ 代表一个长度可变的数组,数组中的每个元素都是 $int $类型的变量。

vector<double> b;定义了一个容器对象 $b$,$a$ 和 $b$ 的类型是不同的。

成员函数

所有容器都有以下两个成员函数:

  • int size():返回容器对象中元素的个数。

  • bool empty():判断容器对象是否为空。

顺序容器和关联容器还有以下成员函数:

  • begin() :返回指向容器中第一个元素的迭代器。

  • end() :返回指向容器中最后一个元素后面的位置的迭代器。

  • rbegin() :返回指向容器中最后一个元素的反向迭代器。

  • rend() :返回指向容器中第一个元素前面的位置的反向迭代器。

  • erase(...) :从容器中删除一个或几个元素。该函数参数较复杂,此处省略。

  • clear() :从容器中删除所有元素。

    $ tips$ : 如果一个容器是空的,则 begin()end()的返回值相等,rbegin()rend()的返回值也相等。

顺序容器还有以下常用成员函数:

  • front() :返回容器中第一个元素的引用。
  • back() :返回容器中最后一个元素的引用。
  • push_back() :在容器末尾增加新元素。
  • pop_back() :删除容器末尾的元素。
  • insert(...):插入一个或多个元素。该函数参数较复杂,此处省略。

容器详解

//TODOLIST

  • vector
  • stack
  • queue
  • priority_queue
  • map
  • pair
  • set
  • multiset
  • deque

STL迭代器

示例

第一个是我们常见的$for$循环遍历数组

1
2
3
4
5
6
7
8
void traverseVector_1(int v[],int len)//传入数组和数组长度
{
for(int i=0;i<=len:i++)
{
cout << v[i] << " ";
}
cout<<endl;
}

然后看一段vector容器的下标遍历

1
2
3
4
5
6
7
8
void traverseVector_1(vector<int> v)
{
for(unsigned int i = 0; i < v.size(); ++i)
{
cout<<v[i]<<" ";
}
cout<<endl;
}

然后再看一段vector容器的迭代器遍历

1
2
3
4
5
6
7
8
9
10
11
void traverseVector_2(vector<int> v)
{
// 注:如果参数为const vector<int> 需要用const_iterator
vector<int>::iterator it = v.begin(); //定义了vector类型的迭代器 it,并将其指向v的开头
// vector<int>::const_iterator iter=v.begin();
for(; it != v.end(); ++it)
{
cout<<(*it)<<" ";
}
cout<<endl;
}

算法

算法可以处理容器,也可以处理普通的数组。

有的算法会改变其所作用的容器。例如:

  • copy:将一个容器的内容复制到另一个容器。
  • remove:在容器中删除一个元素。
  • random_shuffle:随机打乱容器中的元素。
  • fill:用某个值填充容器。

有的算法不会改变其所作用的容器。例如:

  • find:在容器中查找元素。
  • count_if:统计容器中符合某种条件的元素的个数。

STL 中的大部分常用算法都在头文件 algorithm 中定义。此外,头文件 numeric 中也有一些算法。

下面介绍一个常用算法 find,以便对算法是什么、怎么用有一个基本的概念。

find 算法和其他算法一样都是函数模板。

实战

括号匹配,使用栈解决

P1739

表达式括号匹配 https://www.luogu.org/problem/P1739

作业

NOJ CF5C

Longest Regular Bracket Sequence