版本3和30间的区别 (跳过第27版)

STL概述

STL是Standard Template Library的缩写，是C++标准库中最强大、最复杂、最有用的部分。STL主要由容器（container）、跌代子（iterator）、算法（algorithm）所组成。还有仿函数（functor）、适配器（adapter）、配置器（allocator）等辅助组件。

1. 容器container

容器是存放和管理数据元素的数据结构，分为两大类：顺序容器（sequence container）和关联容器（associative container）。

顺序容器有：vector（向量，酷似数组）, deque（双端队列）, list（双链表）
关联容器有：map（字典）, set（集合）, multi_map（允许重复键的字典）, multi_set（允许重复键的集合）

除此以外还有：

特殊的容器：string（字符串）, array（C语言原始数组）
容器适配器：stack（栈）, queue（队列）, priority_queue（优先队列）
内部容器：不提供给用户使用，只用来实现其他容器，比如红黑树（用来实现map,set），堆（用来实现priority_queue）

容器一般使用模板类来实现

2. 跌代子iterator

跌代子是用来访问容器内元素的对象，类似指针。

3. 算法algorithm

算法是用来处理容器内的元素的一些操作，比如搜索、排序、拷贝、修改等。算法一般使用函数模板来实现。

4. 仿函数functor

用法类似函数的对象。用重载了operator()的类或者模板类来实现

容器与容器适配器

1. vector向量

1.1. 接口说明

vector的用法类似于数组，不同的是数组空间可以动态分配。

   1 #include <vector>
   2 namespace std {
   3    template< class T, class Allocator = allocator<T> > class vector;
   4 }

T可以是任何类型，但是必须满足：assignable, copyable

1.1.1. 构造方法

   1 vector< int > a2(10); //构造10个元素的vector
   2 vector< int > a3(10, 5); //构造一个10个元素的vector，每个元素都是5
   3 vector< int > a4(a2); //构造一个vector与a2完全一样
   4 vector< int > a1; // 构造一个空的vector
   5 int values[] = {10, 11, 12, 13, 14};
   6 vector< int > a5( values, values+5); //通过迭代子来构造vector
   7

1.1.2. 不变操作和赋值

   1 a1.size( ) //取容器内元素的个数
   2 a1.empty( ) //判断容器是否为空
   3 a1 == a2 //判断两个容器的内容是否相同, 还有!=, <, >, <=, >=
   4 a1 = a2 //将a2全部元素赋给a1
   5 a1.assign( values, values+5 ) //将values[0]到values[4]赋给a1
   6 a1.assign( 10, 5) //给a1赋值10个5
   7

1.1.3. 元素访问

   1 a1[ 5 ] //取第5个元素，下标从0开始
   2 a1.at(5) //取第5个元素，带边界检查
   3 a1.front() //取第0个元素
   4 a1.back() //取最后一个元素
   5

1.1.4. 跌代子

   1 a1.begin() //随机跌代子，指向a1[0]
   2 a1.end()  //随机跌代子，指向最后一个的下一个
   3 a1.rbegin() //随机跌代子，指向最后一个
   4 a1.rend() //随机跌代子，指向a1[0]的前一个
   5

1.1.5. 插入删除操作

   1 a1.insert( a1.begin(), 5); //在a1的最前面插入一个5
   2 a1.insert(a1.end(), 10, 6); //在a1的最后面插入10个6
   3 a1.insert(a1.begin(), values, values+5) //在a1的最前面插入values[0]到values[4]
   4 a1.push_back( 5 ) //在a1的最后面插入一个5
   5 a1.pop_back( ) // 删除a1的最后一个元素
   6 a1.erase( a1.begin() ) //删除a1中的第一个元素
   7 a1.erase( a1.begin(), a1.begin() +2) //删除a1最前面2个元素
   8 a1.resize( 10 ) //将a1元素个数改为10，增加的部分值为默认构造
   9 a1.resize( 10, 6) //将a1元素个数改为10，增加的部分值为6
  10 a1.clear() //清除所有元素
  11

1.2. 用法实例

   1 #include <vector>
   2 int main() {
   3    using namespace std;
   4    vector< string > sentence;
   5    sentence.reserve( 5 );
   6    sentence.push_back( “ Hello, “);
   7    sentence.push_back( “how “);
   8    sentence.push_back( “are “);
   9    sentence.push_back( "you ");
  10    sentence.push_back( “?“);
  11    copy( sentence.begin(), sentence.end(), ostream_iterator<string>(cout, “  “));
  12    cout << endl;
  13    cout << sentence.size() << endl;
  14    cout << sentence.capacity() << endl;
  15    swap( sentence[1], sentence[3]);
  16    sentence.insert( find(sentence.begin(), sentence.end(), “?”), “always”);
  17    sentence.back() = “!”;
  18    copy( sentence.rbegin(), sentence.rend(), ostream_iterator<string>(cout, “  “));
  19    cout << endl;
  20 }

用vector代替数组使用

   1 vector < int > a(10); // int a[10];
   2 a[0] = 1;
   3 a[1] = 2;
   4 a[2] = a[0] + a[1];
   5 for( int i = 0; i < a.size(); i++)
   6    scanf( “%d”, &a[i] );

1.3. vector的实现

vector的实现类似于数据结构中的顺序表

attachment:vector.jpg

   1 template<class T, class Alloc=alloc>
   2 class vector {
   3 public:
   4     typedef T value_type;
   5     typedef value_type* iterator;
   6     typedef value_type& reference;
   7     typedef size_t size_type;
   8 protected:
   9     iterator start;
  10     iterator finish;
  11     iterator end_of_storage;
  12 
  13 
  14 public:
  15     iterator begin() { return start; }
  16     iterator end() { return finish; }
  17     size_type size() const { //返回当前元素个数
  18         return size_type(end() - begin());
  19     }
  20     bool empty() const {
  21         return begin() == end();
  22     }
  23     reference operator[](size_type n) {
  24         return *(begin() + n);
  25     }
  26     reference front() {
  27         return *begin();
  28     }
  29     reference back() {
  30         return *(end() - 1);
  31     }
  32     size_type capacity() const {  //返回当前容量的大小
  33         return size_type(end_of_storage - begin()); 
  34     } 
  35     size_type reserve(size_type n); //改变容量的大小
  36     void push_back(const T& x) {
  37         if(finish != end_of_storage) {
  38             construct(finish, x);
  39             ++finish;
  40         } else {
  41             insert_aux(end(), x);
  42         }
  43     }
  44 protected:
  45     typedef simple_alloc<value_type, Alloc> data_allocator;
  46     void deallocate() {
  47         if(start) data_allocator::deallocate(start, end_of_storage - start);
  48     }
  49     
  50     void insert_aux(iterator position, const T& x) {
  51         if(finish != end_of_storage) {
  52             construct(finish, *(finish-1));
  53             ++finish;
  54             T x_copy = x;
  55             copy_backward(position, finish-2, finish-1);
  56             *position = x_copy;
  57         } else {
  58             const size_type old_size = size();
  59             const size_type len = old_size != 0 ? 2 * old_size : 1;
  60             iterator new_start = data_allocator::alloate(len);
  61             iterator new_finish = new_start;
  62             try {
  63                 new_finish = uninitialized_copy(start, position, new_start);
  64                 construct(new_finish, x);
  65                 ++ new_finish;
  66                 new_finish = uninitialized_copy(position, finish, new_finish);
  67             } catch(...) {
  68                 destroy(new_start, new_finish);
  69                 data_allocator::deallocate(new_start, len);
  70                 throw;
  71             }
  72             destroy(begin(), end());
  73             deallocate();
  74             start = new_start;
  75             finish = new_finish;
  76             end_of_storage = new_start + len;
  77         }
  78     }
  79 };

2. deque双端队列

