# 泛型编程

我们先来看两个代码片段，第一个片段使用数组来寻找相同的值，第二个片段使用链表的数据结构来寻找相同的值。

```C++
double * find_ar(double * ar, int n, const double & val)
{
    for (int i=0;i<n;i++)
        if(ar[i] == val)
            return &ar[i];
    return 0;
}
```

```C++
struct Node
{
    double item;
    Node * p_next;
}
```

泛型编程旨在使用同一个find函数来处理数组、链表或者任何其他容器类型。函数不仅独立于容器中存储的数据类型，而且独立于容器本身的数据结构。**模板**提供了存储容器中数据类型的通用表示，遍历容器中值得通用表示就是**迭代器**。

普通迭代器需要哪些特征呢？

- 应能够对迭代器执行解除引用得操作，以便于能够访问它引用的值。如果p是一个迭代器，那么*p应该具有定义。
- 应能够将一个迭代器赋给另一个。如果p和q都是一个迭代器，那么p=q应该要有定义。
- 应能够将一个迭代器与另一个迭代器进行比较，所以p==q和p!=q要有定义。
- 能够使用迭代器遍历容器中所有的元素。则p++和++p要有定义。

STL按功能的强弱定义了多种级别的迭代器。

```C++
typedef double * iterator;
iterator find_ar(iterator ar, int n, const double & val)
{
    for(int i=0; i<n; i++, ar++)
        if(*ar==val)
            return ar;
    return 0;
}
```

## 迭代器类型

不同的算法对迭代器的实现方法不同。例如，查找算法需要定义++运算符，以便于迭代器能够遍历整个容器，它要求能够读取数据，但不要求能够写数据，只查看不修改。排序算法要求能够随机访问，以便于能够交换两个不相邻的元素，排序算法要求能够读写数据。

STL定义了5种迭代器，并根据所需迭代器的类型对算法进行了描述。

- 输入迭代器
- 输出迭代器
- 正向迭代器
- 双向迭代器
- 随机访问迭代器

```C++
template<class InputIterator, class T>
InputIterator find(InputIterator first, InputIterator last, const T& value);

//函数原型指出了这种算法需要一个输入迭代器

template<class RandomAccessIterator>
void sort(RandomAccessIterator first, RandomAccessIterator last);

//排序算法需要一个随机访问迭代器
```

这5种迭代器都可以执行解除引用的操作，即为它们定义*运算符，也可以进行比较。

## 迭代器功能

| 迭代器功能       | 输入 | 输出 | 正向 | 双向 | 随机访问 |
| ---------------- | ---- | ---- | ---- | ---- | -------- |
| 接触引用读取     | 有   | 无   | 有   | 有   | 有       |
| 解除引用写入     | 无   | 有   | 有   | 有   | 有       |
| 固定和可重复排序 | 无   | 无   | 有   | 有   | 有       |
| ++i，i++         | 有   | 有   | 有   | 有   | 有       |
| --i，i--         | 无   | 无   | 无   | 有   | 有       |
| i[n]             | 无   | 无   | 无   | 无   | 有       |
| i+n              | 无   | 无   | 无   | 无   | 有       |
| i-n              | 无   | 无   | 无   | 无   | 有       |
| i+=n             | 无   | 无   | 无   | 无   | 有       |
| i-=n             | 无   | 无   | 无   | 无   | 有       |

## 容器种类

STL中提供了多种容器的种类。

通用容器：deque、list、queue、priority_queue、stack、vector、map、multimap、set、multiset、bitset，C++11新增容器：forward_list、unordered_map、unordered_multimap、unordered_set、unordered_multiset。

基本容器不能保证其元素都按特定的顺序存储，也不能保证元素的顺序不变，对概念进行改进后可以增加这样的保证。




