猫史档案馆

       我们在使用各式各样的基础数据类型的时候，往往会遇到这样的问题：

       想要一个能够自己扩展的数组，有个已经写好的算法模板……

       STL，即Standard Template Library（标准模板库），可以满足这些需求，它通过template定义了大量的可复用，泛型支持的数据结构，算法等，为广大开发者提供了众多高效编程工具。

       我们假定各位已经学会了OOP等前置基础知识，并已熟练掌握C++的语法。

       那么，现在开始吧！

第一节：走进泛型编程

        我们都学过一个模板函数或对象的定义：

template<class T>
void function(T A,T B){
    ...// 函数体
}

       但在实际的开发中，我们可能很少用到template，因为大部分情况下，我们只需要处理单一类型的需求，即使有重复，我们也通常复制粘贴解决。

       而面对大型库的开发，减少代码重复，保证其泛用性，我们就必须使用template提供的无定型数据，即泛型编程！

        比如下面的实例：

struct int_pairs{
    int a;
    int b;
};
struct float_pairs{
    float a;
    float b;
};
...

        面对这种代码大量重复而仅在类型上有区分的情况，我们完全可以用模板代码代替：

template<class T>
class pairs{
    T a;
    T b;
};// 叫pairs是为了与std::pair区分，请在实际开发中使用后者

       模板化的好处就是：它省略了类型，改为通过一个虚拟的模板参数来表示一个特定的实现，如果我们需要定义上述的int_pairs和float_pairs，只需要如下代码即可：

typedef pairs<int>     int_pairs;
typedef pairs<float> float_pairs;

        STL的诞生让泛型编程第一次被大规模使用，比如请见如下STL的源码：（取自SGI STL实现）

template <class Category, class T, class Distance = ptrdiff_t,
          class Pointer = T*, class Reference = T&>
struct iterator {
    typedef Category    iterator_category;
    typedef T           value_type;
    typedef Distance    difference_type;
    typedef Pointer     pointer;
    typedef Reference   reference;
};
template<class Iterator>
struct iterator_traits {
    typedef typename Iterator::iterator_category iterator_category;
    typedef typename Iterator::value_type       value_type;
    typedef typename Iterator::difference_type  difference_type;
    typedef typename Iterator::pointer          pointer;
    typedef typename Iterator::reference        reference;
}

        可以看到，在iterator这样的基层组件中，template是完完全全承担起了容纳各式各样数据类型的重任。

        泛型编程的优点是不言而喻的，当然，它也有一些缺点，比如：

template<typename T, typename U>
??? multiply(T a,U b){
    return a * b;
}

       因为T与U的参数还不在作用域内，我们没法定义出这个multiply函数的返回类型，在C++11之后，可以通过以下语法：

template<typename T,typename U>
auto multiply(T a,U b) -> decltype(T * U){
    return T * U;
}// C++11语法

template<typename T,typename U>
decltype(auto) multiply(T a,U b){
    return T * U;
}// C++14语法

       C++通过自动类型推断说明符decltype解决了这个问题，编译器会自动推断返回类型。

       我们将接下来了解各式各样的STL容器。

 

第二节：了解STL容器

       STL容器（即container）是一系列泛型化的数据结构，它们通过近乎专家级别的算法结构与内存管理，实现了从动态数组到内置红黑树的map与set等常用组件，这一节，我们将从最基础的vector，动态数组（也叫矢量）讲起。

       我们会在各种地方使用vector——比方说在内存不够时，vector能够减少内存开销，同时其能适应各式各样的STL算法（位于<algorithm>头文件）

       了解vector的用法前，我们需要了解基础：前面提到的iterator。

        iterator，迭代器，是一种智能指针，它可以用来指向各种各样的对象，同时其能提供优秀的内存管理与使用体验，在开发中，iterator可以框定一个容器的首尾范围，并能遍历各种容器的元素。

        我们以vector的迭代器为例：

std::vector<int> a;
auto begin = a.begin();
auto end   = a.end();

         begin()与end()成员函数会返回a的首尾迭代器。其中，begin()指向开头第一个元素，而end()指向最后一个元素的再后一个元素，即“超尾迭代器”，end()实际上是不可抵达的，因而对于大部分寻找算法，在找不到对应元素后都会返回end()表示未找到。

        在[begin,end)（左闭右开区间）中，我们可以通过迭代器的循环遍历其每一个元素：

#include <iostream>
#include <cstdlib>
#include <vector>// 定义vector的头文件

int main(){
    std::vector<int> a = {喵};//可以通过列表初始化定义vector
    auto begin = a.begin();
    auto end   = a.end();
    for(auto i = begin;i < end;++i){// end()在循环中到达不了，只能用<而非<=
        std::cout << *i << ",";// 注意到迭代器的本质就是指针，因而使用*解引用来获取它所指向的内容
    }// 或者写成for(auto i = a.begin();i < a.end();++i)
}

          即可输出如下内容：

