• 为什么要有STL，自己做算法不好吗？

其实自己做算法挺好的，有时候思路不一样，说不定还更省时间，但是！！你有没有想过，你也总有一天会写出不高效的算法吧，STL都嫌弃的人是不可能用boost了，因为boost里的东西比STL激进多了,c++都学了，何必要阉割STL呢

面向过程--->基于对象--->面向对象--->泛型

• 面向过程：是把程序分成若干个子过程，将事物的方法隐藏于各个函数内--（C语言）。并且只适用于用小型的程序，对于大型程序不易处理变化的需求，所以我们才需要新的抽象。
• 基于对象：与前者相比，可以更好的处理变化，但是各个类之间的关系不容易处理，而且代码的数量比面向过程更大----需要新的抽象。
• 面向对象： 与基于对象相比，有更多的间接性。运用多态，我们可以调用某种方法，而不用指定此方法所属的类型。因而达到更进一步的抽象性。
  它为我们带来了------MFC（以C++类的形式封装了Windows API，并且包含一个应用程序框架，以减少应用程序开发人员的工作量。
• 泛型：（Generic）是一种抽象的就如OO是一种抽象一样。
  相应语法：Template
  它为我们带来了今天的主角：-----STL（简单来说就是 数据结构和算法的模板的集合）

泛型程序设计：（使用模板的程序设计）

• 解释：将一些常用的数据结构（比如：链表、数组、二叉树）和算法（比如 排序，查找）写成模板，以后不论数据结构里放的是什么对象，算法针对什么样的对象，则都无需重新实现数据结构，重新编写算法，而且还能获得非常高的性能（此处有争议哈哈哈哈哈哈哈）
  如果说之前我们学了那么多鬼语言，做了那么多的铺垫都仅仅是钻木取火的话，辣么我们现在用STL代表着我们进入工业时代啦！

• STL的三个关键组件：

• 容器：一个STL容器是一个数据结构，也是类模板，其中包括：vector\deque\list\set\map\stack\queue等。
• 迭代器：可用于一次存取容器中元素，类似于指针。
• 算法：用来操作容器中的元素的函数模板。

这张图片完美的向我们展示了STL该有的责任：

STL

对三大关键组件内容的详细展开:

• 容器：

容器的三大分类

顺序容器、关联容器的存储模型

• 迭代器（iterator）

迭代器的作用：能够让迭代器与算法不干扰的相互发展，最后又能无间隙的粘合起来，重载了*，＋＋，＝＝，！＝，＝运算符。用以操作复杂的数据结构，容器提供迭代器，算法使用迭代器；常见的一些迭代器类型：iterator、const_iterator、reverse_iterator和const_reverse_iterator
例子：
vector <int> ::const_iterator i;

 #include <iostream>  
    #include <vector>  
    using namespace std;  
    int main()  
    {  
        vector<int> v;  
        v.push_back(3);  //数组尾部插入3  
        v.push_back(2);  
        v.push_back(1);  
        v.push_back(0);  
        cout << " 下标 " << v[3] << endl;  
        cout << " 迭代器 " << endl;  
        for(vector<int>::iterator i = v.begin();i!= v.end();++i)  
        {  
            cout << *i << " ";  
        }  
        cout << endl;  
        //在第一个元素之前插入111  insert begin+n是在第n个元素之前插入  
        v.insert(v.begin(),111);  
        //在最后一个元素之后插入222 insert end + n 是在n个元素之后插入  
        v.insert(v.end(),222);  
        for(vector<int>::iterator i = v.begin();i!= v.end();++i)  
        {  
            cout << *i << " ";  
        }  
        cout << endl;  
      
        vector<int> arr(10);  
        for(int i = 0; i < 10; i++)  
        {  
            arr[i] = i;  
        }  
        for(vector<int>::iterator i = arr.begin();i!= arr.end();++i)  
        {  
            cout << *i << " ";  
        }  
        cout << endl;  
        //删除 同insert  
        arr.erase(arr.begin());  
        for(vector<int>::iterator i = arr.begin();i!= arr.end();++i)  
         {  
            cout << *i << " " ;  
         }  
        cout << endl ;  
        arr.erase(arr.begin(),arr.begin()+5);  
        for(vector<int>::iterator i = arr.begin();i!= arr.end();++i)  
        {  
            cout << *i << " " ;  
        }  
        cout << endl ;  
        return 0 ;  
     }  