deque与vector相似，区别是deque两端都是开放的，两端插入删除都很快。在头文件<deque>中定义。 attachment:deque.jpg

实现： attachment:deque_imp.jpg

可以随机访问，但速度比vector稍慢

迭代子是随机跌代子，是一种class而不是原始指针

操作非常相似，增加操作：push_front, pop_front，减少操作：reserve,capacity

任何插入和删除操作都可能使跌代子失效

例子：

   1 int main() {
   2     deque<string> coll;
   3     coll.assign (3, string("string"));
   4     coll.push_back ("last string");
   5     coll.push_front ("first string");
   6     copy (coll.begin(), coll.end(), ostream_iterator<string>(cout,"\n"));
   7     coll.pop_front();
   8     coll.pop_back();
   9     for (int i=1; i<coll.size(); ++i) {
  10         coll[i] = "another " + coll [i];
  11     }
  12     coll.resize (4, "resized string");
  13     copy (coll.begin(), coll.end(), ostream_iterator<string>(cout,"\n"));
  14 }

3. list链表

一般为双链表实现

#include <list> 提供双向跌代子，不能随机访问插入删除操作非常快速插入删除操作不会使跌代子失效提供了一些移动元素的算法，比通用算法更快

   1 c1.swap(c2)：交换两个链表的内容
   2 c.remove(val)
   3 c.remove_if(predictor)
   4 c.unique() 删除重复元素
   5 c.splice() 将一个链表中的元素切一部分到另一个链表
   6 c.sort() 排序
   7 c.merge() 合并两个链表
   8 c.reverse() 倒置

例

   1 void printLists (const list<int>& 11, const list<int>& 12) {
   2 cout << "list1: ";
   3 copy (l1.begin(), l1.end(), ostream_iterator<int>(cout," "));
   4 cout << endl << "list2: ";
   5 copy (12.begin(), 12.end(), ostream_iterator<int>(cout," "));
   6 cout << endl << endl;
   7 }
   8 int main() {
   9 list<int> list1, list2;
  10 for (int i=0; i<6; ++i) {
  11 list1.push_back(i);
  12 list2.push_front(i);
  13 }
  14 printLists(list1, list2);
  15 list2.splice(find(list2.begin(),list2.end(), 3), list1); 
  16 printLists(list1, list2);
  17 list2.splice(list2.end(), list2, list2.begin());
  18 printLists(list1, list2);
  19 list2.sort();
  20 list1 = list2;
  21 list2.unique();
  22 printLists(list1, list2);
  23 list1.merge(list2);
  24 printLists(list1, list2);
  25 }

4. stack栈

#include <stack> namespace std { template <class T, class Container = deque<T> > class stack; } 实现：

主要操作 push() 入栈 top() 取栈顶元素 pop() 出栈例：

   1 int main() {
   2 stack<int> st;
   3 st.push(l);
   4 st.push(2);
   5 st.push(3);
   6 cout << st.top() << ' ';
   7 st.pop() ;
   8 cout << st.top() << ' ';
   9 st.pop() ;
  10 st.top() = 77;
  11 st.push(4);
  12 st.push(5);
  13 st.pop() ;
  14 while (!st.empty()) {
  15 cout << st.top() << ' ';
  16 st.pop() ;
  17 }
  18 cout << endl;
  19 }

5. queue队列

#include <queue> namespace std { template <class T, class Container = deque<T> > class queue; } 实现

主要操作： push pop back front

