一. STL基本概念

目录

一. STL基本概念

STL六大组件简介：

STL六大组件的交互关系：

STL优点：

STL三大组件：

1. 容器

2. 算法

3. 迭代器

三大组件的关系：

二. 迭代器简单案例

三. STL简单例子

1.

2.

3.

4.

---

STL：Standard Template Library，标准模板库。

STL六大组件简介：

容器：各种数据结构，如vector，list等，用来存放数据，从实现角度来看，STL容器是一种模板类（class template）。

算法：各种常用的算法，如冒泡、排序等。STL算法是一种function template。

迭代器：扮演了容器与算法之间的胶合剂。从实现角度看，迭代器是一种将 operator*，operator->，operator++，operator-- 等指针相关操作予以重载的class template。所有STL容器都附带有自己专属的迭代器。

仿函数：行为类似函数，可作为算法的某种策略。从实现角度来看，仿函数是一种重载了operator()的class或者class template。

适配器：一种用来修饰容器或仿函数或迭代器接口的东西。

空间配置器：负责空间的配置和管理。

STL六大组件的交互关系：

容器通过空间配置器取得数据存储空间，算法通过迭代器存储容器中的内容，仿函数可以协助算法完成不同策略的变化，适配器可以修饰仿函数。

STL优点：

① 数据结构和算法的分离。

eg：在STL的vector容器中，可以放入元素、基础数据类型变量、元素的地址，STL的sort()排序函数可以用来操作 vector、list等容器。

② STL中几乎所有代码都采用了模板类和模板函数的方式实现，这相比于传统的由函数和类组成的库来说提供了更好的代码重用机会。

③ 高性能：如map可以高效地从十万条记录里查找指定的记录，因为map是采用红黑树的变体实现的。

④ 高移植性：在项目A上用STL编写的模块，可以直接移植到项目B上。

STL三大组件：

1. 容器

容器，置物之所也。

任何特定的数据结构都是为了实现某种特定的算法，STL容器就是将运用最广泛的一些数据结构实现出来。常用的数据结构：数组（array），链表（list），树（tree），栈（stack），队列（queue），集合（set），映射表（map）。

序列式容器：

容器元素在容器中的位置由元素进入容器的时间和地点决定。如：Vector容器、List容器、Stack容器、Queue容器。

关联式容器：

指容器已经有了一定的规则，容器元素在容器中的位置由我的规则来决定。如：Set/multiset容器、Map/multimap容器。

2. 算法

算法，问题之解法也。

质变算法：

运算过程中会更改区间内元素的内容。如：拷贝、替换、删除等。

非质变算法：

运算过程中不会更改区间内元素的内容。如：查找、计数、遍历、寻找极值等。

3. 迭代器

是一种抽象的概念，程序语言中并没有与之对应的实物。

迭代器的设计思维：

STL的中心思想在于将数据容器（container）和算法（algorithms）分开，彼此独立设计，最后再用一种“胶着剂”将它们粘在一起。

容器和算法的泛型化并不困难，C++的class template和function template可分别达成目标，难的是如何设计两者之间的迭代器。

迭代器的种类：

重点学习双向迭代器、随机访问迭代器。

三大组件的关系：

容器存储数据，并且提供迭代器，算法使用迭代器来操作容器中的元素。

二. 迭代器简单案例

（1）数组容器

//数组容器
template<class T>
class MyArray
{
public:
	//保护原生指针，给原生指针取别名
	typedef T* iterator;
	MyArray()
	{
		mCapacity = 10;
		mSize = 5;
		p = new T[mCapacity];
		for (int i = 0; i < mCapacity; i++)
		{
			p[i] = i + 1;
		}
	}
	//提供迭代器，开始位置的迭代器
	T* begin()
	{
		return p;
	}
	//返回结束位置的迭代器
	T* end()
	{
		return p + mSize;
	}
public:
	T* p;
	int mCapacity;
	int mSize;
};

（2）算法

//算法
template<class T>
void printArray(T begin,T end)
{
	for (; begin != end; ++begin)
	{
		cout << *begin << " ";
	}
	cout << endl;
}

（3）test

void test11()
{
	MyArray<int> arr;
	//获取容器提供的开始位置迭代器
	MyArray<int>::iterator begin = arr.begin();
	//获取容器提供的结束位置迭代器
	MyArray<int>::iterator end = arr.end();
 
	printArray(begin, end);
}

三. STL简单例子

包含头文件

#include       //容器头文件
#include    //算法头文件

1.

 for_each()的原型可近似如下：

void _For_each(_InIt _First, _InIt _Last, _Fn1& _Func)
{
	for (; _First != _Last; ++_First)
		_Func(*_First);
}

2.

3.

4.