• 利用 reverse(v.begin(),v.end())进行数组转置：

#include<iostream>  
#include<vector>  
#include<algorithm>  
using namespace std;  
int main()  
{  
    vector<int> v;  
    for(int i = 0; i < 10; ++i)  
    {  
        v.push_back(i);  
    }  
    for(vector<int>::iterator it = v.begin(); it != v.end(); ++it)  
    {  
        cout << *it << " ";  
    }  
    cout << endl;  
    reverse(v.begin(),v.end());  
    for(vector<int>::iterator it = v.begin(); it != v.end(); ++it)  
    {  
        cout << *it << " ";  
    }  
    cout << endl;  
    return 0;  
}

对vector的详细整理：

• vector的初始化：

vector                 // 创建一个空的vector。
vector c1(c2)          // 复制一个vector
vector c(n)            // 创建一个vector，含有n个数据，数据均已缺省构造产生
vector c(n, elem)      // 创建一个含有n个elem拷贝的vector
vector c(beg,end)      // 创建一个含有n个elem拷贝的vector

• 析构函数

c.~vector ()           // 销毁所有数据，释放内存

• 成员函数

c.assign(beg,end)c.assign(n,elem)
　　将[beg; end)区间中的数据赋值给c。将n个elem的拷贝赋值给c。
c.at(idx)
　　传回索引idx所指的数据，如果idx越界，抛出out_of_range。

常用：
c.back() // 传回最后一个数据，不检查这个数据是否存在。
c.begin() // 传回迭代器中的第一个数据地址。
c.capacity() // 返回容器中数据个数。
c.clear() // 移除容器中所有数据。
c.empty() // 判断容器是否为空。
c.end() // 指向迭代器中末端元素的下一个，指向一个不存在元素。
c.erase(pos) // 删除pos位置的数据，传回下一个数据的位置。
c.erase(beg,end) //删除[beg,end)区间的数据，传回下一个数据的位置。
c.front() // 传回第一个数据。
get_allocator // 使用构造函数返回一个拷贝。
c.insert(pos,elem) // 在pos位置插入一个elem拷贝，传回新数据位置。
c.insert(pos,n,elem) // 在pos位置插入n个elem数据。无返回值。
c.insert(pos,beg,end) // 在pos位置插入在[beg,end)区间的数据。无返回值。
　　
c.max_size() // 返回容器中最大数据的数量。
c.pop_back() // 删除最后一个数据。
c.push_back(elem) // 在尾部加入一个数据。
c.rbegin() // 传回一个逆向队列的第一个数据。
c.rend() // 传回一个逆向队列的最后一个数据的下一个位置。
c.resize(num) // 重新指定队列的长度。
c.reserve() // 保留适当的容量。
c.size() // 返回容器中实际数据的个数。
c1.swap(c2)
swap(c1,c2) // 将c1和c2元素互换。同上操作。
operator[] // 返回容器中指定位置的一个引用。

• 用法示例：

• 创建一个vector：
  vector容器提供了多种创建方法，下面介绍几种常用的。

创建一个Widget类型的空的vector对象：
　　vector vWidgets;
　　
创建一个包含500个Widget类型数据的vector：
　　vector vWidgets(500);
　　
创建一个包含500个Widget类型数据的vector，并且都初始化为0：
　　vector vWidgets(500, Widget(0));
　　
创建一个Widget的拷贝：
　　vector vWidgetsFromAnother(vWidgets);
　　
向vector添加一个数据
　　vector添加数据的缺省方法是push_back()。
push_back()函数表示将数据添加到vector的尾部，并按需要来分配内存。

例如：向vector中添加10个数据，需要如下编写代码：
　　for(int i= 0;i<10; i++) {
　　 vWidgets.push_back(Widget(i));
　　}

• 获取vector中指定位置的数据

vector里面的数据是动态分配的，使用push_back()的一系列分配空间常常决定于文件或一些数据源。
如果想知道vector存放了多少数据，可以使用empty()。
获取vector的大小，可以使用size()。

例如，如果想获取一个vector v的大小，但不知道它是否为空，或者已经包含了数据，如果为空想设置为-1，
你可以使用下面的代码实现：
　　int nSize = v.empty() ? -1 : static_cast(v.size());

