几种模板

首先认识一下函数模板、类模板、栈模板。

函数模板

函数模板就是一个模型，而模板函数是函数模板经过类型实例化的函数。

如下template<class T>是一个简单的函数模板：

template<class T>
T Max(T a, T b)
{
    return a > b ? a : b;
}
int main()
{
    cout << Max(2, 5) << endl;//与Max匹配的函数叫模板函数
    cout << Max('t', 'a') << endl;//使用模板不受限于它的类型
}

也可以一次定义几个不同类型

template<class T1, class T2>
void fn(T1 a, T2 b)
{
    cout << a << " " << b << endl;
}
void main()
{
    fn('a', 5);
}

类模板

类模板不是类，需要经过参数实例化之后才是可以用的类（创建对象的时候告诉类模板<类型>）

template<class T>
class A
{
public:
    A(int i=0):m_i(i){}
    void print() { cout << m_i << endl; }
private:
    T m_i
};
int main()
{
    //A a;//err
    A<int> a(10);//这样经过参数实例化之后才是可以用的类
    a.print();
}

使用栈模板

自己模拟栈要很长一段代码：

#define SIZE 10
template<class T>
class SeqStack
{
public:
    SeqStack()
    {
        m_capacity = SIZE;
        m_data = new T[m_capacity];
        m_top = -1;
    }
    ~SeqStack()
    {
        delete[]m_data;
        m_data = nullptr;
    }
    void Push(int v)
    {
        if (IsFull())return;
        m_data[++m_top] = v;
    }
    void Pop()
    {
        if (IsEmpty())
        {
            return;
        }
        m_top--;
    }
    bool IsEmpty()
    {
        return m_top == -1;
    }
    bool IsFull()
    {
        return m_top >= m_capacity - 1;
    }
    int GetTop()  //要优化
    {
        if (IsEmpty())
            return 0;
        return m_data[m_top];
    }
private:
    T* m_data;
    int m_top;
    int m_capacity;
};
int main()
{
    SeqStack<int> ss;
    ss.Push(1);
    ss.Push(2);
    ss.Push(3);
    while (!ss.IsEmpty())
    {
        cout << ss.GetTop() << " ";
        ss.Pop();
    }
}

栈模板就可以直接用，带上头文件#include<stack>，很方便，效果跟自己模拟是一样的

int main()
{
    stack<int> ss;
    ss.push(1);
    ss.push(2);
    ss.push(3);
    while (!ss.empty())
    {
        cout << ss.top() << endl;
        ss.pop();
    }
}

---

STL 标准模板库

STL的重要的组件：容器、算法、迭代器

容器：存放数据

算法：操作数据

迭代器：容器和算法之间的粘合器——通过迭代器把容器里的东西取出，给算法操作（指针）

STL是泛型程序库：所有组件可以针对任意型别运作。

使用

例：从标准输入读取一段整数，将这些整数存放在一个动态开辟的数组中，数组的

第一个元素存储整数的个数，以后依次是这些整数。

void main()
{
    vector<int> vv;
    copy(istream_iterator<int>(cin), istream_iterator<int>(),
        back_insert_iterator<vector<int>>(vv));
    copy(vv.begin(), vv.end(), ostream_iterator<int>(cout, " "));
}

容器

•容器：用来管理某类对象的集合。容纳特定数据类型对象的集合,STL容器是将最常用的一些数据结构实现出来.包含了许多数据结构,如:vector,queue,statck…,string也可以看作是一个容器.

•分类:容器用来管理一组元素，为了适应不同需要，STL根据数据在容器中排列的特性,容器可分为序列式容器和关联式容器两种.

•序列式容器:可序群集，其中每个元素都有固定位置——取决于插入时机和地点,与元素的值没有关系,如果你以追加方式对一个群集置入n个元素，它们的排列次序将和置入次序一致。如vector,deque,list

•关联式容器:已序群集，元素位置取决于特定的排序准则,和插入顺序无关。如果你将n个元素置入这样的群集中，它们的位置取决于元素值，和插入次序无关。STL提供了4个这样的容器：set,map，。multiset，multimap。

关联式容器也可被视为特殊的序列式容器，因为已序群集正是根据某个排序准则排列而成。

vector容器

向量（Vector）是一个封装了动态大小数组的顺序容器（Sequence Container）。跟任意其它类型容器一样，它能够存放各种类型的对象。可以简单的认为，向量是一个能够存放任意类型的动态数组。

vector:将其元素置于一个动态数组中加以管理，是一种动态数组，是基本数组的类模板，用于代替数组，支持随机存取。

int main()
{
    vector<int> v;
    //v里面的构造方法
    vector<int> v1(5);//5个0
    vector<int> v2(4, 7);//4个7
    int arr[5] = { 1,2,3,4,5 };
    vector<int> v3(arr,arr+5);//1，2，3，4，5
    for (int i = 0; i < v2.size(); i++)
        cout << v2[i] << " ";
    cout << endl;
    v.push_back(1);
    v.push_back(2);
    v.push_back(40);
    v.push_back(3);
    for (int i = 0; i < v.size(); i++)
        cout << v[i] << " ";
    cout << endl;
}

普通二维数组必须定义列数，如a[][3]，但vector的每行列数可以不一样

void main()
{
    vector<int> v;
    vector<vector<int>> vv;//vv相当于一个二维数组
    v.push_back(1);//1
    vv.push_back(v);//1
    v.push_back(2);//1 2
    vv.push_back(v);
//1    
//1 2
    v.push_back(3);//1 2 3
    vv.push_back(v);
//1
//1 2    
//1 2 3
    for (int i = 0; i < vv.size(); i++)
    {
        for (int j = 0; j < vv[i].size(); j++)
            cout << vv[i][j] << " ";
        cout << endl;
    }
}

