STL入门导论[原+译]

STL入门引导

涉及到的源码：http://download.csdn.net/detail/nuptboyzhb/4239649

STL主要有以下六个大的部分：

l 迭代器（iterators）

迭代器可以理解为一个模板指针；迭代器技术能够使程序反复的对STL容器的内容进行访问；

l 算法（alogrithms）

STL提供了很多的数据结构算法，这些算法在std命名空间中定义，通过#include<algorithm>来获得使用权。如常用的算法有：for_each()、find()、find_if()、count()、replace()、copy()、sort()、merge等

l 容器（containers）

常见的容器有：向量容器vector、双向链表容器list、双端队列容器deque、集合容器set、多重集合容器multiset、映射容器map、多重映射容器multimap

l 函数对象（function objects）

l 内存分配器（allocators）

l 适配器（adapter）

适配器是一种泛化的模板类型。STL提供的适配器主要分为迭代器适配器、函数对象适配器、容器适配器，分别用来进行迭代器、函数对象和容器的转换。

1. 命名空间

用标准的std命名空间，using namespace std;

2. 一些建议

1．在Debug模式下，忽略如下警告信息：#pragma warning(disable: 4786)

2．当定义如下容器时：

不要写成vector <list<int>> veclis;而要vector <list <int> > veclis;也即是在‘>’与‘>’之间，加一个空格；

3. copy算法的巧用

对于如下程序的输出；

#include <string>

#include <set>

#include <iostream>

using namespace std;

#pragma warning(disable: 4786)

int main(int argc, char* argv[])

{

       set <string> strset;

       set <string>::iterator si;

       strset.insert("cantaloupes");

       strset.insert("apple");

       strset.insert("orange");

       strset.insert("banana");

       strset.insert("grapes");

       strset.insert("grapes");  

       // This one overwrites the previous occurrence

       for (si=strset.begin(); si!=strset.end(); si++)  

       {  

              cout << *si << " "; 

       }

       cout << endl;

       return 0;

}

我们可以用如下语句，代替for循环的输出：

copy(strset.begin(), strset.end(), ostream_iterator<string>(cout, " "));

4. 如何对一些类应用Map容器

map是一个通过键(key)来获得值的。当你用你自己定义的类，而不是一些数据类型（如int），你必须保证自定义的类包含如下函数和操作；

1. 默认构造函数（通常是空）

2. 拷贝构造函数

3. 重载运算符’=’

以上三点，是必须的，当然，你也可以添加其他的函数和运算符；

举例：

#include <string>

#include <iostream>

#include <vector>

#include <map>

using namespace std;

 

class CStudent

{

public :

  int nStudentID;

  int nAge;

public :

  //定义一个空的构造函数

  CStudent()  {  }

  // Full constructor

  CStudent(int nSID, int nA)  {  nStudentID=nSID; nAge=nA;  }

  // 定义一个拷贝构造函数

  CStudent(const CStudent& ob)  

    {  nStudentID=ob.nStudentID; nAge=ob.nAge;  }

  // 重载运算符 =

  void operator = (const CStudent& ob)  

  {  nStudentID=ob.nStudentID; nAge=ob.nAge;  }

};

 

int main(int argc, char* argv[])

{

       map <string, CStudent> mapStudent;

       

       mapStudent["Joe Lennon"] = CStudent(103547, 22);

       mapStudent["Phil McCartney"] = CStudent(100723, 22);

       mapStudent["Raoul Starr"] = CStudent(107350, 24);

       mapStudent["Gordon Hamilton"] = CStudent(102330, 22);

       

       // Access via the name

       cout << "The Student number for Joe Lennon is " << 

              (mapStudent["Joe Lennon"].nStudentID) << endl;

       

       return 0;

}

5. typedef的应用

例如：

typedef set <int> SET_INT;

typedef SET_INT::iterator SET_INT_ITER

6. 迭代器的注意事项

iterator - For any container other than the vector, you can only step one at a time in a forward direction through the container. That is you can only use the ++ operator, not the -- or += operator on it. For vector only you can use any of +=, --, -=, ++, and all the comparison operators <, <=, >, >=, ==, !=.对于大多数的容器，只能应用如下操作符：++,<,<=,>,>=,==,!=;而对于vector向量容器，还可以使用+=, --, -=, ++运算符。