例

   1 int main() {
   2 queue<string> q;
   3 q.push("These ");
   4 q.push("are ");
   5 q.push("more than ");
   6 cout << q.front();
   7 q.pop();
   8 cout << q.front();
   9 q.pop();
  10 q.push(''four ");
  11 q.push("words!");
  12 q.pop();
  13 cout << q.front();
  14 q.pop();
  15 cout << q.front() << endl;
  16 q.pop();
  17 cout << "number of elements in the queue: " << q.size() << endl;
  18 }

6. priority_queue优先队列

按照大小顺序出队的队列 #include <queue> namespace std { template <class T, class Container = vector<T>, class Compare = less<typename Container::value_type> > class priority_queue; } 实现：堆

push() 入队 top() 读取下一个元素 pop() 删除下一个元素

   1 int main() {
   2 priority_queue<float> q;
   3 q.push(66.6);
   4 q.push(22.2);
   5 q.push(44.4);
   6 cout << q.top() << ' ';
   7 q.pop();
   8 cout << q.top() << endl;
   9 q.pop();
  10 q.push(11.1);
  11 q.push(55.5);
  12 q.push(33.3);
  13 q.pop();
  14 while (!q.empty()) {
  15 cout << q.top() << ' ';
  16 q.pop();
  17 }
  18 cout << endl;
  19 }

7. set与multi_set

在这两种容器中，元素能够根据指定的排序规则自动的排序，以优化查找。两者区别是：set不允许有重复的元素，multi_set允许有重复的元素。

   1 #include <set>
   2 namespace std {
   3 template <class T,
   4 class Compare = less<T>,
   5 class Allocator = allocator<T> >
   6 class set;
   7 template <class T,
   8 class Compare = less<T>,
   9 class Allocator = allocator<T> >
  10 class multiset;
  11 }

内部结构

例子：

   1 #include <iostream>
   2 #include <set>
   3 using namespace std;
   4 int main() {
   5 typedef set<int,greater<int> > IntSet;
   6 IntSet coll1; // empty set container
   7 coll1.insert(4);
   8 coll1.insert(3);
   9 coll1.insert(5);
  10 coll1.insert(1);
  11 coll1.insert(6);
  12 coll1.insert(2);
  13 coll1.insert(5);
  14 IntSet::iterator pos;
  15 for (pos = coll1.begin(); pos != coll1.end(); ++pos) {
  16 cout << *pos << ' ';
  17 }
  18 cout << endl;
  19 pair<IntSet::iterator,bool> status = coll1.insert(4);
  20 if (status.second) {
  21 cout << "4 inserted as element "<< distance (coll1.begin(),status. first) + 1<< endl;
  22 }else {
  23 cout << "4 already exists" << endl;
  24 }
  25 set<int> coll2(coll1.begin(),
  26 coll1.end());
  27 copy (coll2.begin(), coll2.end(), ostream_iterator<int>(cout," "));
  28 cout << endl;
  29 coll2.erase (coll2.begin(), coll2.find(3));
  30 int num;
  31 num = coll2.erase (5);
  32 cout << num << " element(s) removed" << endl;
  33 copy (coll2.begin(), coll2.end(), ostream_iterator<int>(cout," "));
  34 cout << endl;
  35 }

8. map与multi_map

存放关键字与对应值的数据结构

   1 #include <map>
   2 namespace std {
   3 template <class Key, class T,
   4 class Compare = less<Key>,
   5 class Allocator = allocator<pair<const Key,T> > >
   6 class map;
   7 template <class Key, class T,
   8 class Compare = less<Key>,
   9 class Allocator = allocator<pair<const Key,T> > >
  10 class multimap;
  11 }

内部结构

   1 #include <iostream>
   2 #include <map>
   3 #include <string>
   4 using namespace std;
   5 int main() {
   6 typedef map<string,float> StringFloatMap;
   7 StringFloatMap stocks; // create empty container
   8 stocks["BASF"] = 369.50;
   9 stocks["VW"] = 413.50;
  10 stocks["Daimler"] = 819.00;
  11 stocks["BMW"] = 834.00;
  12 stocks["Siemens"] = 842.20;
  13 StringFloatMap::iterator pos;
  14 for (pos = stocks.begin(); pos != stocks.end(); ++pos) {
  15 cout << "stock: " << pos->first << "\t" << "price: " << pos->second << endl;
  16 }
  17 cout << endl;
  18 for (pos = stocks.begin(); pos != stocks.end(); ++pos) {
  19 pos->second *= 2;
  20 }
  21 for (pos = stocks.begin(); pos != stocks.end(); ++pos) {
  22 cout << "stock: " << pos->first << "\t"<< "price: " << pos->second << endl;
  23 }
  24 cout << endl;
  25 stocks["Volkswagen"] = stocks["VW"];
  26 stocks.erase("VW");
  27 for (pos = stocks.begin(); pos != stocks.end(); ++pos) {
  28 cout << "stock: " << pos->first << "\t"<< "price: " << pos->second << endl;
  29 }
  30 }

算法Algorithm

对容器内的数据进行处理的函数

#include <algorithm> //一般算法

#include <numeric> //数值算法

#include <functional> //仿函数

1. 算法分类

非变动性算法

for_each
count
count_if
min_element
max_element
find
find_if
search_n
search
find_end
find_first_of
adjacent_find
equal
mismatch
lexicographical_compare

变动性算法

copy
copy_backward
transform
merge
swap_ranges
fill
fill_n
generate
generate_n
replace
replace_if
replace_copy
replace_copy_if

移除算法

remove
remove_if
remove_copy
remove_copy_if
unique
unique_copy

变序性算法 reverse reverse_copy rotate rotate_copy next_permutation prev_permutation random_shuffle partition stable_partition

排序算法 sort stable_sort partial_sort partial_sort_copy nth_element partition stable_partition make_heap push_heap pop_heap sort_heap

已序区间算法 binary_search includes lower_bound upper_bound equal_range merge set_union set_intersection set_difference set_symmetric_difference inplace_merge

数值算法 accumulate inner_product adjacent_difference partial_sum

2. for_each

对区间内每一个元素采用某一种操作

实现：

template <class InputIterator, class UnaryFunction>
UnaryFunction for_each(InputIterator first, InputIterator last, UnaryFunction f) {
   while( first != end) {
      f(*first);
      ++first;
}
return f;
}

用例1：

void print ( int elem) {
   cout << elem << ‘ ‘;
}
int main() {
vector< int > col( 5, 10); 
for_each( col.begin(), col.end(), print);
cout << endl;
}

用例2：

template< class T>
class AddValue{
private:
T value;
public:
AddValue( const T&v) : value(v) {}
void operator()(T&elem) const { elem+=value; }
};
int main() {
vector<int > col(5, 10);
for_each(col.begin(), col.end(), AddValue<int>(10));
   copy( col.begin(), col.end(), ostream_iterator<int>(cout, “  “));
}

用例3：

class MeanValue {
private:
   int num, sum;
public:
   MeanValue() : num(0), sum(0) {}
   void operator()( int elem ) { num ++; sum+=elem; }
   double value() { return static_cast<double>(sum) / static_cast<double>(num); }
};
int main() {
vector<int> col(5, 10);
MeanValue  mv = for_each(col.begin(), col.end(), MeanValue() );
cout << mv.value();
}

3. transform

功能1：将区间内每个元素作变换，存储到另一个空间里面

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

功能2：将两个区间内的元素作变换，存储到另一个空间内

template <class InputIterator1, class InputIterator2, class OutputIterator, class BinaryFunction>
OutputIterator transform(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, OutputIterator result, BinaryFunction binary_op) {
while( first1 != last1 ) {
    *result = op(*first1, *first2);
    ++result;
    ++first1;
    ++first2;
}
return result;
}

用例1：

int main() {
vector< int > c1(5, 10);
transform( c1.begin(), c1.end(), c1.begin(), negate<int>() );
list < int> c2;
transform( c1.begin(), c1.end(), back_inserter(c2), bind2nd(multiplies<int>(), 5));
transform( c2.rbegin(), c2.rend(), ostream_iterator<int>(cout, “ “), negate<int>());
transform( c1.begin(), c1.end(), c1.begin(), c1.begin(), multiplies<int>());
transform( c1.begin(), c1.end(), c2.rbegin(), c1.begin(), plus<int>());
transform( c1.begin(), c1.end(), c1.begin(), ostream_iterator<int>(cout, “ “), minus<int>() );
}

仿函数(Functor, Function Object)

能像函数一样使用的对象。普通函数、函数指针、定义了operator()的类的对象都可以作为仿函数。

#include <functional>

1. Generator

不带参数的仿函数比如： rand

2. Unary Function

带一个参数的仿函数。比如： abs negate identity

3. Predicate

返回真或假的Unary Function 比如： logical_not

4. Binary Function

带两个参数的仿函数。 plus minus multiplies divides modulus Binary Predicate 返回真或假的Binary Function less greater equal_to not_equal_to less_equal greater_equal logical_and logical_or auxiliary function bind1st bind2nd not1 not2 mem_fun_ref mem_fun ptr_fun compose1 compose2 Sample 例1 find_if (coll.begin(),coll.end(), bind2nd (greater<int>(),42));

例2 pos = find_if (coll.begin() , coll.end(), not1 (bind2nd(modulus<int>(),2)));

list<int> L; list<int>::iterator first_positive = find_if(L.begin(), L.end(), bind2nd(greater<int>(), 0));

例3 class Person { private: std::string name; public: void print() const { std::cout << name << std::endl; } void printWithPrefix (std::string prefix) const { std::cout << prefix << name << std::endl; } }; void foo (const std::vector<Person>& coll){ for_each (coll.begin(), coll.end(), mem_fun_ref(&Person::print)); for_each (coll.begin(), coll.end(), bind2nd (mem_fun_ref (&Person::printWithPrefix), "person: ")); } void ptrfoo (const std::vector<Person*>& coll) { for_each (coll.begin() , coll.end(), mem_fun(&Person::print)); for_each (coll.begin() , coll.end(), bind2nd(mem_fun(&Person::printWithPrefix), "person: ")); }

例4 bool check(int elem); pos = find_if (coll.begin(), coll.end(), not1(ptr_fun(check))); pos = find_if (coll.begin(), coll.end(), bind2nd(ptr_fun(strcmp),"")); transform(first, last, first, compose1(negate<double>, ptr_fun(fabs)));

例5 list<int> L; list<int>::iterator in_range = find_if(L.begin(), L.end(),

not1(compose2(logical_and<bool>(), bind2nd(greater_equal<int>(), 1), bind2nd(less_equal<int>(), 10))));

例6 char str[MAXLEN]; const char* wptr = find_if(str, str + MAXLEN, compose2(not2(logical_or<bool>()), bind2nd(equal_to<char>(), ' '), bind2nd(equal_to<char>(), '\n')));

Iterator迭代子

迭代子是一种能够遍历容器里面的全部或者部分元素的对象，一个迭代子能够表示容器里面一个特定的位置。

使用begin(), end()获得容器的迭代子。迭代子的类型会随着容器的不同而不同，可表示为container<T>::iterator,如果支持双向跌代，则可以通过rbegin(), rend()获得反向跌代子。反向跌代子的类型为：container<T>::reverse_iterator,

1. 分类

Input：只能单向读取，比如istream
Output：只能单向写入，比如ostream
Forward：单向读取和写入，具有Input和Output跌代子的全部能力，比如slist
Bidirectional：双向读取和写入，具有Forward跌代子的全部能力，比如list, set, map
Random：随机读取和写入，具有Bidirectional跌代子的全部能力，比如vector, deque

2. 运算符

迭代子最基本的操作有：

iter++, ++iter：让跌代子移动到下一个元素，有前置后置两种形式。
*iter：返回迭代子当前位置上的元素。如果是Input代子，返回元素的值，只能读取；如果是Output跌代子，返回引用，只能写入。
iter1 == iter2 , iter1 != iter2：判断两个跌代子是否指向同一个位置。（Output没有此操作）
iter1 = iter2：改变跌代子指向的位置。（Output没有此操作）
iter ->：如果元素是类（结构体），则可以使用->直接访问元素的成员。
iter --, --iter：使用--移动到前一个元素，有前置后置两种形式。（双向跌代子和随机跌代子）
iter [n]：后面第n个的元素（Random跌代子）
iter += n：往后面移动n个位置（Random跌代子）
iter -= n：往前面移动n个位置（Random跌代子）
iter + n, n + iter：后面第n个位置（Random跌代子）
iter - n：前面第n个位置（Random跌代子）
iter1 - iter2: 两个元素之间的距离（Random跌代子）
iter1<iter2, iter1 > iter2, iter1 <= iter2, iter1 >= iter2: 比较两个跌代子的位置（Random跌代子）

3. 辅助函数

advance(iter, n)：将跌代子后移n个位置
distance(iter1, iter2)：两个跌代子之间的距离

4. 迭代子适配器

reverse iterator
insert iterators(back_inserter, front_inserter, inserter)
Stream Iterators(ostream_iterator, istream_iterator)

5. Sample

例1

   1 //OK for forward iterators
   2 //IMPOSSIBLE for output iterators
   3 while (pos != coll.end()) {
   4   *pos = foo();
   5   ++pos;
   6 }

例2

   1 int main() {
   2   vector<int> coll;
   3   for (int i=-3; i<=9; ++i) {
   4     coll.push_back (i);
   5   }
   6   cout << "number/distance: " << coll.end()-coll.begin() << endl;
   7   vector<int>::iterator pos;
   8   for (pos=coll.begin(); pos<coll.end(); ++pos) {
   9     cout << *pos << ' ';
  10   }
  11   for (int i=0; i<coll.size(); ++i) {
  12     cout << coll.begin() [i] << ' ';
  13   }
  14   for (pos = coll.begin(); pos < coll.end()-1; pos += 2) {
  15     cout << *pos << ' ';
  16   }
  17 }

例3

   1 int main() {
   2   list<int> coll;
   3   //insert elements from 1 to 9
   4   for (int i=1; i<=9; ++i) {
   5     coll.push_back(i);
   6   }
   7   list<int>::iterator pos = coll.begin();
   8   cout << *pos << endl;
   9   advance (pos, 3);
  10   cout << *pos << endl;
  11   advance (pos, -1);
  12   cout << *pos << endl;
  13 }

例4

   1 int main(){
   2   list<int> coll;
   3   for (int i=-3; i<=9; ++i) {
   4     coll.push_back(i);
   5   }
   6   list<int>::iterator pos;
   7   pos = find (coll.begin(), coll.end(), 5);
   8   if (pos != coll.end()) {
   9     cout << distance(coll.begin(),pos) << endl;
  10   }
  11   else {
  12     cout << "5 not found" << endl;
  13   }
  14 }

例5

   1 void print (int elem) {
   2   cout << elem << ' ';
   3 }
   4 int main() {
   5   list<int> coll;
   6   for (int i=1; i<=9; ++i) {
   7     coll.push_back(i);
   8   }
   9   for_each (coll.begin(), coll.end(), print);
  10   for_each (coll.rbegin(), coll.rend(), print);
  11 }

例6

   1 int main() {
   2   vector<int> coll;
   3   for (int i=1; i<=9; ++i) {
   4     coll.push_back(i);
   5   }
   6   vector<int>::iterator pos;
   7   pos = find (coll.begin(), coll.end(), 5);
   8   cout << "pos: " << *pos << endl;
   9   vector<int>::reverse_iterator rpos(pos);
  10   cout << "rpos: " << *rpos <<endl;
  11 }

例7

   1 void print (int elem) {
   2   cout << elem << ' ';
   3 }
   4 int main() {
   5   deque<int> coll;
   6   for (int i=1; i<=9; ++i) {
   7     coll.push_back(i);
   8   }
   9   deque<int>::iterator pos1;
  10   pos1 = find (coll.begin(), coll.end(), 2); 
  11   deque<int>::iterator pos2;
  12   pos2 = find (coll.begin(), coll.end(), 7); 
  13   for_each (pos1, pos2, print); 
  14   deque<int>::reverse_iterator rpos1(pos1);
  15   deque<int>::reverse_iterator rpos2(pos2);
  16   for.each (rpos2, rpos1, print);
  17 }

例8

   1 int main(){
   2   list<int> coll;
   3   for (int i=1; i<=9; ++i) {
   4     coll.push_back(i);
   5   }
   6   list<int>::iterator pos;
   7   pos = find (coll.begin(), coll.end(),5); 
   8   cout << "pos: " << *pos << endl;
   9   list<int>::reverse_iterator rpos(pos);
  10   cout << "rpos: " << *rpos << endl;
  11   list<int>::iterator rrpos;
  12   rrpos = rpos.base();
  13   cout << "rrpos: " << *rrpos << endl;
  14 }

例9

   1 int main() {
   2   vector<int> coll;
   3   back_insert_iterator<vector<int> > iter(coll);
   4   *iter = 1;
   5   iter++;
   6   *iter = 2;
   7   iter++;
   8   *iter = 3;
   9   copy( col1.begin(), col1.end(), ostream_iterator<int>(cout, “  “));
  10   back_inserter(coll) = 44;
  11   back_inserter(coll) = 55;
  12   copy( col1.begin(), col1.end(), ostream_iterator<int>(cout, “  “));
  13   copy (coll .begin(), coll.end(), back_inserter(coll));
  14   copy( col1.begin(), col1.end(), ostream_iterator<int>(cout, “  “));
  15 }

例10

   1 int main() {
   2   list<int> coll;
   3   front_insert_iterator<list<int> > iter(coll);
   4   *iter = 1;
   5   iter++;
   6   *iter = 2;
   7   iter++;
   8   *iter = 3;
   9   copy( col1.begin(), col1.end(), ostream_iterator<int>(cout, “  “));
  10   front_inserter(coll) = 44;
  11   front_inserter(coll) = 55;
  12   copy( col1.begin(), col1.end(), ostream_iterator<int>(cout, “  “));
  13   copy (coll.begin(), coll.end(), front_inserter(coll)); 
  14   copy( col1.begin(), col1.end(), ostream_iterator<int>(cout, “  “));
  15 }

例11

   1 int main() {
   2   ostream_iterator<int> intWriter(cout,"\n");
   3   *intWriter = 42;
   4   intWriter++;
   5   *intWriter = 77;
   6   intWriter++;
   7   *intWriter = -5;
   8   vector<int> coll;
   9   for (int i=1; i<=9; ++i) {
  10     coll.push_back(i);
  11   }
  12   copy (coll.begin(), coll.end(), ostream_iterator<int>(cout));
  13   copy (coll.gin(), coll.end(), ostream_iterator<int>(cout," < "));
  14 }

例12

   1 int main(){
   2   istream_iterator<int> intReader(cin);
   3   istream_iterator<int> intReaderEOF;
   4   while (intReader != intReaderEOF) {
   5     cout << "once: " << *intReader << endl;
   6     cout << "once again: " << *intReader << endl;
   7     ++intReader;
   8   }
   9 }

例13

   1 int main() {
   2   istream_iterator<string> cinPos(cin);
   3   ostream_iterator<string> coutPos(cout," ");
   4   while (cinPos != istream_iterator<string>()) {
   5     advance (cinPos, 2);
   6     if (cinPos != istream_iterator<string>()) {
   7       *coutPos++ = *cinPos++;
   8     }
   9   }
  10   cout << endl;
  11 }

例14

   1 int main() {
   2   vector<Date> e;
   3   copy( istream_iterator<Date>(cin), istream_iterator<Date>(), back_inserter(e));
   4   vector<Date>::iterator first = find(e.begin(), e.end(), "01/01/95");
   5   vector<Date>::iterator last = find(e.begin(), e.end(), "12/31/95");
   6   *last = "12/30/95";
   7   copy(first, last, ostream_iterator<Date>(cout, "\n"));
   8   e.insert(--e.end(), TodaysDate());
   9   copy( first, last, ostream_iterator<Date>(cout, "\n") );
  10 }

注：早先获得的跌代子在特定的操作后会失效！！vector的迭代子在插入、删除以及重新分配内存后可能会失效。

练习

Write a program to print a histogram of the frequencies of different characters in its input.
Write a program to print a histogram of the lengths of words in its input. It is easy to draw the histogram with the bars horizontal; a vertical orientation is more challenging.
Write a program that prints the distinct words in its input sorted into decreasing order of frequency of occurrence. Precede each word by its count.
Write a cross-referencer that prints a list of all words in a document, and for each word, a list of the line numbers on which it occurs.
Write the program tail, which prints the last n lines of its input. By default, n is set to 10, let us say, but it can be changed by an optional argument so that
```
tail -n
```
prints the last n lines. The program should behave rationally no matter how unreasonable the input or the value of n. Write the program so it makes the best use of available storage.
Write a program to remove all comments from a C program. Don't forget to handle quoted strings and character constants properly. C comments don't nest.
Write a program to check a C program for rudimentary syntax errors like unmatched parentheses, brackets and braces. Don't forget about quotes, both single and double, escape sequences, and comments. (This program is hard if you do it in full generality.)
Write a program to implement a queue using two stacks.

-  ⇤ ← 于2006-02-22 00:12:43修订的的版本3 → 
  大小: 4234
  编辑: czk
  备注:
+   ← 于2006-02-28 23:15:45修订的的版本30 → ⇥
  大小: 29679
  编辑: czk
  备注:
-删除的内容标记成这样。
+加入的内容标记成这样。
 行号 20:
-跌代子是用来访问容器内元素的对象，类似指针。 跌代子根据能力的不同，分为：

 * 随机跌代子（vector、deque的迭代子）
 * 双向跌代子（list的迭代子）
 * 单向跌代子
 * 输入跌代子
 * 输出跌代子

另外还有

 * 跌代子适配器：将原来不是迭代子的东西变成迭代子，或者将一种迭代子变成另一种迭代子（比如back_inserter, front_inserter,  inserter, 反向迭代子，ostream_iterator, istream_iterator）
+跌代子是用来访问容器内元素的对象，类似指针。
-行号 38:
+行号 28:
-= vector向量 =
== 接口说明 ==
+= 容器与容器适配器 =
== vector向量 ==
=== 接口说明 ===
-行号 46:
+行号 37:
-   template< class T, class Allocator = allocator<T> > vector;
+   template< class T, class Allocator = allocator<T> > class vector;
-行号 52:
+行号 43:
-=== 构造方法 ===
+==== 构造方法 ====
-行号 63:
+行号 54:
-=== 不变操作和赋值 ===
+==== 不变操作和赋值 ====
-行号 74:
+行号 65:
-=== 元素访问 ===
+==== 元素访问 ====
-行号 80:
+行号 71:
-a1.end() //取最后一个元素
}}}