vector定义后不能直接赋值，必须有东西存进去再修改

void main()
{
    vector<int> v;
    //v.resize(5);
    v[0] = 5;
//这相当于下面这两行，是不行的
    //int a;
    //a[0] = 6;
}

---

算法

•算法：用来处理群集内的元素。它们可以出于不同的目的而搜寻，排序，修改，使用那些元素。是一种应用在容器上以各种方法处理其内存的行为或功能,如sort(排序),copy(拷贝)…,算法由模板函数体现,这些函数不是容器类的成员函数，是独立的函数,它们可以用于STL容器,也可以用于普通的C++数组等.

•头文件：#include<algorithm>在STL的泛型算法中有4类基本的算法：

•1)变序型队列算法: 可以改变容器内的数据；

•2)非变序型队列算法:处理容器内的数据而不改变他们；

•3)排序值算法:包涵对容器中的值进行排序和合并的算法，还有二叉搜 索算法 ,

•4)通用数值算法：此种算法不多，涉及到专业领域中有用的算术操作，独立包涵于头文件<numeric>中，在此不多做解释

排序sort()

使用必须加上头文件#include<algorithm>。

sort默认是做非递减排序，用的类模板，这个自己也可以模拟，如下：

自己也可以写个函数传入sort使其做非递增排序。

bool great(int a, int b)
{
    return a > b;
}
template<class T>
class Great
{
public:
    bool operator()(T a, T b)
    {
        return a > b;
    }
};
void main()
{
    int a[] = { 1,3,2,5,4,7,6,9,8,0 };
    int n = sizeof(a) / sizeof(a[0]);
    //sort(a, a + n,greater<int>());
    //sort(a, a + n, great);//函数模板，用函数名当做函数指针传入
    sort(a, a + n, Great<int>());//类模板，运用了（）的重载
    for (int i = 0; i < n; i++)
        cout << a[i] << " ";
    cout << endl;
}

遍历for_each()

for_each()函数是C++ STL中的一个遍历函数，函数原型如下：

for_each(InputIterator first, InputIterator last, Function functor);

拷贝copy()

复制 [first, last) 所定义的范围中的元素到始于 d_first 的另一范围。

函数原型：

template<class InputIterator, class OutputIterator>  
inline OutputIterator copy(  
      InputIterator first,   
      InputIterator last,   
      OutputIterator result  
);

for_each()和copy()的使用：

void print(int n)
{
    cout << n << " ";
}
int s = 0;
void Sum(int n)
{
    s = s + n;
}
void main()
{
    int a[5] = { 1,2,3,4,5 };
    int b[5];
    copy(a, a + 5, b);//把[a,a+n)复制到b
    //    copy(b, b + 5, ostream_iterator<int>(cout, ","));
    for_each(b, b + 5, print);//输出12345
    for_each(b, b + 5, Sum);//输出15
    cout << "s = " << s << endl;
}

反转函数reverse

将区间[iterator1,iterator2)内的元素反转

交换swap_ranges

函数原型：

template<typename T1, typename T2>
 void swap(std::pair<T1,T2> left, std::pair<T1,T2> right);

前两个参数分别是第一个序列的开始和结束迭代器，第三个参数是第二个序列的开始迭代器。显然，这两个序列的长度必须相同。这个算法会返回一个迭代器，它指向第二个序列的最后一个被交换元素的下一个位置。

使用：

bool great5(int n)
{
    return n > 5;
}
template<class T>
class Less5
{
public:
    bool operator()(T n)
    {
        return n < 5;
    }
};
void main()
{
    int a[] = { 1,2,3,4,5 };
    int b[] = { 6,7,8,9,0 };
    int n = sizeof(a) / sizeof(a[0]);
    int* p = find(a, a + n, 15);
    cout << *(p - 1) << endl;
    p = find_if(a, a + n, great5);
    cout << *p << endl;
    p = find_if(a, a + n, Less5<int>());
    cout << *p << endl;
    reverse(a, a + n);
    swap_ranges(a, a + 3, b);
    cout << count(a, a + 5, 2) << endl;
    cout << count_if(a, a + 5, Less5<int>()) << endl;
}

判断包含关系includes

函数原型

template <class InputIterator1, class InputIterator2, class Compare>
  bool includes ( InputIterator1 first1, InputIterator1 last1,
                  InputIterator2 first2, InputIterator2 last2, Compare comp );

测试 [first1,last1)里面是否包含了[first2,last2)里面的所有元素。

int main(void)
{
    int a[10] = { 12,0,5,3,6,8,9,34,32,18 };
    int b[5] = { 5,3,6,8,9 };
    int d[15];
    sort(a, a + 10);
    for (int i = 0; i < 10; i++)
        cout << " " << a[i];
    sort(b, b + 5);  // 3 5 6 8 9
    if (includes(a, a + 10, b, b + 5))  //一个数组是否包含另外一个数组
        cout << "\n" << "sorted b members are included in a." << endl;
    else
        cout << "sorted a dosn`t contain sorted b!";
    merge(a, a + 10, b, b + 5, d); //合并
    for (int j = 0; j < 15; j++)
        cout << "  " << d[j];
    return 0;
}

归并排序merge

merge只有归并部分，使用它必须是两个有序数组经行归并（先用sort()排序）

void main()
{
    int a[5] = { 5,4,1,2,3 };
    int b[5] = { 6,8,1,4,6 };
    int c[10];
    sort(a, a + 5);
    sort(b, b + 5);
    merge(a, a + 5, b, b + 5, c);
}