C++ STL 做为C++的一个标准类库，包含了复用性最高的数据结构（容器）与算法（模板函数）。

STL考虑到类型对于数据结构与算法的通用性，使用了模板这种语法机制来实现类型的泛化，也就是泛型。

STL考虑到算法对于数据结构的普遍适用，增加了一个中间层 － 迭代器。迭代器也是一种模板类，通常定义为容器类的内部类，封装一个指向容器类的指针，并重载与指针相关的一些运算符。各容器的迭代器提供统一名称的接口，以方便使用。算法（模板函数）通常以一对迭代器（指向容器第一个元素和容器最后一个元素的后部）为参数来遍历容器元素。

STL为了让算法（模板函数）的代码更加通用，通常使用函数对象（仿函数）为参数，让其适用不同的应用特定要求，如less<int>、greater<int>等。

1 vector 向量

vector顺序存储元素（以数组为底层数据结构），元素类型可嵌套，元素数量可动态增长，支持随机访问。是C++推荐使用的类型（代替C数组）。

vector支持inert()，但push_back()效率相对要高。

#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
bool cmp(int &x, int& y)
{
    return x>y;
}
void vectorUse()
{
    int a[10] = {2,5,8,6,3,7,1,9,4,10};
    vector<int>vec(a,a+10);
    printf("size:%d\n",vec.size());
    printf("正向输出 vec:");
    vector<int>::iterator it,it2;
    for(it=vec.begin();it!=vec.end();it++)
    {
        printf("%d ",*it);
    }
    printf("\n");
    int x = 6;
    it2 = find(vec.begin(),vec.end(),x);
    if(it2!=vec.end())
        printf("查找到元素%d\n",*it2);
    else
        printf("没有找到元素%d\n",x);
    printf("递减排序\n");
    sort(vec.begin(),vec.end(),cmp);
    vector<int>::reverse_iterator rit;
    printf("反向输出 vec:");
    for(rit=vec.rbegin();rit!=vec.rend();rit++)
        printf("%d ",*rit);
    printf("\n");
}

int main()
{
    vectorUse();
    getchar();
    return 0;
}
/*
size:10
正向输出 vec:2 5 8 6 3 7 1 9 4 10
查找到元素6
递减排序
反向输出 vec:1 2 3 4 5 6 7 8 9 10
*/

2 deque 双端队列

在功能上和vector相似，但是可以在前后两端向其中相对较高效率地添加数据（用map管理多个size大小的连续内存块）。一个中央控制器（连续存储的指向不同元素的指针所组成的数组）和多个缓冲区。

支持首尾（中间不能）快速增删，也支持随机访问。

#include <stdio.h>
#include <deque>
using namespace std;
void print(deque<int> &dq)
{
    deque<int>::iterator iter;
    for(iter=dq.begin();iter!=dq.end();iter++)
        printf("%d ",*iter);
    printf("\n");
}
void userDeque()
{
    deque<int> dq;
    dq.push_front(1);
    dq.push_back(2);
    dq.push_front(3);
    dq.push_back(4);
    print(dq);
    dq.pop_front();
    dq.pop_back();
    print(dq);
}
int main()
{
    userDeque();
    getchar();
    return 0;
}
/*
3 1 2 4
1 2

*/

3 list 链表

由节点组成的双向链表（每个节点有指向前驱和指向后继的两个指针），在任意位置进行快速插入和删除操作。

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

bool cmp(const int &n)
{
    return n<3;
}

void print(list<int> &lst)
{
    list<int>::iterator it;
    for(it=lst.begin();it!=lst.end();it++)
        printf("%d ",*it);
    printf("\n");
}

void useList()
{
    int a[] = {1,2,3,3,3,4,5,4,4,5};
    int n = sizeof a / sizeof *a;
    list<int> lst(a,a+n);
    lst.remove_if(cmp);
    cout<<"remove_if: ";
    print(lst);
    lst.unique();
    cout<<"unique: ";
    print(lst);
}