=== 跌代子 ===
+a1.back() //取最后一个元素
}}}

==== 跌代子 ====
-行号 92:
+行号 83:
-=== 插入删除操作 ===
+==== 插入删除操作 ====
-行号 106:
+行号 97:
+=== 用法实例 ===
{{{
#!cplusplus 
#include <vector>
int main() {
   using namespace std;
   vector< string > sentence;
   sentence.reserve( 5 );
   sentence.push_back( “ Hello, “);
   sentence.push_back( “how “);
   sentence.push_back( “are “);
   sentence.push_back( "you ");
   sentence.push_back( “?“);
   copy( sentence.begin(), sentence.end(), ostream_iterator<string>(cout, “  “));
   cout << endl;
   cout << sentence.size() << endl;
   cout << sentence.capacity() << endl;
   swap( sentence[1], sentence[3]);
   sentence.insert( find(sentence.begin(), sentence.end(), “?”), “always”);
   sentence.back() = “!”;
   copy( sentence.rbegin(), sentence.rend(), ostream_iterator<string>(cout, “  “));
   cout << endl;
}
}}}

用vector代替数组使用

{{{
#!cplusplus 
vector < int > a(10); // int a[10];
a[0] = 1;
a[1] = 2;
a[2] = a[0] + a[1];
for( int i = 0; i < a.size(); i++)
   scanf( “%d”, &a[i] );
}}}

