Skip to content

STL.md

Latest commit

 

History

History
220 lines (168 loc) · 11.1 KB

STL.md

File metadata and controls

220 lines (168 loc) · 11.1 KB

STL

目录

  1. 【STL介绍】
  2. 【容器】
  3. 【迭代器】
  4. 【函数对象】
  5. 【算法】

1. STL(标模板库准)介绍

STL提供了一组表示容器、迭代器、函数对象和算法的模板。STL使得能够构造各种容器（包括数组、队列和链表）和执行各种操作（包括搜索、排序和随机排列）。

  • 容器 —— 是一个与数组类似的单元，可以存储若干个值。STL容器是同质，即存储的值的类型相同。
  • 算法 —— 是完成特定任务（如对数组进行排序或在链表中查找特定值）的方法。
  • 迭代器 —— 能够用来遍历容器的对象，与能够遍历数组的指针类似，是广义指针。
  • 函数对象 —— 是类似于函数的对象，可以是类对象或函数指针（包括函数名，因为函数名被用作指针）。

下面以模板类vector的使用对STL有一个基本认识。

#include<iostream>
#include<vector>

int main() {
	using namespace std;
	//创建一个存储 int类型的vector对象
	vector<int> vec;
	int i;
	//显示vec的初始大小
	cout << "vector 大小 = " << vec.size() << endl;

	//存进5个值
	for ( i = 0; i < 5; i++)
	{
		vec.push_back(i);
	}

	//显示vec的大小
	cout << "扩大的 vector 大小 = " << vec.size() << endl;

	// 输出里面的值
	for (i = 0; i < 5; i++) {
		cout << "value of vec [" << i << "] = " << vec[i] << endl;
	}

	// 使用迭代器访问vec的值
	vector<int>::iterator v = vec.begin();
	while (v != vec.end()) {
		cout << "value of v = " << *v << endl;
		v++;
	}
	return 0;
}

泛型编程

STL是一种泛型编程（generic programming）。面向对象编程关注的式编程的数据方面，而泛型编程关注的是算法。他们之间的共同点是抽象和创建可重用代码，但理念决然不同。
泛型编程旨在编写独立于数据类型的代码。在C++中，完成通用程序的工具是模板。当然模板使得能够按照泛型定义函数或类，而STL通过通用算法更进了一步。

3. 迭代器Iterator

理解迭代器是理解STL的关键所在。模板使得算法独立于存储的数据类型，而迭代器使算法独立于使用的容器类型。因此他们都是STL通用方法的重要组成部分。

3.1 迭代器使用

使用容器时，无需知道其迭代器是如何实现的，也无需知道超尾是如何实现的，而只需要知道他有迭代器，其begin()返回一个指向第一个元素的迭代器，end()返回一个指向超尾位置的迭代器即可。
例：打印vector<double>对象中的值：

vector<double>::iterator pr;	//声明一个vector<double>类型的迭代器
for(pr=socres.begin();pr!=scores.end();pr++)
	cout<<*pr<<endl;

如果使用list<double>类模板来存储分数，代码如下：

list<double>::iterator pr;	//声明一个list<double>类型的迭代器
for(pr=socres.begin();pr!=scores.end();pr++)
	cout<<*pr<<endl;

使用C++11新增的自动类型推断可以进一步简化：对矢量vector或列表list都可以用如下代码：

for(auto pr=socres.begin();pr!=scores.end();pr++)
	cout<<*pr<<endl;

实际上，作为一种编程风格应避免直接使用迭代器，而应尽可能的使用STL函数（如for_each）来处理细节。

3.2 迭代器类型

不同的算法对迭代器的要求也不同。例如查找算法和排序算法。STL定义了5种迭代器。

类型描述
输入迭代器必须能否访问容器中所有的值
输出迭代器程序可以修改容器的值而不能读取
正向迭代器只能使用++运算符来遍历容器，总是按照相同顺序遍历一系列值
双向迭代器具有正向迭代器的所有特性，同时支持（前缀和后缀）递减运算符
随机访问迭代器能够直接跳转到容器钟的任何一个元素

4. 容器Containers

容器是存储其他对象的对象。被存储的对象必须是同一种类型，可以是OOP意义上的对象，也可以是内置类型值。

4.1 基本容器

下面是容器容器的特性，基本容器不能保证其元素都按照特定的顺序存储，也不能保证元素的顺序不变。