void useList2()
{
    int a[] = {3,5,1,4,6,2};
    list<int>lst(a,a+6);
    list<int>::iterator iter;
    lst.sort();
    for(iter=lst.begin();iter!=lst.end();iter++)
        printf("%d ",*iter);
    printf("\n");
    lst.sort(greater<int>());
    for(iter=lst.begin();iter!=lst.end();iter++)
        printf("%d ",*iter);
    printf("\n");
}

class Ctest
{
    int n;
public:
    Ctest(int m):n(m){}
    ~Ctest(){}
    const int getn() const
    {
        return n;
    }
    const bool operator<(const Ctest& s)const
    {
        return n>s.getn();
    }
};

void print(list<Ctest> &lst)
{
    list<Ctest>::iterator it;
    for(it=lst.begin();it!=lst.end();it++)
        printf("%d ",*it);
    printf("\n");
}

void useList3()
{
    Ctest obj1(3),obj2(5),obj3(2);
    Ctest obj4(7),obj5(4),obj6(1),obj7(6);
    list<Ctest> lst1,lst2;
    lst1.push_back(obj1);
    lst1.push_back(obj2);
    lst1.push_back(obj3);
    lst2.push_back(obj4);
    lst2.push_back(obj5);
    lst2.push_back(obj6);
    lst2.push_back(obj7);
    printf("排序前：\n");
    printf(" lst1: ");
    print(lst1);
    printf(" lst2: ");
    print(lst2);
    printf("排序\n");
    lst1.sort();
    lst2.sort();
    printf("排序后：\n");
    printf(" lst1: ");
    print(lst1);
    printf(" lst2: ");
    print(lst2);
    printf("lst1合并到lst2\n");
    lst2.merge(lst1);
    print(lst2);
}

int main()
{
    //useList()
    useList2();
    useList3();

    getchar();
    return 0;
}
/* useList(); vc6运行有误，在线可运行
remove_if: 3 3 3 4 5 4 4 5 
unique: 3 4 5 4 5 
1 2 3 4 5 6
6 5 4 3 2 1
*/

4 set 集合

以树型结构来存储线性数据，以确保数据元素（节点，关键字）预定的有序性。其底层数据结构是红黑树（二叉平衡树，在数据增、删时会考虑数据有序性而需要考虑调整元素存储位置）。要求元素唯一。

STL set底层为什么用红黑树，不用哈希表？set支持集合操作，集合的并、交、差等运算在数据有序时其时间复杂度会大大降低，而红黑树是一种有序结构。

#include <stdio.h>
#include <set>
#include <algorithm>
using namespace std;
void print(set<int> &st)
{
    set<int>::iterator it;
    for(it=st.begin();it!=st.end();it++)
        printf("%d ",*it);
    printf("\n");
}
void useSet()
{
    set<int>st1,st2,st3;
    int a[]={4,1,2,6};
    int n=sizeof a / sizeof *a;
    st1.insert(a,a+n);
    int b[]={1,5,3,2,4};
    int m=sizeof b / sizeof *b;
    st2.insert(b,b+m);
    //set<int>::iterator it3;
    printf("set1: ");
    print(st1);
    printf("set2: ");
    print(st2);
    insert_iterator< set<int> > insert_it(st3,st3.begin());
    set_union(st1.begin(),st1.end(),st2.begin(),st2.end(),insert_it);
    printf("并集：");
    print(st3);
    st3.clear();
    set_intersection(st1.begin(),st1.end(),st2.begin(),st2.end(),insert_it);
    printf("交集：");
    print(st3);
    st3.clear();
    set_difference(st1.begin(),st1.end(),st2.begin(),st2.end(),insert_it);
    printf("差集：");
    print(st3);
    st3.clear();
    
}
int main()
{
    useSet();
    getchar();
    return 0;
}
/*
set1: 1 2 4 6
set2: 1 2 3 4 5
并集：1 2 3 4 5 6
交集：1 2 4
差集：6

*/

5 map 映射

以树型结构来存储线性数据，以确保数据元素（节点，由关键字、值组成）预定的有序性。其底层数据结构是红黑树（二叉平衡树，在数据增、删时会考虑数据有序性而需要考虑调整元素存储位置）。要求元素唯一。

元素关键字和值一对一映射，可以基于关键字快速查找。