• 访问vector中的数据
  使用两种方法来访问vector。
  1、 vector::at()
  2、 vector::operator[]
  　　operator[]主要是为了与C语言进行兼容。它可以像C语言数组一样操作。
  但at()是我们的首选，因为at()进行了边界检查，如果访问超过了vector的范围，将抛出一个例外。
  由于operator[]容易造成一些错误，所有我们很少用它，下面进行验证一下：
  　　
  分析下面的代码：

　　vector v;
　　v.reserve(10);
　　
    for(int i=0; i<7; i++) {
　　  v.push_back(i);
　　}
　　
    try {int iVal1 = v[7];
　　  // not bounds checked - will not throw
　　  int iVal2 = v.at(7);
　　  // bounds checked - will throw if out of range
　　} 

    catch(const exception& e) {
　　  cout << e.what();
　　}
　

• 删除vector中的数据
  vector能够非常容易地添加数据，也能很方便地取出数据，
  同样vector提供了erase()，pop_back()，clear()来删除数据，
  当删除数据时，应该知道要删除尾部的数据，或者是删除所有数据，还是个别的数据。

Remove_if()有三个参数：
　　1、 iterator _First：指向第一个数据的迭代指针。
　　2、 iterator _Last：指向最后一个数据的迭代指针。
　　3、 predicate _Pred：一个可以对迭代操作的条件函数。
　　

图片.png

• 编程测试顺序容器矢量（vector）的主要功能和使用方法。
  解：

#include<algorithm>
#include<vector>
#include<iostream>
#include<functional>
using namespace std;

int main(){
    ostream_iterator<int> output(cout," "); 
    //用输出迭代子output来输出，其中第二参数" "表示用空格分隔各个整数。
    int ia[18]={47,29,5,37,13,23,11,61,7,31,41,2,59,19,17,53,43,3};
    vector<int> vec(ia,ia+9); //数据填入vector;vector共有7个构造函数,常用3个
    //vector(),用以声明空的vector;vector(n),用以声明有n个元素的vector；
    //vector(first,last),用以声明一个vector，
    //其元素的初值是从区间[first,last)所指定的序列中的元素复制而来的；
    vector<int> vec2(18); 
    if(vec.empty()) cout<<"vector空"<<endl;
    else{
        cout<<"vector不空，"<<"vector中的元素："<<endl;
        unique_copy(vec.begin(),vec.end(),output);
        cout<<endl;
    }
    cout<<"当前分配元素空间数量:"<<vec.capacity()<<endl;
    vec.reserve(12);
    cout<<"当前为vector保留的最小分配元素空间数量:"<<vec.capacity()<<endl;
    vec.erase(vec.begin(),vec.end());
    cout<<"当前分配元素空间数量:"<<vec.capacity()<<endl;
    vec.resize(10);
cout<<"当前重新分配元素空间数量为10，实际分配元素空间数量:"
 <<vec.capacity()<<endl;
    vec.assign(ia+10,ia+16);
    cout<<"vector存放序列容许最大长度："<<vec.max_size()<<endl;
    cout<<"vector中的元素："<<endl;
    unique_copy(vec.begin(),vec.end(),output);
    cout<<endl;
    vec.assign(ia,ia+18);
    cout<<"vector中的元素："<<endl;
    unique_copy(vec.begin(),vec.end(),output);
    cout<<endl;
    sort(vec.begin(),vec.end(),greater<int>());//降序排列
    cout<<"vector中的元素："<<endl;
    unique_copy(vec.begin(),vec.end(),output);
    cout<<endl;
    cout<<"用反转迭代子输出vector中的元素："<<endl;
    unique_copy(vec.rbegin(),vec.rend(),output);
    cout<<endl;cout<<"第1个元素："<<vec.front()<<endl;
    cout<<"最后1个元素："<<vec.back()<<endl;
    cout<<"第8个元素："<<vec[6]<<endl;
    cout<<"原vector2中的元素："<<endl;
    unique_copy(vec2.begin(),vec2.end(),output);
    cout<<endl;
    vec2.swap(vec);
    cout<<"交换后vector2中的元素："<<endl;
    unique_copy(vec2.begin(),vec2.end(),output);
    cout<<endl;
    return 0;
}

• 编程测试顺序容器列表（list）的主要功能和使用方法。
  解：

#include<algorithm>
#include<list>
#include<iostream>
#include<functional>
using namespace std;