一些基本的容器特征
表达式返回类型说明复杂度
X::iterator指向T的迭代器类型满足正向迭代器要求的任何迭代器编译时间
X::value_typeTT的类型编译时间
X u;创建一个名为u的空容器固定
X();创建一个匿名的空容器固定
X u(a);调用复制构造函数后u==a线性
X u=a;作用同X u(a);线性
r = a;X&调用赋值运算后r==a线性
(&a)->~X()void对容器中每个元素应用析构函数线性
a.begin()迭代器返回指向容器第一个原色的迭代器固定
a.end()迭代器返回超尾值迭代器固定
a.size()无符号整型返回元素个数，等价于a.end()-a.begin()固定
a.swap(b)void交换a和b的内容固定
a==b可转换为bool如果a和b的长度相同，且a中每个元素都等于b中相应的元素，则为真线性
a!=b可转换为bool返回!(a==b)线性

其中X表示容器类型，如vector；T表示存储在容器中的对象类型；a 和 b 表示类型为X的值；r表示类型为X&的值；u表示类型为X的标识符。

4.2 序列容器

可以通过添加要求改进基本的容器概念。序列（sequence）是一种重要的改进。序列概念增加了迭代器至少是正向迭代器这样的要求，这保证了元素将按照特定顺序排列，不会在两次迭代之间发生变化。
7种STL序列：

7种序列容器
容器特点常用方法
vector是数组的一种类表示，提供了自动内存管理功能，可以动态的改变vector对象的长度，支持随机访问。rbegin()、rend()
deque表示双端队列，从deque对象的开始位置插入和删除元素的时间是固定的，而不是像vector那样是线性的。
list表示双向链表。list在链表种任意位置进行插入和删除的时间都是固定的。insert()、sort()、remove()、merge()、unique()
forward_list它实现了单链表。每个节点都只链接到下一个节点，因此forward_list只需要正向迭代器。相比list，forward_list更简单紧凑，功能也更少，不可反转。
queuequeue模板类是一个适配器类。不允许随机访问队列元素和变量元素。可以添加元素到队尾，从队首删除元素等。front()、back()、push()、pop()
priority_queue支持的操作和queue模板类相同，是另一种适配器类。最大的区别队列中最大的元素被移到队首。size()、top()
arrayarray并非STL容器，因为长度是固定的，没有定义调整容器大小的操作。operator[]()、at(),很多标准STL算法可以用于array对象，如copy()、for_each()

4.4 关联容器

关联容器（associative container）是对容器概念的另一种改进。关联容器将值与键关联在一起，并使用键来查找值。关联容器的优点在于，它提供了对元素的快速访问，允许插入新的元素但不能插入指定位置。STL提供了4种关联容器：set、multiset、map和multimap。

4种关联容器
容器特点常用方法
set是最简单的关联容器，其值类型和与键相同，键是唯一的，不能存储多个相同的值。可翻转、排序。rbegin()、rend()
multiset和set类似，最大的区别是multiset键和值得类型不同，且同一个键可能与多个值相关联。
map
multimap

4.6 无序关联容器（C++11）

无序关联容器与关联容器一样，通过键与值关联起来。差别在于关联容器是基于树结构的，而无序机构关联容器是基于数据结构哈希表的，这可以提高添加、删除和查找算法的效率。

  • unordered_set
  • unordered_multiset
  • unordered_map
  • unorddered_multimap

5. 函数对象

很多STL算法都是用函数对象——也叫函数符（functor）。函数符是可以以函数方式与（）结合使用的任意对象。这包括函数名、指向函数的指针和重载了（）运算符的类对象（即定义了函数operator( )( )的类）。例如，可以这样定义一个类：

class Linear{
private:
	double slope;
    double y0;
public:
    Linear(double sl_ = 1, double y_ = 0)
        :slope(sl_),y0(y_){}
    double operator()(double x){return y0 + slope * x;}
};

这样重载的()运算符使得能够像函数那样使用Linear对象：

Linear f1；
Linear f2(2.5,10.0);
double y1 = fl(12.5);	//右边相当于fl.operator()(12.5)
double y2 = f2(0.4);

6. 算法

STL包含很多处理容器的非成员函数，如sort()、find()、copy()。它们的总体设计是相同的，都是用迭代器来标识要处理的数据区间和结果放置的位置。对于算法函数设计，有两个主要的通用部分。首先，它们都是用模板来提供泛型；其次，它们都使用迭代器来提供访问容器中数据的通用表示。