我们知道，C数组支持下标操作，通过数字索引来映射元素的存储位置，其实质是指针算术运算的语法糖。而map也同样支持下标操作，通过关键字来映射元素的存储位置，其实质是一种树型二分搜索。

#include <stdio.h>
#include <map>
#include <algorithm>
using namespace std;
void print(map<char,int> &mp)
{
    map<char,int>::iterator it;
    for(it=mp.begin();it!=mp.end();it++)
        printf("[%c,%d] ",it->first,it->second);
    printf("\n");
}
void useMap()
{
    map<char,int>mp;
    mp.insert(pair<char,int>('a',1));
    mp.insert(map<char,int>::value_type('b',2));
    mp['c']=3;
    printf("map: ");
    print(mp);
}
int main()
{
    useMap();
    getchar();
    return 0;
}
/*
#include <iostream>
using namespace std;

*/

6 stack 堆栈

在特定情形下，我们希望限定对元素的访问顺序。如后进先出（最后存储进去的元素，确保最先访问）。最常用的适用场景就是函数的嵌套调用与返回，括号匹配，进制转换，优先遍历等。这种特定的数据结构，我们可以通过数组或列表来简单模拟，与数组支持随机访问或列表支持顺序访问不同，我们用数组或列表来模拟时，限定其只在一端进行操作（增、删、读）。STL的stack的底层数据结构一般使用list或deque。

#include <iostream>       // std::cout
#include <stack>          // std::stack

int main ()
{
    std::stack<int> mystack;
    
    for (int i=0; i<5; ++i) 
        mystack.push(i);
    
    std::cout << "Popping out ";
    std::cout << mystack.size();
    std::cout << " elements...";
    while (!mystack.empty())
    {
        std::cout << ' ' << mystack.top();
        mystack.pop();
    }
    std::cout << '\n';
    getchar();
    return 0;
}
// Popping out 5 elements... 4 3 2 1 0

7 queue 队列

在特定情形下，我们希望限定对元素的访问顺序。如后进后出（最后存储进去的元素，确保最后访问）。最常用的适用场景就是广度优先遍历等。这种特定的数据结构，我们可以通过数组或列表来简单模拟，与数组支持随机访问或列表支持顺序访问不同，我们用数组或列表来模拟时，限定其只在前、后端进行操作（增、删、读）。queue要求提供push_back和push_front的功能，因此可以使用list或deque作为底层数据结构，而不能使用vector作为底层数据结构。

// constructing queues
#include <iostream>       // std::cout
#include <deque>          // std::deque
#include <list>           // std::list
#include <queue>          // std::queue

int main ()
{
  std::deque<int> mydeck (3,100);        // deque with 3 elements
  std::list<int> mylist (2,200);         // list with 2 elements

  std::queue<int> first;                 // empty queue
  std::queue<int> second (mydeck);       // queue initialized to copy of deque

  std::queue<int,std::list<int> > third; // empty queue with list as underlying container
  std::queue<int,std::list<int> > fourth (mylist);

  std::cout << "size of first: " << first.size() << '\n';
  std::cout << "size of second: " << second.size() << '\n';
  std::cout << "size of third: " << third.size() << '\n';
  std::cout << "size of fourth: " << fourth.size() << '\n';
  int sum (0);

  for (int i=1;i<=10;i++) 
      first.push(i);

  while (!first.empty())
  {
     sum += first.front();
     first.pop();
  }

  std::cout << "total: " << sum << '\n';
  std::cout << first.front() << " " << first.back();
  return 0;
}
/*
size of first: 0
size of second: 3
size of third: 0
size of fourth: 2
total: 55
0 10
*/

8 priority_queue 优先队列

在特定情形下，我们希望优先度（如数值最大或最小）最高的元素确保最先访问，这样的数据结构称为优先队列。自然，这种数据结构的数据元素的增删需要考虑元素存储的优先顺序而需要考虑调整。priority_queque要求提供随机访问的功能，因此可以使用vector或deque作为底层数据结构，而不能使用list作为底层数据结构。

优先队列通常通过堆来实现，而堆一般可以通过二叉树来实现。