<!-- markdown for nginx, see https://phus.lu -->
<script>
!function(){
	var dom = {
		element: null,
		get: function (o) {
			var obj = Object.create(this)
			obj.element = (typeof o == "object") ? o : document.createElement(o)
			return obj
		},
		add: function (o) {
			var obj = dom.get(o)
			this.element.appendChild(obj.element)
			return obj
		},
		text: function (t) {
			this.element.appendChild(document.createTextNode(t))
			return this
		},
		attr: function (k, v) {
			this.element.setAttribute(k, v)
			return this
		}
	}

	if (!document.head) return
	head = dom.get(document.head)
	head.add('meta').attr('charset', 'utf-8')
	head.add('meta').attr('name', 'viewport').attr('content', 'width=device-width,initial-scale=1')

	if (!document.body) {
		document.write(["<div class=\"container\">",
		"<h3>nginx.conf</h3>",
		"<textarea rows=6 cols=50>",
		"# download markdown.html to /wwwroot",
		"location ~ \\.md$ {",
		"    default_type text/html;",
		"    add_after_body /markdown.html;",
		"}",
		"</textarea>",
		"</div>"].join("\n"))
		return
	}

	var bodytext = document.body.innerHTML
	document.body.innerHTML = ''

	div = dom.get('div').attr('class', 'container')

	div.add('script').attr('src', 'https://cdnjs.cloudflare.com/ajax/libs/marked/0.5.2/marked.min.js').attr('integrity', 'sha256-zFUosuESzULu5P+SZdjRRtBZR8+1u5RZDlbt3Q5KL8U=').attr('crossorigin', 'anonymous')
	div.add('link').attr('rel', 'stylesheet').attr('href', 'https://cdnjs.cloudflare.com/ajax/libs/github-markdown-css/5.1.0/github-markdown-light.min.css').attr('integrity', 'sha256-WQx0Y6LLZeGv3V3NVVge+YIL5MIOt45RPuFdkyNodls=').attr('crossorigin', 'anonymous')

	title = decodeURIComponent(document.location.pathname.replace(/.*\//, '').replace(/\.html$/, ''))
	document.title = '《' + title.replace(/\.md$/, '') + '》'
	tbody = div.add('table').add('tbody')
	tbody.add('tr').add('th').text(title).attr('class', 'octicon-book')
	tbody.add('tr').add('td').add('div').attr('id', 'readme').attr('class', 'markdown-body')

	wait = function (name, callback) {
		var interval = 10; // ms
		window.setTimeout(function() {
			if (window[name]) {
				callback(window[name])
			} else {
				window.setTimeout(arguments.callee, interval)
			}
		}, interval)
	}
	wait('marked', function() {
		document.getElementById("readme").innerHTML = marked.parse(bodytext)
	})

	document.body.appendChild(div.element)
}()
</script>

<style>
body {
	margin: 0;
	font-family: "ubuntu", "Tahoma", "Microsoft YaHei", Arial, Serif;
}
.markdown-body {
	float: left;
	font-family: "ubuntu", "Tahoma", "Microsoft YaHei", Arial, Serif;
}
.container {
	padding-right: 15px;
	padding-left: 15px;
	margin-right: auto;
	margin-left: auto;
}
@media (min-width: 768px) {
	.container {
		max-width: 80%;
	}
}
@media (min-width: 992px) {
	.container {
		max-width: 70%;
	}
}
@media (min-width: 1200px) {
	.container {
		max-width: 60%;
	}
}
table {
	width: 100%;
	max-width: 100%;
	margin-bottom: 20px;
	border: 1px solid #ddd;
	padding: 0;
	border-collapse: collapse;
}
table th {
	font-size: 14px;
}
table tr {
	border: 1px solid #ddd;
	padding: 5px;
}
table th, table td {
	border: 1px solid #ddd;
	font-size: 14px;
	line-height: 20px;
	padding: 3px;
	text-align: left;
}
.octicon-book {
	background-position: center left;
	background-repeat: no-repeat;
	padding-left: 20px;
	background-image: url("data:image/svg+xml;charset=utf8,%3Csvg xmlns='http://www.w3.org/2000/svg' width='16' height='16' viewBox='0 0 16 16'%3E%3Cpath d='M3,5 L7,5 L7,6 L3,6 L3,5 L3,5 Z M3,8 L7,8 L7,7 L3,7 L3,8 L3,8 Z M3,10 L7,10 L7,9 L3,9 L3,10 L3,10 Z M14,5 L10,5 L10,6 L14,6 L14,5 L14,5 Z M14,7 L10,7 L10,8 L14,8 L14,7 L14,7 Z M14,9 L10,9 L10,10 L14,10 L14,9 L14,9 Z M16,3 L16,12 C16,12.55 15.55,13 15,13 L9.5,13 L8.5,14 L7.5,13 L2,13 C1.45,13 1,12.55 1,12 L1,3 C1,2.45 1.45,2 2,2 L7.5,2 L8.5,3 L9.5,2 L15,2 C15.55,2 16,2.45 16,3 L16,3 Z M8,3.5 L7.5,3 L2,3 L2,12 L8,12 L8,3.5 L8,3.5 Z M15,3 L9.5,3 L9,3.5 L9,12 L15,12 L15,3 L15,3 Z' /%3E%3C/svg%3E");
}
</style>