=== vector的实现 ===
vector的实现类似于数据结构中的顺序表

attachment:vector.jpg

{{{#!cplusplus
template<class T, class Alloc=alloc>
class vector {
public:
    typedef T value_type;
    typedef value_type* iterator;
    typedef value_type& reference;
    typedef size_t size_type;
protected:
    iterator start;
    iterator finish;
    iterator end_of_storage;


public:
    iterator begin() { return start; }
    iterator end() { return finish; }
    size_type size() const { //返回当前元素个数
        return size_type(end() - begin());
    }
    bool empty() const {
        return begin() == end();
    }
    reference operator[](size_type n) {
        return *(begin() + n);
    }
    reference front() {
        return *begin();
    }
    reference back() {
        return *(end() - 1);
    }
    size_type capacity() const {  //返回当前容量的大小
        return size_type(end_of_storage - begin()); 
    } 
    size_type reserve(size_type n); //改变容量的大小
    void push_back(const T& x) {
        if(finish != end_of_storage) {
            construct(finish, x);
            ++finish;
        } else {
            insert_aux(end(), x);
        }
    }
protected:
    typedef simple_alloc<value_type, Alloc> data_allocator;
    void deallocate() {
        if(start) data_allocator::deallocate(start, end_of_storage - start);
    }
    
    void insert_aux(iterator position, const T& x) {
        if(finish != end_of_storage) {
            construct(finish, *(finish-1));
            ++finish;
            T x_copy = x;
            copy_backward(position, finish-2, finish-1);
            *position = x_copy;
        } else {
            const size_type old_size = size();
            const size_type len = old_size != 0 ? 2 * old_size : 1;
            iterator new_start = data_allocator::alloate(len);
            iterator new_finish = new_start;
            try {
                new_finish = uninitialized_copy(start, position, new_start);
                construct(new_finish, x);
                ++ new_finish;
                new_finish = uninitialized_copy(position, finish, new_finish);
            } catch(...) {
                destroy(new_start, new_finish);
                data_allocator::deallocate(new_start, len);
                throw;
            }
            destroy(begin(), end());
            deallocate();
            start = new_start;
            finish = new_finish;
            end_of_storage = new_start + len;
        }
    }
};
}}}

== deque双端队列 ==
deque与vector相似，区别是deque两端都是开放的，两端插入删除都很快。在头文件<deque>中定义。
attachment:deque.jpg

实现：
attachment:deque_imp.jpg

可以随机访问，但速度比vector稍慢

迭代子是随机跌代子，是一种class而不是原始指针

操作非常相似，增加操作：push_front, pop_front，减少操作：reserve,capacity

任何插入和删除操作都可能使跌代子失效

例子：

例子：
{{{#!cplusplus
int main() {
    deque<string> coll;
    coll.assign (3, string("string"));
    coll.push_back ("last string");
    coll.push_front ("first string");
    copy (coll.begin(), coll.end(), ostream_iterator<string>(cout,"\n"));
    coll.pop_front();
    coll.pop_back();
    for (int i=1; i<coll.size(); ++i) {
        coll[i] = "another " + coll [i];
    }
    coll.resize (4, "resized string");
    copy (coll.begin(), coll.end(), ostream_iterator<string>(cout,"\n"));
}
}}}

== list链表 ==
一般为双链表实现

