[数据结构与算法]C++ STL模板

一、STL介绍

STL（Standard Template Library），即标准模板库，是一个具有工业强度的，高效的C++程序库。它被容纳于C++标准程序库（C++ Standard Library）中，是ANSI/ISO C++标准中最新的也是极具革命性的一部分。该库包含了诸多在计算机科学领域里所常用的基本数据结构和基本算法。为广大C++程序员们提供了一个可扩展的应用框架，高度体现了软件的可复用性。

它的核心包括以下三个组件：

二、实验内容

1.序列变换（取反、平方、立方）

代码：

#include <vector>
#include <map>
#include <iostream>
#include <algorithm>
#include <functional>
#include <set>
using namespace std;
//取反
template<typename T>
T InvT(T a)
{
    return -a;
}
template<typename T>
//平方
T SqrT(T a)
{
    return a * a;
}
//立方
template<typename T>
T CubeT(T a)
{
    return a * a * a;
}
//自定义操作运算函数
template<typename inputIter, typename outputIter, typename MyOperator>
void transCalcT(inputIter begInput, inputIter endInput, outputIter begOutput, MyOperator op)
{
    for (; begInput != endInput; begInput++, begOutput++)
    {
        *begOutput = op(*begInput);
    }
}

template < typename T>
void outputCont(string strNme, ostream& os, T begin, T end)
{
    os << strNme + "的遍历结果为：[";
    for (; begin != end; begin++)
    {
        os << *begin << " ";
    }
    os << "]" << endl;
}

int main(int argc, char** argv) {
    const int N = 5;
    int a[N] = { 1,2,3,4,5 };
    int b[N];
    //设置一个容量为5的容器vb，数据类型为double
    vector<double> vb(N);
    transCalcT(a, a + N, vb.begin(), InvT<int>);
    outputCont("原数组", cout,a, a+N);
    outputCont("取反的结果", cout, vb.begin(), vb.end());
    transCalcT(a, a + N, vb.begin(), SqrT<int>);
    outputCont("平方的结果", cout, vb.begin(), vb.end());
    transCalcT(a, a + N, vb.begin(), CubeT<int>);
    outputCont("立方的结果", cout, vb.begin(), vb.end());
   
}

运行结果：

2.像素变换（二值化、灰度拉伸）

代码如下：

#include <vector>
#include <map>
#include <iostream>
#include <algorithm>
#include <functional>
#include <set>
using namespace std;
// 二值化
template<typename T>
class MyThreshold {
public:
    MyThreshold(int n = 128) :_nThreshold(n) {}
    int operator()(T val)
    {
        //在二值化过程中，对每一个像元进行二值化处理，若小于_nThreshold，则置为0，反之则置为1
        return val < _nThreshold ? 0 : 1;
    }
    int _nThreshold;
};

//灰度变换
template <typename T>
class Mytrans
{
public:
    Mytrans(int n = 128) :c(n) {}
    int operator()(T val)
    {
        //将每一个像元大小增加10
        return val += 10;
    }
    int c;
};
//自定义操作运算函数
template<typename inputIter, typename outputIter, typename MyOperator>
void transCalcT(inputIter begInput, inputIter endInput, outputIter begOutput, MyOperator op)
{
    for (; begInput != endInput; begInput++, begOutput++)
    {
        *begOutput = op(*begInput);
    }
}

template < typename T>
void outputCont(string strNme, ostream& os, T begin, T end)
{
    os << strNme + "的遍历结果为：[";
    for (; begin != end; begin++)
    {
        os << *begin << " ";
    }
    os << "]" << endl;
}

int main(int argc, char** argv) {
    const int N = 5;
    int a[N] = { 120,121,128,129,130 };
    int b[N];
    //设置一个容量为5的容器vb，数据类型为double
    vector<double> vb(N);
    transCalcT(a, a + N, vb.begin(), MyThreshold<int>());
    outputCont("二值化", cout, vb.begin(), vb.end());
    transCalcT(a, a + N, vb.begin(), Mytrans<int>());
    outputCont("灰度变换", cout, vb.begin(), vb.end()); 
}

运行结果：

3.SET的应用 实现学生信息的增删改查

