版本57和75间的区别 (跳过第18版)

STL概述

["STL概述"]

如何使用STL文档

["如何使用STL文档"]

容器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）

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

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 vector<int> V;
   2 V.insert(V.begin(), 3);
   3 assert(V.size() == 1 && V.capacity() >= 1 && V[0] == 3);

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栈

   1 #include <stack>
   2 namespace std {
   3    template <class T, class Container = deque<T> >
   4    class stack;
   5 }

主要操作

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队列

   1 #include <queue>
   2 namespace std {
   3    template <class T, class Container = deque<T> >
   4    class queue;
   5 }
   6 
   7 主要操作：
   8  * push
   9  * pop
  10  * back
  11  * front
  12 
  13 例
  14 {{{#!cplusplus
  15 int main() {
  16    queue<string> q;
  17    q.push("These ");
  18    q.push("are ");
  19    q.push("more than ");
  20    cout << q.front();
  21    q.pop();
  22    cout << q.front();
  23    q.pop();
  24    q.push(''four ");
  25    q.push("words!");
  26    q.pop();
  27    cout << q.front();
  28    q.pop();
  29    cout << q.front() << endl;
  30    q.pop();
  31    cout << "number of elements in the queue: " << q.size() << endl;
  32 }

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

1. 概述

算法是一组对容器内的数据进行处理的函数

#include <algorithm>  //一般算法
#include <numeric>  //数值算法

算法的数量很多，大致可以分为：

非变动性算法，一般不会改变容器里面的数据，比如：

 for_each 对每一个元素执行某操作
 count 返回元素个数
 count_if 返回满足某一条件的元素个数
 min_element 返回最小的元素的迭代子
 max_element 返回最大的元素的迭代子
 find 搜索等于某值元素
 find_if 搜索满足某个条件的元素
 search_n 搜索连续n个元素，每个元素都等于某值或者满足某种条件
 search 搜索子区间，该子区间内的每个元素和另一个区间内的元素值相等或者满足一定的关系
 find_end 搜索最后出现的一个子区间，该子区间内的每个元素和另一个区间内的元素值相等或者满足一定的关系
 find_first_of 搜索某些元素第一次出现的位置
 adjacent_find 所艘连着两个相等的元素，或者连着两个元素满足某种关系
 equal 判断两个区间内的元素是否相等或者满足一定关系
 mismatch 搜索两个区间内第一个不同的元素
 lexicographical_compare 检验第一区间内的元素是否小于第二个区间内的元素

变动性算法，比如：

 for_each 对每个元素执行某个操作
 copy 复制
 copy_backward 复制（从后向前）
 transform 对一个区间每一个元素做某个操作，结果传给另一区间。对两个区间内的元素作某个操作，结果传给第三个区间。
 swap_ranges 交换两个区间内的元素
 fill 某一区间内填充某个值
 fill_n 某一位置开始填充n个某个值
 generate 用一个产生值填充某个区间
 generate_n 用一个产生值填充某一位置开始的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 对区间内最小的n个元素进行排序
partition 对元素进行分段
stable_partition 对元素进行分段（稳定的）
make_heap 建堆
push_heap 入堆
pop_heap 出堆
sort_heap 堆排序

已序区间算法

binary_search 二分查找
includes 判断一个区间是不是另一个区间的子集
lower_bound 找大于等于某个值的第一个元素
upper_bound 找大于某个值的第一个元素
equal_range 返回等于某个值的区间
merge 合并两个区间，结果存到另一个区间
inplace_merge 将一个区间的元素合并到另一个区间
set_union 两个集合并
set_intersection 两个集合交
set_difference 两个集合差
set_symmetric_difference 两个集合对称差

数值算法

accumulate 一个区间内的元素累加
inner_product 两个区间的元素求内积
adjacent_difference 计算区间内每两个相邻元素的差
partial_sum 求区间内的每个元素的部分和

2. for_each

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

实现：

   1 template <class InputIterator, class UnaryFunction>
   2 UnaryFunction for_each(InputIterator first, InputIterator last, UnaryFunction f) {
   3   while( first != end) {
   4     f(*first);
   5     ++first;
   6   }
   7   return f;
   8 }

用例1：

   1 void print ( int elem) {
   2    cout << elem << '\t';
   3 }
   4 int main() {
   5   vector< int > col( 5, 10); 
   6   for_each( col.begin(), col.end(), print);
   7   cout << endl;
   8 }

用例2：

   1 void add10(int &elem) { 
   2    elem+=10; 
   3 }
   4 void print ( int elem) {
   5    cout << elem << '\t';
   6 }
   7 int main() {
   8   vector<int> col(5, 10);
   9   for_each(col.begin(), col.end(), add10);
  10   for_each(col.begin(), col.end(), print);
  11 }

   1 class AddValue{
   2 private:
   3   int value;
   4 public:
   5   AddValue( const int&v) : value(v) {}
   6   void operator()(int&elem) const { elem+=value; }
   7 };
   8 void print ( int elem) {
   9    cout << elem << '\t';
  10 }
  11 int main() {
  12   vector<int > col(5, 10);
  13   int n;
  14   cin >> n;
  15   for_each(col.begin(), col.end(), AddValue(n));
  16   for_each(col.begin(), col.end(), print);
  17 }

   1 template<class T>
   2 class AddValue{
   3 private:
   4   T value;
   5 public:
   6   AddValue( const T&v) : value(v) {}
   7   void operator()(T&elem) const { elem+=value; }
   8 };
   9 template<class T>
  10 void print ( T elem) {
  11    cout << elem << '\t';
  12 }
  13 int main() {
  14   vector<int > col(5, 10);
  15   vector<float> col2(5, 5.5);
  16   vector<string> col3(5, "hello ");
  17   int n;
  18   float m;
  19   string s;
  20   cin >> n >> m >> s;
  21   for_each(col.begin(), col.end(), AddValue<int>(n));
  22   for_each(col2.begin(), col2.end(), AddValue<float>(m));
  23   for_each(col3.begin(), col3.end(), AddValue<string>(s));
  24   for_each(col.begin(), col.end(), print<int>);
  25   for_each(col2.begin(), col2.end(), print<float>);
  26   for_each(col3.begin(), col3.end(), print<string>);
  27 }

用例3：

   1 class MeanValue {
   2 private:
   3    int num, sum;
   4 public:
   5    MeanValue() : num(0), sum(0) {}
   6    void operator()( int elem ) { num ++; sum+=elem; }
   7    double value() { return static_cast<double>(sum) / static_cast<double>(num); }
   8 };
   9 int main() {
  10    vector<int> col(5, 10);
  11    MeanValue  mv = for_each(col.begin(), col.end(), MeanValue() );
  12    cout << mv.value();
  13 }

3. transform

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

   1 template <class InputIterator, class OutputIterator, class UnaryFunction>
   2 OutputIterator transform(InputIterator first, InputIterator last, OutputIterator result, UnaryFunction op) {
   3   while( first != last ) {
   4     *result = op(*first);
   5     ++result;
   6     ++first;
   7   }
   8   return result;
   9 }

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

   1 template <class InputIterator1, class InputIterator2, class OutputIterator, class BinaryFunction>
   2 OutputIterator transform(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, OutputIterator result, BinaryFunction binary_op) {
   3   while( first1 != last1 ) {
   4     *result = binary_op(*first1, *first2);
   5     ++result;
   6     ++first1;
   7     ++first2;
   8   }
   9   return result;
  10 }

用例1：

   1 template<class T>
   2 class AddValue{
   3 private:
   4   T value;
   5 public:
   6   AddValue( const T&v) : value(v) {}
   7   T operator()(const T&elem) const { return elem+value; }
   8 };
   9 template<class T>
  10 class Add{
  11 public:
  12   T operator()(const T& a, const T& b) const { return a + b; }
  13 };
  14 int main() {
  15   vector< int > c1(5, 10);
  16   transform( c1.begin(), c1.end(), c1.begin(), AddValue<int>(10) );
  17   vector< int > c2(5, 5);
  18   vector< int > c3(5);
  19   transform( c1.begin(), c1.end(), c2.begin(), c3.begin(), Add<int>());
  20 }

仿函数(Functor, Function Object)

1. 概述

能像函数一样使用的对象。普通函数、函数指针、定义了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

-  ⇤ ← 于2006-03-01 16:43:32修订的的版本57 → 
  大小: 39898
  编辑: czk
  备注:
+   ← 于2006-03-14 17:02:00修订的的版本75 → ⇥
  大小: 35335
  编辑: czk
  备注:
-删除的内容标记成这样。
+加入的内容标记成这样。
 行号 3:
-标准模板库(Standard Template Library)，简称STL，是关于容器类(container)、算法(algorithm)和迭代子(iterator)的C++库。它提供了计算机科学所需的基本的算法和数据结构。STL是一个通用的库，意思是它的组件大量都是参数化的：STL中几乎每一个组件都是模板。在使用STL前，你应该了解C++的模板是如何用的。

== 容器和算法 ==
跟许多其他类库一样，STL也包含容器类：这些类的目的是用来容纳其他对象。STL的容器类包括vector，list，deque，set，multiset，map，multimap，hash_set，hash_multiset，hash_map，hash_meultimap。每一个这样的类都是一个模板，模板可以被实例化成容纳特定类型的容器。比如说，你可以与使用C语言数组非常相似的方式使用vector<int>，另外vector还消除了手动管理内存分配的繁琐。
{{{#!cplusplus
      vector<int> v(3);            // Declare a vector of 3 elements.
      v[0] = 7;
      v[1] = v[0] + 3;
      v[2] = v[0] + v[1];          // v[0] == 7, v[1] == 10, v[2] == 17  
}}}

STL里面还包含了大量的算法，用来对容器里面的数据进行操作。比如说，只要使用reverse算法，你就可以将一个vector里面的元素顺序反过来：
{{{#!cplusplus
      reverse(v.begin(), v.end()); // v[0] == 17, v[1] == 10, v[2] == 7
}}}

在调用reverse的时候有两点需要注意。第一，reverse是一全局函数，不是成员函数。第二，它需要两个参数而不是一个：它对一个区间内的元素进行操作，而不是一个容器。在这个特例里面，这个区间恰好是整个容器v。

造成这两点的原因是相同的：reverse，其它STL算法也一样，是与STL容器相分离的。也就是说，reverse不仅可以用于反转vector的数据元素，也可以用来反转list的数据元素，甚至是C语言数组的元素。比如下面的程序也是合法的：
{{{#!cplusplus
      double A[6] = { 1.2, 1.3, 1.4, 1.5, 1.6, 1.7 };
      reverse(A, A + 6);
      for (int i = 0; i < 6; ++i)
        cout << "A[" << i << "] = " << A[i];
}}}

和前面的反转vector例子类似，这个例子也使用了一个区间：reverse的第一个参数是指向区间开始的指针，第二个参数是指向区间结束的指针。这个区间记为[A, A+6)；这个不对称的标记表明区间的两端时不一样的，第一个是区间开始的位置，第二个是区间最后元素的下一个位置。

== 迭代子 ==

在反转C数组元素的例子中，reverse的参数很清楚，是double*类型的。但是在反转vector的时候，reverse参数的类型是什么呢？反转list呢？也就是说，reverse的参数到底声明成什么?v.begin()和v.end()到底返回什么？

答案就是，传给reverse的参数是迭代子，它是一种泛化的指针。指针本身也是迭代子，这就是为什么reverse可以反转C语言数组的元素。类似的，在vector中声明了内嵌的类型iterator和const_iterator。在前面的例子中，v.begin()和v.end()返回的类型就是vector<int>::iterator。而还有一些迭代子，比如istream_iterator和ostream_iterator，他们根本不和容器关联。

有了迭代子这种机制，使得让算法和容器分离成了可能：算法是模板，用迭代子作为参数，因此他并不局限于一种容器。比如说，要写一个算法在一个区间内进行线性的查找。这实际上就是一个STL的find算法。

{{{#!cplusplus
      template <class InputIterator, class T>
      InputIterator find(InputIterator first, InputIterator last, const T& value) {
          while (first != last && *first != value) ++first;
          return first;
      }
}}}
find算法有三个参数：两个迭代子定义了查找的区间，一个值指定了在这个区间内需要搜索的值。

Find takes three arguments: two iterators that define a range, and a value to search for in that range. It examines each iterator in the range [first, last), proceeding from the beginning to the end, and stops either when it finds an iterator that points to value or when it reaches the end of the range.

First and last are declared to be of type InputIterator, and InputIterator is a template parameter. That is, there isn't actually any type called InputIterator: when you call find, the compiler substitutes the actual type of the arguments for the formal type parameters InputIterator and T. If the first two arguments to find are of type int* and the third is of type int, then it is as if you had called the following function.
{{{#!cplusplus
      int* find(int* first, int* last, const int& value) {
          while (first != last && *first != value) ++first;
          return first;
      }
}}}
+["STL概述"]

= 如何使用STL文档 =

["如何使用STL文档"]
-行号 86:
+行号 38:
+{{{#!cplusplus
vector<int> V;
V.insert(V.begin(), 3);
assert(V.size() == 1 && V.capacity() >= 1 && V[0] == 3);
}}}
-行号 860:
+行号 818:
+}}}
-行号 861:
+行号 820:
-bind1st
+{{{bind1st
-行号 1197:
+行号 1156:
+ * [http://www.stlchina.org/twiki/bin/view.pl/Main/STLChina]

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

STL概述

如何使用STL文档

容器container

1. vector向量

1.1. 接口说明

1.1.1. 构造方法

1.1.2. 不变操作和赋值

1.1.3. 元素访问

1.1.4. 跌代子

1.1.5. 插入删除操作

1.2. 用法实例

1.3. vector的实现

2. deque双端队列

3. list链表

4. stack栈

5. queue队列

6. priority_queue优先队列

7. set与multi_set

8. map与multi_map

算法Algorithm

1. 概述

2. for_each

3. transform

仿函数(Functor, Function Object)

1. 概述