#include <list>
提供双向跌代子，不能随机访问
插入删除操作非常快速
插入删除操作不会使跌代子失效
提供了一些移动元素的算法，比通用算法更快
{{{#!cplusplus
c1.swap(c2)：交换两个链表的内容
c.remove(val)
c.remove_if(predictor)
c.unique() 删除重复元素
c.splice() 将一个链表中的元素切一部分到另一个链表
c.sort() 排序
c.merge() 合并两个链表
c.reverse() 倒置
}}}

例
{{{#!cplusplus
void printLists (const list<int>& 11, const list<int>& 12) {
cout << "list1: ";
copy (l1.begin(), l1.end(), ostream_iterator<int>(cout," "));
cout << endl << "list2: ";
copy (12.begin(), 12.end(), ostream_iterator<int>(cout," "));
cout << endl << endl;
}
int main() {
list<int> list1, list2;
for (int i=0; i<6; ++i) {
list1.push_back(i);
list2.push_front(i);
}
printLists(list1, list2);
list2.splice(find(list2.begin(),list2.end(), 3), list1); 
printLists(list1, list2);
list2.splice(list2.end(), list2, list2.begin());
printLists(list1, list2);
list2.sort();
list1 = list2;
list2.unique();
printLists(list1, list2);
list1.merge(list2);
printLists(list1, list2);
}
}}}

== stack栈 ==
#include <stack>
namespace std {
template <class T, class Container = deque<T> >
class stack;
}
实现：

主要操作
push() 入栈
top() 取栈顶元素
pop() 出栈
例：
{{{#!cplusplus
int main() {
stack<int> st;
st.push(l);
st.push(2);
st.push(3);
cout << st.top() << ' ';
st.pop() ;
cout << st.top() << ' ';
st.pop() ;
st.top() = 77;
st.push(4);
st.push(5);
st.pop() ;
while (!st.empty()) {
cout << st.top() << ' ';
st.pop() ;
}
cout << endl;
}
}}}

== queue队列 ==
#include <queue>
namespace std {
template <class T, class Container = deque<T> >
class queue;
}
实现

主要操作：
push
pop
back
front