reverse_iterator - If you want to step backwards instead of forwards through a non-vector container, replace iterator with reverse_iterator,begin() with rbegin(), and end() withrend(), ++ will then traverse backwards.

const_iterator - a forward iterator that returns aconst value. Use this if you want to make it clear that this points to a read-only value.

const_reverse_iterator - a reverse iterator that returns aconst value.

7. 算法

算法时应用在模板中的函数。你可以很轻松的对模板容器中的元素进行排序、搜索、操作、交换。

容器本身并不传递给算法，而是容器的迭代器传递给算法。因此，算法所限制的数据类型是迭代器的数据类型。

举例：

#include <algorithm>  // If you want to use an 

   // algorithm this is the header used.

#include <numeric>  // (For Accumulate)

#include <vector>

#include <iostream>

using namespace std;

int testscore[] = {67, 56, 24, 78, 99, 87, 56};

// predicate that evaluates a passed test限定函数

bool passed_test(int n)

{

  return (n >= 60);

}

// predicate that evaluates a failed test

bool failed_test(int n)

{

  return (n < 60);

}

int main(int argc, char* argv[])

{

  int total;

  // 用数组初始化向量容器

  vector <int> vecTestScore(testscore, 

     testscore + sizeof(testscore) / sizeof(int));

  //生成迭代器vi

  vector <int>::iterator vi;

 

  // 整理和输出向量容器里的值

  sort(vecTestScore.begin(), vecTestScore.end());

  cout << "Sorted Test Scores:" << endl;

  for (vi=vecTestScore.begin(); vi != vecTestScore.end(); vi++)

  {  cout << *vi << ", ";  }

  cout << endl;

  // min_element 返回一个指向最小值的一个迭代器

  vi = min_element(vecTestScore.begin(), vecTestScore.end());

  cout << "The lowest score was " << *vi << "." << endl;

  // Same with max_element

  vi = max_element(vecTestScore.begin(), vecTestScore.end());

  cout << "The highest score was " << *vi << "." << endl;

  // Use a predicate function to determine the number who passed

  //用一个限定函数，来限定传入值的类型；这里限制的是分数

  cout << count_if(vecTestScore.begin(), vecTestScore.end(), passed_test) << 

         " out of " << vecTestScore.size() << 

         " students passed the test" << endl;

  // and who failed

  cout << count_if(vecTestScore.begin(), 

         vecTestScore.end(), failed_test) << 

         " out of " << vecTestScore.size() << 

         " students failed the test" << endl;

  // Sum the scores

  total = accumulate(vecTestScore.begin(), 

         vecTestScore.end(), 0);

  // Then display the Average

  cout << "Average score was " << 

         (total / (int)(vecTestScore.size())) << endl;

  return 0;

}

8. 模板的派生和嵌入

1. 作为类的成员变量；如：

 class CParam
{
  string name;
  string unit;
       vector <double> vecData;
};

2. 继承模板

      class CParam : public vector <double>
{

string name;

string unit;

};

9. 模板中的模板

为了创建一个更加复杂的数据结构，你可以在一个模板内创建一个模板。最好先用typedef关键字定义该模板。

举例：

#include <iostream>

#include <vector>

using namespace std;

typedef vector <int> VEC_INT;

int inp[2][2] = {{1, 1}, {2, 0}};  

  // Regular 2x2 array to place into the template

int main(int argc, char* argv[])

{

       int i, j;

       vector <VEC_INT> vecvec;

       // if you want to do this in all one step it looks like this

       // vector <vector <int> > vecvec;

       // Fill it in with the array

       VEC_INT v0(inp[0], inp[0]+2);  // passing two pointers 

    // for the range of values to be copied to the vector

       VEC_INT v1(inp[1], inp[1]+2);

       vecvec.push_back(v0);

       vecvec.push_back(v1);

       for (i=0; i<2; i++)

       {

              for (j=0; j<2; j++)

              {

                     cout << vecvec[i][j] << "  ";

              }

              cout << endl;

       }

       return 0;

}

// Output:

// 1 1

// 2 0