int main(){
    ostream_iterator<int>output(cout," "); 
    //用输出迭代子output来输出，其中第二参数" "表示用空格分隔各个整数。
    int ia[18]={47,29,5,37,13,23,11,61,7,31,41,2,59,19,17,53,43,3};
    list<int> list1(ia,ia+18); //数据填入list1;list共有7个构造函数,常用3个
    //list(),用以声明空的list;list(n),用以声明有n个元素的list；
    //list(first,last),用以声明一个list，
    //其元素的初值是从区间[first,last)所指定的序列中的元素复制而来的；
    list<int> list2(18); 
    if(list1.empty()) cout<<"list1空"<<endl;
    else{
        cout<<"list1不空，"<<"list1中的元素："<<endl;
        unique_copy(list1.begin(),list1.end(),output);
        cout<<endl;
    }
    list1.sort(greater<int>());//降序排列
    cout<<"list1中的元素降序排列："<<endl;
    unique_copy(list1.begin(),list1.end(),output);
    cout<<endl;
    cout<<"用反转迭代子输出list1中的元素："<<endl;
    unique_copy(list1.rbegin(),list1.rend(),output);
    cout<<endl;cout<<"第1个元素："<<list1.front()<<endl;
    cout<<"最后1个元素："<<list1.back()<<endl;
    cout<<"原list2中的元素："<<endl;
    unique_copy(list2.begin(),list2.end(),output);
    cout<<endl;
    list2.swap(list1);
    cout<<"交换后list2中的元素："<<endl;
    unique_copy(list2.begin(),list2.end(),output);
    cout<<endl;
    cout<<"现list1中的元素空了："<<endl;
    unique_copy(list1.begin(),list1.end(),output);
    cout<<endl;
    list1.assign(list2.begin(),list2.end());
    cout<<"将list2的元素赋到list1中："<<endl;
    unique_copy(list1.begin(),list1.end(),output);
    cout<<endl;
    list2.resize(10);
    cout<<"list2中的元素应剩10个："<<endl;
    unique_copy(list2.begin(),list2.end(),output);
    cout<<endl;
    list1.pop_back();
    cout<<"现list1中的元素："<<endl;
    unique_copy(list1.begin(),list1.end(),output);
    cout<<endl;
    list1.pop_front();
    cout<<"现list1中的元素："<<endl;
    unique_copy(list1.begin(),list1.end(),output);
    cout<<endl;
    list1.push_back(ia[17]);
    cout<<"因原list1中最后的元素与新插入元素相同，未能真正插入："<<endl;
    unique_copy(list1.begin(),list1.end(),output);
    cout<<endl;
    list1.push_front(ia[0]);
    cout<<"现list1中的元素："<<endl;
    unique_copy(list1.begin(),list1.end(),output);
    cout<<endl;
    return 0;
}

• 编程测试以双向队列（deque）为基础的容器适配器队列（queue）的主要功能和使用方法。
  解：

#include<deque>
#include<queue>
#include<iostream>
using namespace std;

int main(){
    int i,j;
    double da[10]={3.1,4.2,84.5,18.3,6.8,5.9,8.3,22.8,1.23,4.7};
    queue<double> que1;
    for(i=0;i<10;i++) que1.push(da[i]);
    for(i=0;i<10;i++){
        cout<<que1.front()<<'\t';
        que1.pop();
    }
    cout<<endl;
    return 0;
}

• 使用映射（map），建立阿拉伯的数字0~9和英文单词Zero到Nine的映射关系，并输入阿拉伯数字（如：1），输出英文数字（如：One）。
  解：

#include<iostream.h>
#include<map>
using namespace std;

typedef map<int,char*> ismap;

int main(){
    int i=1,j;
    char* str[10]={"one","two","three","fore","five","six","sever","eight","nine","ten"};
    ismap trans_map1;
    ismap::iterator it;
    for(i=1;i<=10;i++)  trans_map1.insert(ismap::value_type(i,str[i-1]));
    for(it=trans_map1.begin();it!=trans_map1.end();it++) 
        cout<<(*it).first<<'\t'<<(*it).second<<endl;
    cout<<trans_map1.size()<<endl;
    cout<<"请输入1~10的数字："<<endl;
    cin>>j;
    it=trans_map1.find(j);
    cout<<(*it).first<<'\t'<<(*it).second<<endl;
    return 0;
}

这里是一些关于STL的面试题：
https://blog.csdn.net/weiyuefei/article/details/52089146