例
{{{#!cplusplus
int main() {
queue<string> q;
q.push("These ");
q.push("are ");
q.push("more than ");
cout << q.front();
q.pop();
cout << q.front();
q.pop();
q.push(''four ");
q.push("words!");
q.pop();
cout << q.front();
q.pop();
cout << q.front() << endl;
q.pop();
cout << "number of elements in the queue: " << q.size() << endl;
}
}}}

== priority_queue优先队列 ==
按照大小顺序出队的队列
#include <queue>
namespace std {
template <class T, class Container = vector<T>, class Compare = less<typename Container::value_type> >
class priority_queue;
}
实现：堆

push() 入队
top() 读取下一个元素
pop() 删除下一个元素

{{{#!cplusplus
int main() {
priority_queue<float> q;
q.push(66.6);
q.push(22.2);
q.push(44.4);
cout << q.top() << ' ';
q.pop();
cout << q.top() << endl;
q.pop();
q.push(11.1);
q.push(55.5);
q.push(33.3);
q.pop();
while (!q.empty()) {
cout << q.top() << ' ';
q.pop();
}
cout << endl;
}
}}}

== set与multi_set ==
在这两种容器中，元素能够根据指定的排序规则自动的排序，以优化查找。两者区别是：set不允许有重复的元素，multi_set允许有重复的元素。
{{{#!cplusplus
#include <set>
namespace std {
template <class T,
class Compare = less<T>,
class Allocator = allocator<T> >
class set;
template <class T,
class Compare = less<T>,
class Allocator = allocator<T> >
class multiset;
}
}}}
内部结构

例子：
{{{#!cplusplus
#include <iostream>
#include <set>
using namespace std;
int main() {
typedef set<int,greater<int> > IntSet;
IntSet coll1; // empty set container
coll1.insert(4);
coll1.insert(3);
coll1.insert(5);
coll1.insert(1);
coll1.insert(6);
coll1.insert(2);
coll1.insert(5);
IntSet::iterator pos;
for (pos = coll1.begin(); pos != coll1.end(); ++pos) {
cout << *pos << ' ';
}
cout << endl;
pair<IntSet::iterator,bool> status = coll1.insert(4);
if (status.second) {
cout << "4 inserted as element "<< distance (coll1.begin(),status. first) + 1<< endl;
}else {
cout << "4 already exists" << endl;
}
set<int> coll2(coll1.begin(),
coll1.end());
copy (coll2.begin(), coll2.end(), ostream_iterator<int>(cout," "));
cout << endl;
coll2.erase (coll2.begin(), coll2.find(3));
int num;
num = coll2.erase (5);
cout << num << " element(s) removed" << endl;
copy (coll2.begin(), coll2.end(), ostream_iterator<int>(cout," "));
cout << endl;
}
}}}
== map与multi_map ==
存放关键字与对应值的数据结构
{{{#!cplusplus
#include <map>
namespace std {
template <class Key, class T,
class Compare = less<Key>,
class Allocator = allocator<pair<const Key,T> > >
class map;
template <class Key, class T,
class Compare = less<Key>,
class Allocator = allocator<pair<const Key,T> > >
class multimap;
}
}}}
内部结构
{{{#!cplusplus
#include <iostream>
#include <map>
#include <string>
using namespace std;
int main() {
typedef map<string,float> StringFloatMap;
StringFloatMap stocks; // create empty container
stocks["BASF"] = 369.50;
stocks["VW"] = 413.50;
stocks["Daimler"] = 819.00;
stocks["BMW"] = 834.00;
stocks["Siemens"] = 842.20;
StringFloatMap::iterator pos;
for (pos = stocks.begin(); pos != stocks.end(); ++pos) {
cout << "stock: " << pos->first << "\t" << "price: " << pos->second << endl;
}
cout << endl;
for (pos = stocks.begin(); pos != stocks.end(); ++pos) {
pos->second *= 2;
}
for (pos = stocks.begin(); pos != stocks.end(); ++pos) {
cout << "stock: " << pos->first << "\t"<< "price: " << pos->second << endl;
}
cout << endl;
stocks["Volkswagen"] = stocks["VW"];
stocks.erase("VW");
for (pos = stocks.begin(); pos != stocks.end(); ++pos) {
cout << "stock: " << pos->first << "\t"<< "price: " << pos->second << endl;
}
}
}}}

= 算法Algorithm =

对容器内的数据进行处理的函数

#include <algorithm>  //一般算法

#include <numeric>  //数值算法

#include <functional>  //仿函数


== 算法分类 ==
非变动性算法
 * for_each
 * count
 * count_if
 * min_element
 * max_element
 * find
 * find_if
 * search_n
 * search
 * find_end
 * find_first_of
 * adjacent_find
 * equal
 * mismatch
 * lexicographical_compare

变动性算法
 * copy
 * copy_backward
 * transform
 * merge
 * swap_ranges
 * fill
 * fill_n
 * generate
 * generate_n
 * replace
 * replace_if
 * replace_copy
 * replace_copy_if 

移除算法
 * remove
 * remove_if
 * remove_copy
 * remove_copy_if
 * unique
 * unique_copy

变序性算法
reverse
reverse_copy
rotate
rotate_copy
next_permutation
prev_permutation
random_shuffle
partition
stable_partition

排序算法
sort
stable_sort
partial_sort
partial_sort_copy
nth_element
partition
stable_partition
make_heap
push_heap
pop_heap
sort_heap

已序区间算法
binary_search
includes
lower_bound
upper_bound
equal_range
merge
set_union
set_intersection
set_difference
set_symmetric_difference
inplace_merge

数值算法
accumulate
inner_product
adjacent_difference
partial_sum

== for_each ==
对区间内每一个元素采用某一种操作

实现：
{{{
template <class InputIterator, class UnaryFunction>
UnaryFunction for_each(InputIterator first, InputIterator last, UnaryFunction f) {
   while( first != end) {
      f(*first);
      ++first;
}
return f;
}
}}}
用例1：
{{{
void print ( int elem) {
   cout << elem << ‘ ‘;
}
int main() {
vector< int > col( 5, 10); 
for_each( col.begin(), col.end(), print);
cout << endl;
}
}}}
用例2：
{{{
template< class T>
class AddValue{
private:
T value;
public:
AddValue( const T&v) : value(v) {}
void operator()(T&elem) const { elem+=value; }
};
int main() {
vector<int > col(5, 10);
for_each(col.begin(), col.end(), AddValue<int>(10));
   copy( col.begin(), col.end(), ostream_iterator<int>(cout, “  “));
}
}}}
用例3：
{{{
class MeanValue {
private:
   int num, sum;
public:
   MeanValue() : num(0), sum(0) {}
   void operator()( int elem ) { num ++; sum+=elem; }
   double value() { return static_cast<double>(sum) / static_cast<double>(num); }
};
int main() {
vector<int> col(5, 10);
MeanValue  mv = for_each(col.begin(), col.end(), MeanValue() );
cout << mv.value();
}
}}}
== transform ==
功能1：将区间内每个元素作变换，存储到另一个空间里面
{{{
template <class InputIterator, class OutputIterator, class UnaryFunction>
OutputIterator transform(InputIterator first, InputIterator last, OutputIterator result, UnaryFunction op) {
while( first != last ) {
    *result = op(*first);
    ++result;
    ++first;
}
return result;
}
}}}
功能2：将两个区间内的元素作变换，存储到另一个空间内
{{{
template <class InputIterator1, class InputIterator2, class OutputIterator, class BinaryFunction>
OutputIterator transform(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, OutputIterator result, BinaryFunction binary_op) {
while( first1 != last1 ) {
    *result = op(*first1, *first2);
    ++result;
    ++first1;
    ++first2;
}
return result;
}
}}}
用例1：
{{{
int main() {
vector< int > c1(5, 10);
transform( c1.begin(), c1.end(), c1.begin(), negate<int>() );
list < int> c2;
transform( c1.begin(), c1.end(), back_inserter(c2), bind2nd(multiplies<int>(), 5));
transform( c2.rbegin(), c2.rend(), ostream_iterator<int>(cout, “ “), negate<int>());
transform( c1.begin(), c1.end(), c1.begin(), c1.begin(), multiplies<int>());
transform( c1.begin(), c1.end(), c2.rbegin(), c1.begin(), plus<int>());
transform( c1.begin(), c1.end(), c1.begin(), ostream_iterator<int>(cout, “ “), minus<int>() );
}
}}}

= 仿函数(Functor, Function Object) =
能像函数一样使用的对象。普通函数、函数指针、定义了operator()的类的对象都可以作为仿函数。
{{{
#include <functional>
}}}
== Generator ==
不带参数的仿函数
比如：
rand
== Unary Function ==
带一个参数的仿函数。
比如：
abs
negate
identity
== Predicate ==
返回真或假的Unary Function
比如：
logical_not
== Binary Function ==
带两个参数的仿函数。
plus
minus
multiplies
divides
modulus
Binary Predicate
返回真或假的Binary Function
less
greater
equal_to
not_equal_to
less_equal
greater_equal
logical_and
logical_or
auxiliary function
bind1st
bind2nd
not1
not2
mem_fun_ref
mem_fun
ptr_fun
compose1
compose2
Sample
例1
find_if (coll.begin(),coll.end(), bind2nd (greater<int>(),42));

例2
pos = find_if (coll.begin() , coll.end(), not1 (bind2nd(modulus<int>(),2))); 

list<int> L;
list<int>::iterator first_positive = find_if(L.begin(), L.end(), bind2nd(greater<int>(), 0));

例3
class Person {
private:
std::string name;
public:
void print() const {
std::cout << name << std::endl;
}
void printWithPrefix (std::string prefix) const {
std::cout << prefix << name << std::endl;
}
};
void foo (const std::vector<Person>& coll){
for_each (coll.begin(), coll.end(), mem_fun_ref(&Person::print));
for_each (coll.begin(), coll.end(), bind2nd (mem_fun_ref (&Person::printWithPrefix), "person: "));
}
void ptrfoo (const std::vector<Person*>& coll) {
for_each (coll.begin() , coll.end(), mem_fun(&Person::print));
for_each (coll.begin() , coll.end(), bind2nd(mem_fun(&Person::printWithPrefix), "person: "));
}

例4
bool check(int elem);
pos = find_if (coll.begin(), coll.end(), not1(ptr_fun(check)));
pos = find_if (coll.begin(), coll.end(), bind2nd(ptr_fun(strcmp),""));
transform(first, last, first, compose1(negate<double>, ptr_fun(fabs)));

例5
list<int> L;
list<int>::iterator in_range = find_if(L.begin(), L.end(),
   not1(compose2(logical_and<bool>(), bind2nd(greater_equal<int>(), 1), bind2nd(less_equal<int>(), 10))));

例6
char str[MAXLEN];
const char* wptr = find_if(str, str + MAXLEN,    compose2(not2(logical_or<bool>()), bind2nd(equal_to<char>(), ' '), bind2nd(equal_to<char>(), '\n')));

= Iterator迭代子 =
迭代子是一种能够遍历容器里面的全部或者部分元素的对象，一个迭代子能够表示容器里面一个特定的位置。

使用begin(), end()获得容器的迭代子。迭代子的类型会随着容器的不同而不同，可表示为container<T>::iterator,如果支持双向跌代，则可以通过rbegin(), rend()获得反向跌代子。反向跌代子的类型为：container<T>::reverse_iterator, 

== 分类 ==
 * Input：只能单向读取，比如istream
 * Output：只能单向写入，比如ostream
 * Forward：单向读取和写入，具有Input和Output跌代子的全部能力，比如slist
 * Bidirectional：双向读取和写入，具有Forward跌代子的全部能力，比如list, set, map
 * Random：随机读取和写入，具有Bidirectional跌代子的全部能力，比如vector, deque
== 运算符 ==
迭代子最基本的操作有：
 * iter++, ++iter：让跌代子移动到下一个元素，有前置后置两种形式。
 * *iter：返回迭代子当前位置上的元素。如果是Input代子，返回元素的值，只能读取；如果是Output跌代子，返回引用，只能写入。
 * iter1 == iter2 , iter1 != iter2：判断两个跌代子是否指向同一个位置。（Output没有此操作）
 * iter1 = iter2：改变跌代子指向的位置。（Output没有此操作）
 * iter ->：如果元素是类（结构体），则可以使用->直接访问元素的成员。
 * iter --, --iter：使用--移动到前一个元素，有前置后置两种形式。（双向跌代子和随机跌代子）
 * iter [n]：后面第n个的元素（Random跌代子）
 * iter += n：往后面移动n个位置（Random跌代子）
 * iter -= n：往前面移动n个位置（Random跌代子）
 * iter + n, n + iter：后面第n个位置（Random跌代子）
 * iter - n：前面第n个位置（Random跌代子）
 * iter1 - iter2: 两个元素之间的距离（Random跌代子）
 * iter1<iter2, iter1 > iter2, iter1 <= iter2, iter1 >= iter2: 比较两个跌代子的位置（Random跌代子）
== 辅助函数 ==
 * advance(iter, n)：将跌代子后移n个位置
 * distance(iter1, iter2)：两个跌代子之间的距离
== 迭代子适配器 ==
 * reverse iterator
 * insert iterators(back_inserter, front_inserter, inserter)
 * Stream Iterators(ostream_iterator, istream_iterator)
== Sample ==
例1
{{{#!cplusplus
//OK for forward iterators
//IMPOSSIBLE for output iterators
while (pos != coll.end()) {
  *pos = foo();
  ++pos;
}
}}}
例2
{{{#!cplusplus
int main() {
  vector<int> coll;
  for (int i=-3; i<=9; ++i) {
    coll.push_back (i);
  }
  cout << "number/distance: " << coll.end()-coll.begin() << endl;
  vector<int>::iterator pos;
  for (pos=coll.begin(); pos<coll.end(); ++pos) {
    cout << *pos << ' ';
  }
  for (int i=0; i<coll.size(); ++i) {
    cout << coll.begin() [i] << ' ';
  }
  for (pos = coll.begin(); pos < coll.end()-1; pos += 2) {
    cout << *pos << ' ';
  }
}
}}}
例3
{{{#!cplusplus
int main() {
  list<int> coll;
  //insert elements from 1 to 9
  for (int i=1; i<=9; ++i) {
    coll.push_back(i);
  }
  list<int>::iterator pos = coll.begin();
  cout << *pos << endl;
  advance (pos, 3);
  cout << *pos << endl;
  advance (pos, -1);
  cout << *pos << endl;
}
}}}
例4
{{{#!cplusplus
int main(){
  list<int> coll;
  for (int i=-3; i<=9; ++i) {
    coll.push_back(i);
  }
  list<int>::iterator pos;
  pos = find (coll.begin(), coll.end(), 5);
  if (pos != coll.end()) {
    cout << distance(coll.begin(),pos) << endl;
  }
  else {
    cout << "5 not found" << endl;
  }
}
}}}
例5
{{{#!cplusplus
void print (int elem) {
  cout << elem << ' ';
}
int main() {
  list<int> coll;
  for (int i=1; i<=9; ++i) {
    coll.push_back(i);
  }
  for_each (coll.begin(), coll.end(), print);
  for_each (coll.rbegin(), coll.rend(), print);
}
}}}
例6
{{{#!cplusplus
int main() {
  vector<int> coll;
  for (int i=1; i<=9; ++i) {
    coll.push_back(i);
  }
  vector<int>::iterator pos;
  pos = find (coll.begin(), coll.end(), 5);
  cout << "pos: " << *pos << endl;
  vector<int>::reverse_iterator rpos(pos);
  cout << "rpos: " << *rpos <<endl;
}
}}}
例7
{{{#!cplusplus
void print (int elem) {
  cout << elem << ' ';
}
int main() {
  deque<int> coll;
  for (int i=1; i<=9; ++i) {
    coll.push_back(i);
  }
  deque<int>::iterator pos1;
  pos1 = find (coll.begin(), coll.end(), 2); 
  deque<int>::iterator pos2;
  pos2 = find (coll.begin(), coll.end(), 7); 
  for_each (pos1, pos2, print); 
  deque<int>::reverse_iterator rpos1(pos1);
  deque<int>::reverse_iterator rpos2(pos2);
  for.each (rpos2, rpos1, print);
}
}}}
例8
{{{#!cplusplus
int main(){
  list<int> coll;
  for (int i=1; i<=9; ++i) {
    coll.push_back(i);
  }
  list<int>::iterator pos;
  pos = find (coll.begin(), coll.end(),5); 
  cout << "pos: " << *pos << endl;
  list<int>::reverse_iterator rpos(pos);
  cout << "rpos: " << *rpos << endl;
  list<int>::iterator rrpos;
  rrpos = rpos.base();
  cout << "rrpos: " << *rrpos << endl;
}
}}}
例9
{{{#!cplusplus
int main() {
  vector<int> coll;
  back_insert_iterator<vector<int> > iter(coll);
  *iter = 1;
  iter++;
  *iter = 2;
  iter++;
  *iter = 3;
  copy( col1.begin(), col1.end(), ostream_iterator<int>(cout, “  “));
  back_inserter(coll) = 44;
  back_inserter(coll) = 55;
  copy( col1.begin(), col1.end(), ostream_iterator<int>(cout, “  “));
  copy (coll .begin(), coll.end(), back_inserter(coll));
  copy( col1.begin(), col1.end(), ostream_iterator<int>(cout, “  “));
}
}}}
例10
{{{#!cplusplus
int main() {
  list<int> coll;
  front_insert_iterator<list<int> > iter(coll);
  *iter = 1;
  iter++;
  *iter = 2;
  iter++;
  *iter = 3;
  copy( col1.begin(), col1.end(), ostream_iterator<int>(cout, “  “));
  front_inserter(coll) = 44;
  front_inserter(coll) = 55;
  copy( col1.begin(), col1.end(), ostream_iterator<int>(cout, “  “));
  copy (coll.begin(), coll.end(), front_inserter(coll)); 
  copy( col1.begin(), col1.end(), ostream_iterator<int>(cout, “  “));
}
}}}
例11
{{{#!cplusplus
int main() {
  ostream_iterator<int> intWriter(cout,"\n");
  *intWriter = 42;
  intWriter++;
  *intWriter = 77;
  intWriter++;
  *intWriter = -5;
  vector<int> coll;
  for (int i=1; i<=9; ++i) {
    coll.push_back(i);
  }
  copy (coll.begin(), coll.end(), ostream_iterator<int>(cout));
  copy (coll.gin(), coll.end(), ostream_iterator<int>(cout," < "));
}
}}}
例12
{{{#!cplusplus
int main(){
  istream_iterator<int> intReader(cin);
  istream_iterator<int> intReaderEOF;
  while (intReader != intReaderEOF) {
    cout << "once: " << *intReader << endl;
    cout << "once again: " << *intReader << endl;
    ++intReader;
  }
}
}}}
例13
{{{#!cplusplus
int main() {
  istream_iterator<string> cinPos(cin);
  ostream_iterator<string> coutPos(cout," ");
  while (cinPos != istream_iterator<string>()) {
    advance (cinPos, 2);
    if (cinPos != istream_iterator<string>()) {
      *coutPos++ = *cinPos++;
    }
  }
  cout << endl;
}
}}}
例14
{{{#!cplusplus
int main() {
  vector<Date> e;
  copy( istream_iterator<Date>(cin), istream_iterator<Date>(), back_inserter(e));
  vector<Date>::iterator first = find(e.begin(), e.end(), "01/01/95");
  vector<Date>::iterator last = find(e.begin(), e.end(), "12/31/95");
  *last = "12/30/95";
  copy(first, last, ostream_iterator<Date>(cout, "\n"));
  e.insert(--e.end(), TodaysDate());
  copy( first, last, ostream_iterator<Date>(cout, "\n") );
}
}}}
注：早先获得的跌代子在特定的操作后会失效！！vector的迭代子在插入、删除以及重新分配内存后可能会失效。


= 练习 =
 1. Write a program to print a histogram of the frequencies of different characters in its input.
 1. Write a program to print a histogram of the lengths of words in its input. It is easy to draw the histogram with the bars horizontal; a vertical orientation is more challenging.
 1. Write a program that prints the distinct words in its input sorted into decreasing order of frequency of occurrence. Precede each word by its count.
 1. Write a cross-referencer that prints a list of all words in a document, and for each word, a list of the line numbers on which it occurs.
 1. Write the program tail, which prints the last n lines of its input. By default, n is set to 10, let us say, but it can be changed by an optional argument so that{{{
tail -n
}}}prints the last n lines. The program should behave rationally no matter how unreasonable the input or the value of n. Write the program so it makes the best use of available storage.
 1. Write a program to remove all comments from a C program. Don't forget to handle quoted strings and character constants properly. C comments don't nest.
 1. Write a program to check a C program for rudimentary syntax errors like unmatched parentheses, brackets and braces. Don't forget about quotes, both single and double, escape sequences, and comments. (This program is hard if you do it in full generality.)
 1. Write a program to implement a queue using two stacks.

"C++标准模板库"版本比较