喵,

          如果你不想要最后一个逗号，那么：

#include <iostream>
#include <cstdlib>
#include <vector>// 定义vector的头文件

int main(){
    std::vector<int> a = {喵};
    for(auto i = a.begin();i < a.end();++i){
        std::cout << *i;
        if(i < a.end() - 1)
            std::cout << ",";
    }
}

        可以看到，a.end() - 1即代表末尾的元素。

        vector的常用方法如下：

std::vector<int> a;
size_t s = a.size();// 返回a的元素个数
a.push_back(int);// 在a的末尾添加新元素
a.push_front(int);// 在a的开头添加新元素
a.erase(std::vector<int>::iterator);// 通过指向其中一个元素的iterator来删除此元素
a.operator[](int i);// 以数组表示法返回第i个元素，即return a[i];
a.at(int i);// 返回第i个元素，但会检查是否越界，若是则会抛出out_of_range异常，相较于数组表示法性能较低

        一些常用算法也可以使用在vector上（它们并不是vector独有的）：

void reverse(a.begin(),a.end());// 将[begin(),end())间的元素反转
auto Iter = find(a.begin(),a.end(),int S);// 在[begin,end)中寻找S，若没有则返回a.end()，否则返回其所在位置的迭代器
std::sort(a.begin(),a.end());// 对[begin(),end())之间的元素排序，默认使用从小到大的排序顺序，也可以自定义（详见之后一元谓词的详解）
//请注意，reverse和sort都会修改a的内容

        我们现在可以写出如下代码：

#include <iostream>
#include <cstdlib>
#include <algorithm>// 定义STL算法的头文件
#include <vector>// 定义vector的头文件

int main(){
    std::vector<int> a;
    int n;
    std::cout << "输入元素个数: ";
    std::cin >> n;// 输入元素的个数
    for(auto i = 0;i < n;++i){
        int tmp; 
        std::cin >> tmp;
        a.push_back(tmp);// 添加元素
    }
    std::cout << "查找: ";
    int find_num;
    std::cin >> find_num;
    auto iter = find(a.begin(),a.end(),find_num);
    std::cout << "位于第" << (iter - a.begin() + 1) << "个元素" << std::endl;
    //迭代器的加减可以直接对应数组的下标，它返回两个迭代器的距离（与类型无关）
    std::cout << "排序结果: "<<std::endl;
    std::sort(a.begin(),a.end());
    for(auto i = a.begin();i < a.end();++i){
        std::cout << *i;
        if(i < a.end() - 1)
            std::cout << ",";
    }
    return 0;
}

         以下为输出结果：

输入元素个数: 10
19 10 39 47 23 67 91 12 46 77
查找: 39
位于第3个元素
排序结果:
10,12,19,23,39,46,47,67,77,91

        vector也可以赋值给另一个同类型的vector，如下：

std::vector<int> b = a;

作业

1.STL的编程基础（思想）是什么？

2.在STL中，使用什么表示容器范围？

3.对于一个容器，它的end()表示什么？

4.写出三个vector容器自身的方法

5.写一个程序，要求定义一个vector，并能完成以下操作：

程序不断读入一个字符串

        当用户输入"find"字符串时，询问“查找：”，接受一个数字，并返回它在vector中的位置

        当用户输入"sort"字符串时，在不修改原来vector的情况下输出其排序后的结果

        当用户输入"pushend"字符串时，接受一个数字并将其加入末尾，输入"pushfront"则将其加入开头

 

a.insert(a.begin(),n);

#include <algorithm>
#include <vector>
#include <cstdlib>
#include <iostream>

int main(){
    std::vector<int> a;
    while(true){
        std::string str;
        std::cin >> str;
        if(str == "find"){
            std::cout << "查找: ";
            int n;
            std::cin >> n;
            auto i = find(a.begin(),a.end(),n);
            if(i == a.end())
                std::cout << "未找到!"<< std::endl;
            else
                std::cout << "位于第" << (i - a.begin() + 1) << "个位置" << std::endl;
        }else if(str == "sort"){
            std::vector<int> b = a;
            sort(b.begin(),b.end());
            std::cout << "排序: " << std::endl;
            for(auto i = b.begin();i < b.end();++i){
                std::cout << *i;
                if(i < b.end() - 1)
                    std::cout << ",";
            }
            std::cout << std::endl;
        }else if(str == "pushfront"){
            std::cout << "输入: ";
            int n;
            std::cin >> n;
            a.insert(a.begin(),n);
        }else if(str == "pushend"){
            std::cout << "输入: ";
            int n;
            std::cin >> n;
            a.push_back(n);
        }else
            std::cout << "未知指令" << std::endl;
    }
    return 0;
}