代码如下：

    class studentInfo {
    public:
        //两个参数的构造函数
        studentInfo(string strNo, string strName) {
            _strNo = strNo;
            _strName = strName;
        }
        string _strNo;
        string _strName;
        //输出符重载
        friend ostream& operator<<(ostream& os, const studentInfo& info)
        {
            os << info._strNo << " " << info._strName;
            return os;
        }
        //比较学号大小
        friend bool operator<(const studentInfo& info1, const studentInfo& info2) {
            return info1._strNo < info2._strNo;
        }
    };
    void TestSet()
    {
        vector<studentInfo> students;
        //将一个学生对象插入动态数组中(增加元素)
        students.push_back(studentInfo("10021", "Zhang san"));
        students.push_back(studentInfo("10002", "Li si"));
        students.push_back(studentInfo("10003", "Wang wu"));
        students.push_back(studentInfo("10011", "Wang Liu"));
        students.push_back(studentInfo("10010", "Wu Liu"));
        set<studentInfo> studentSet(students.begin(), students.end());
        outputCont("student set", cout, studentSet.begin(), studentSet.end());
        //删除指定元素
        studentSet.erase(studentInfo("10010", "Wu Liu"));
        outputCont("student set(deleted)", cout, studentSet.begin(), studentSet.end());
        //查询指定学号的学生姓名
        const char* num = "10011";
        set<studentInfo>::iterator it;
        for (it = studentSet.begin(); it != studentSet.end(); it++)
        {
            if(((*it)._strNo).compare(num)==0)
                cout << (*it)._strName << " ";
        }
        //Set的迭代器iterator有const修饰，因此只能对它进行读取而不能进行修改
    }

运行结果：

4.map的应用 使用map统计字符串中每个字符出现的次数

代码如下：

    void TestMap()
    {
        //定于map类型
        map<char, int> word_count;
        const char* word = "hello world";
        for (int i = 0; i < strlen(word); i++)
        {
            ++word_count[word[i]];                     
        }
        map<char, int>::iterator iter;             
        for (iter = word_count.begin(); iter != word_count.end(); iter++)
        {
            cout << "[" << iter->first << "] = " << iter->second << endl;
        }
    }

运行结果：

总结

1.STL的一个重要特点是数据结构和算法的分离。尽管这是个简单的概念，但这种分离确实使得STL变得非常通用。例如，由于STL的sort()函数是完全通用的，你可以用它来操作几乎任何数据集合，包括链表，容器和数组；

2.STL另一个重要特性是它不是面向对象的。为了具有足够通用性，STL主要依赖于模板而不是封装，继承和虚函数（多态性）

3. 箭头表示概念与子概念的关系，例如前向迭代器这一概念是输入迭代器和输出迭代器这两个概念的子概念，也就是说一个前向迭代器肯定是输入迭代器，也肯定是输出迭代器。

输入迭代器：可以用来从序列中读取数据，如输入流迭代器

istream_iterator<T>
以输入流（如cin）为参数构造
可用*(p++)获得下一个输入的元素

输出迭代器：允许向序列中写入数据，如输出流迭代器

ostream_iterator<T>
构造时需要提供输出流（如cout）
可用(*p++) = x将x输出到输出流

前向迭代器：既是输入迭代器又是输出迭代器，并且可以对序列进行单向的遍历

双向迭代器：与前向迭代器相似，但是在两个方向上都可以对数据遍历

随机访问迭代器：也是双向迭代器，但能够在序列中的任意两个位置之间进行跳转，如指针、使用vector的begin()、end()函数得到的迭代器

4.算法部分主要由头文件，和组成。

<algorithm>是所有STL头文件中最大的一个（尽管它很好理解），它是由一大堆模版函数组成的，可以认为每个函数在很大程度上都是独立的，其中常用到的功能范围涉及到比较、交换、查找、遍历操作、复制、修改、移除、反转、排序、合并等等。
<numeric>体积很小，只包括几个在序列上面进行简单数学运算的模板函数，包括加法和乘法在序列上的一些操作。
<functional>中则定义了一些模板类，用以声明函数对象。

STL中算法大致分为四类：

非可变序列算法：指不直接修改其所操作的容器内容的算法。
可变序列算法：指可以修改它们所操作的容器内容的算法。
排序算法：对序列进行排序和合并的算法、搜索算法以及有序序列上的集合操作。
数值算法：对容器内容进行数值计算。