版本2和6间的区别 (跳过第4版)

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

跌代子是用来访问容器内元素的对象，类似指针。跌代子根据能力的不同，分为：

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

另外还有

跌代子适配器：将原来不是迭代子的东西变成迭代子，或者将一种迭代子变成另一种迭代子（比如back_inserter, front_inserter, inserter, 反向迭代子，ostream_iterator, istream_iterator）

3. 算法algorithm

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

4. 仿函数functor

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

vector向量

1. 接口说明

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

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

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

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.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.3. 元素访问

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

1.4. 跌代子

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

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

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] );

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 size_t size_type;
   7 protected:
   8     iterator start;
   9     iterator finish;
  10     iterator end_of_storage;
  11     //...
  12 public:
  13     iterator begin() { return start; }
  14     iterator end() { return finish; }
  15     size_type reserver(size_type n); //改变容量的大小
  16     size_type capacity() const { return size_type(end() - begin()); } //返回当前容量的大小
  17 };

-  ⇤ ← 于2006-02-22 00:10:50修订的的版本2 → 
  大小: 4196
  编辑: czk
  备注:
+   ← 于2006-02-22 00:41:27修订的的版本6 → ⇥
  大小: 5860
  编辑: czk
  备注:
-删除的内容标记成这样。
+加入的内容标记成这样。
 行号 7:
-行号 9:
+行号 10:
-除此以外还有： 
 * 特殊的容器：string（字符串）, array（C语言原始数组） 
 * 容器适配器：stack（栈）, queue（队列）, priority_queue（优先队列）
+除此以外还有：

 * 特殊的容器：string（字符串）, array（C语言原始数组）
 * 容器适配器：stack（栈）, queue（队列）, priority_queue（优先队列）
-行号 13:
+行号 16:
-行号 17:
+行号 21:
-行号 21:
+行号 26:
  * 输出跌代子
-行号 23:
+行号 29:
-行号 34:
+行号 41:
-{{{#!cplusplus
+{{{
#!cplusplus
-行号 40:
+行号 49:
-行号 41:
+行号 51:
-行号 42:
+行号 53:
-{{{#!cplusplus
+{{{
#!cplusplus
-行号 45:
+行号 57:
-vector < int > a4(a2); //构造一个vector与a2完全一样
+vector< int > a4(a2); //构造一个vector与a2完全一样
-行号 48:
+行号 60:
-vector < int > a5( values, values+5); //通过迭代子来构造vector
+vector< int > a5( values, values+5); //通过迭代子来构造vector
-行号 52:
+行号 64:
-{{{#!cplusplus
+{{{
#!cplusplus
-行号 60:
+行号 73:
-行号 61:
+行号 75:
-{{{#!cplusplus
+{{{
#!cplusplus
-行号 67:
+行号 82:
-行号 68:
+行号 84:
-{{{#!cplusplus
+{{{
#!cplusplus
-行号 74:
+行号 91:
-行号 75:
+行号 93:
-{{{#!cplusplus
+{{{
#!cplusplus
-行号 87:
+行号 106:
+== 用法实例 ==
{{{
#!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 size_t size_type;
protected:
    iterator start;
    iterator finish;
    iterator end_of_storage;
    //...
public:
    iterator begin() { return start; }
    iterator end() { return finish; }
    size_type reserver(size_type n); //改变容量的大小
    size_type capacity() const { return size_type(end() - begin()); } //返回当前容量的大小
};
}}}

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