#include <stdio.h>
#include <queue>
using namespace std;
void print(priority_queue<int> &pq)
{
    while(!pq.empty())
    {
        printf("%d ",pq.top());
        pq.pop();
    }
    printf("\n");
}
void print(priority_queue<int,vector<int>,greater<int> > &pq)
{
    while(!pq.empty())
    {
        printf("%d ",pq.top());
        pq.pop();
    }
    printf("\n");
}

void useQue()
{
    int a[] = {3,6,1,5,4,2};
    int n = sizeof a / sizeof *a;
    priority_queue<int>pq1(a,a+n); // 默认以vector作为底层容器

    print(pq1);
    // 显式声明底层容器vector，谓词函数greater
    priority_queue<int,vector<int>,greater<int> > pq2(a,a+n);
    print(pq2);
}

#include <string>
struct Stud
{
    int no;
    string name;
    Stud(int n,string na):no(n),name(na){}
    bool operator<(const Stud &s)const{
        return no<s.no;
    }
    bool operator>(const Stud &s)const{
        return no>s.no;
    }
};
struct StudCmp{ // 结构体定义函数对象
    bool operator()(const Stud &s1,const Stud &s2)const{
        return s1.name > s2.name;
    }
};
void print(priority_queue<Stud> &pq)
{
    while(!pq.empty())
    {
        printf("[%d %s] ",pq.top().no,pq.top().name.c_str());
        pq.pop();
    }
    printf("\n");
}
void print(priority_queue<Stud,vector<Stud>,StudCmp > &pq)
{
    while(!pq.empty())
    {
        printf("[%d %s] ",pq.top().no,pq.top().name.c_str());
        pq.pop();
    }
    printf("\n");
}
void useQue2()
{
    Stud a[] = {Stud(1,"Mary"),Stud(3,"John"),Stud(2,"Henry")};
    int n = sizeof a / sizeof *a;
    priority_queue<Stud> pq1(a,a+n);
    print(pq1);
    priority_queue<Stud,vector<Stud>,StudCmp >pq2(a,a+n);
    print(pq2);
}

int main()
{
    useQue();
    useQue2();
    getchar();
    return 0;
}
/*
6 5 4 3 2 1
1 2 3 4 5 6
[3 John] [2 Henry] [1 Mary]
[2 Henry] [3 John] [1 Mary]
*/

9 unordered_map 无序哈希表

数据要求存得进去，取得出来，并要考虑效率。哈希表就是这种思路的最佳实践。

我们知道，数组可以通过数字下标来随机访问，但只能顺序查找。

哈希存储在数据元素存储时，通过一个哈希函数（以数据元素的关键字为参数）为计算一个数据元素特定的下标作为存储位置（当然还要考虑冲突处理）。这样，数据元素访问时，便可以以关键字为下标索引来访问，其最佳情形可以达到O(1)的访问效率。

10// unordered_map::operator[]
#include <iostream>
#include <string>
#include <unordered_map>

int main ()
{
  std::unordered_map<std::string,std::string> mymap;

  mymap["Bakery"]="Barbara";  // new element inserted
  mymap["Seafood"]="Lisa";    // new element inserted
  mymap["Produce"]="John";    // new element inserted

  std::string name = mymap["Bakery"];   // existing element accessed (read)
  mymap["Seafood"] = name;              // existing element accessed (written)

  mymap["Bakery"] = mymap["Produce"];   // existing elements accessed (read/written)

  name = mymap["Deli"];      // non-existing element: new element "Deli" inserted!

  mymap["Produce"] = mymap["Gifts"];    // new element "Gifts" inserted, "Produce" written

  for (auto& x: mymap) {
    std::cout << x.first << ": " << x.second << std::endl;
  }

  return 0;
}
/*
Gifts: 
Deli: 
Produce: 
Seafood: Barbara
Bakery: John
*/

10 小结一下

STL中的容器（数据结构）和模板类函数（算法）就是给程序员提供的“轮子”。凝聚了库设计者和实现者最佳的程序设计思路。

每种容器都有自己的底层数据结构，每种容器都有自己特定的优势和应用场景。

http://www.cplusplus.com/reference/

－End－