STL堪称泛型编程（GP）的典范，其算法既独立于特定容器（数据结构），又能操作各类容器的元素，其关键在于每个容器都有定义一个叫迭代器的类，这个类封装了容器类对象的一个指针，并重载了一些指针操作的运算符，如"*、->、++、--、+n“等。同时，在算法和迭代器中间封装了一个叫迭代器萃取器（iterator_traits）的中间层，用于萃取迭代器类别和容器元素的类型。

提示一下，在模板类编程中，使用typedef 或 typedef typename定义型别是一种常用的做法。

1 每个容器都定义有自己的专属迭代器

按容器特性及重载的操作符不同，有5种迭代器：

五种迭代器之间有一种继承关系：

一般容器至少支持双向迭代器。

指针也是一种迭代器。

需要注意的是，容器适配器并不提供迭代器，而是定义容器的特殊访问点，通过成员函数去访问。

2 STL算法能通过iterator_traits萃取到迭代器的类别和容器元素的型别

来看map容器及其返回迭代器的成员函数begin()、end()：

#include <iostream>#include <map>int main (){  std::map<char,int> mymap;  mymap['b'] = 100;  mymap['a'] = 200;  mymap['c'] = 300;  // show content:  for (std::map<char,int>::iterator it=mymap.begin(); it!=mymap.end(); ++it)    std::cout << it->first << " => " << it->second << '\n';  return 0;}/*Output:a => 200b => 100c => 300*/

3 常用算法的实现

如std::copy()算法：

template<class InputIterator, class OutputIterator>  OutputIterator copy (InputIterator first, InputIterator last, OutputIterator result){  while (first!=last) {    *result = *first;    ++result; ++first;  }  return result;}

大量的算法内都有while (first!=last)的写法，用来遍历容器区间的每个元素。

std::search()：

template<class ForwardIterator1, class ForwardIterator2>  ForwardIterator1 search ( ForwardIterator1 first1, ForwardIterator1 last1,                            ForwardIterator2 first2, ForwardIterator2 last2){  if (first2==last2) return first1;  // specified in C++11    while (first1!=last1)  {    ForwardIterator1 it1 = first1;    ForwardIterator2 it2 = first2;    while (*it1==*it2) {    // or: while (pred(*it1,*it2)) for version 2        if (it2==last2) return first1;        if (it1==last1) return last1;        ++it1; ++it2;    }    ++first1;  }  return last1;}

4 常用算法的使用

还是上面的std::copy()算法：

#include <iostream>      // std::cout#include <algorithm>    // std::copy#include <vector>         // std::vectorint main () {  int myints[]={10,20,30,40,50,60,70};  std::vector<int> myvector (7);  std::copy ( myints, myints+7, myvector.begin() );  std::cout << "myvector contains:";  for (std::vector<int>::iterator it = myvector.begin(); it!=myvector.end(); ++it)    std::cout << ' ' << *it;  std::cout << '\n';  return 0;}// Output:// myvector contains: 10 20 30 40 50 60 70

其中std::copy ( myints, myints+7, myvector.begin() );

就是用了一个原生指针做迭代器，用指针的简单算术运算来用做容器区间。

std::search():

// search algorithm example#include <iostream>     // std::cout#include <algorithm>    // std::search#include <vector>       // std::vectorbool mypredicate (int i, int j) {  return (i==j);}int main () {  std::vector<int> haystack;  // set some values:        haystack: 10 20 30 40 50 60 70 80 90  for (int i=1; i<10; i++) haystack.push_back(i*10);  // using default comparison:  int needle1[] = {40,50,60,70};  std::vector<int>::iterator it;  it = std::search (haystack.begin(), haystack.end(), needle1, needle1+4);  if (it!=haystack.end())    std::cout << "needle1 found at position " << (it-haystack.begin()) << '\n';  else    std::cout << "needle1 not found\n";  // using predicate comparison:  int needle2[] = {20,30,50};  it = std::search (haystack.begin(), haystack.end(), needle2, needle2+3, mypredicate);  if (it!=haystack.end())    std::cout << "needle2 found at position " << (it-haystack.begin()) << '\n';  else    std::cout << "needle2 not found\n";  return 0;} Edit & Run/*Output:needle1 found at position 3needle2 not found*/

ref:

－End－