C++ STL简述-白红宇

C++ STL简述

阅读量：5246 次

发布时间：2019-06-14

本文共 5571 字，大约阅读时间需要 18 分钟。

前言

最近要找工作，免不得要有一番笔试，今年好像突然就都流行在线笔试了，真是搞的我一塌糊涂。有的公司呢，不支持Python，Java我也不会，C有些数据结构又有些复杂，所以是时候把STL再看一遍了…不会告诉你距离上次使用可能已经有半年以上了。

STL是什么

STL为C++的标准模版库，又称为C++泛型库，在std命名空间中定义了常用的数据结构和算法，使用起来十分方便。

STL提供三种类型的组件：

容器。主要有两类：顺序容器和关联容器。前者主要包括：vector，list，deque和string等，为一些列元素的有序集合。后者主要有：set，multiset，map和multimap，包含查找元素的键值

迭代器的作用是遍历容器

算法库。主要包括四类算法：排序算法，不可变序算法，变序性算法和数值算法

容器常用操作

这一节主要说一下各种容器的常用操作，直接看代码实例即可。

vector

向量容器可以像数组一样对元素进行随机访问，还可以在尾部插入元素，完全可以替代数组。具有内存自动管理的功能，对元素的插入和删除可以动态调整所占用的内存空间。

#include
    
     #include
     
      using namespace std;// sort指定的排序算法 bool Comp(const int &a, const int &b){        if(a!=b)            return a>b;        else            return a>b; } int main(void){    // 初始化有三种方式    // 元素下标均从0开始     vector
      
        v1;  //不指定元素个数     vector
       
         v2(10); // 10个元素，每个初值窦唯0.0     vector
        
          v3(10, 1);  // 10个元素，每个值都为1        // 尾部追加新元素    v1.push_back(1);        // 有2种方式访问元素     // 使用下标方式访问元素    cout<
         
          <

::iterator it; for(it=v1.begin();it!=v1.end();it++) cout<<*it<<" "; // 元素的插入注意：插入的位置为迭代器的位置，不是下标 v3.insert(v3.begin()+2, 0); // 元素的删除，删除迭代器所指的一个元素或一段区间的所有元素 v3.erase(v3.begin()+2); // 删除第3个元素 v3.erase(v3.begin()+1, v3.begin()+5); // 第二到第五个，前开后闭 // 清空 v3.clear(); // 判断是否为空 v1.empty(); // 为空则返回假，反之为真 // 查看元素个数 v2.size(); // reverse反向排列算法，需#include

reverse(v1.begin(), v1.end()); // 排序，需#include

sort(v1.begin(), v1.end()); // 自己指定排序算法 sort(v1.begin(), v1.end(), Comp); }

string

可以把string理解为字符串类，提供了添加、删除、替换、查找和比较丰富的方法，当然也可以使用vector来处理字符串，但是不如string功能丰富。同时可以使用vector这样的向量，类似于字符数组。

#include
    
     #include
     
      #include
      
       using namespace std;// sort指定的排序算法 bool Comp(const int &a, const int &b){        if(a!=b)            return a>b;        else            return a>b; } int main(void){    // 创建string对象    string s;        // 赋值    s = "abc";  // or cin>>s;  or char ss[5000]; scanf("%s", &ss); s=ss;        // 尾部添加字符     s = s + 'd';        // 尾部添加字符串    s = s + "hello world";         // append()方法添加    s.append("123");        // 插入字符到迭代器的位置之前    s.insert(s.begin(), 'p');         // 访问string对象元素    cout<
       
        <
        
          v;    }

set

set实现了红黑树的平衡二叉检索树的数据结构，在插入元素的时候会自动调整二叉树的排列，把元素放到适当的位置，以确保每个子树根节点键值大于左子树所有节点，同时小于右边节点；另外，还要得确保左右子树高度相等。不会插入同样键值的元素。

平衡二叉检索树的检索采用中序遍历算法，构造set的目的是为了快速检索。

#include
    
     #include
     
      #include
      
       #include
       
        using namespace std;// sort指定的排序算法 bool Comp(const int &a, const int &b){        if(a!=b)            return a>b;        else            return a>b; } int main(void){    set
        
          s;        // 插入    s.insert(0);    s.insert(2);    s.insert(0); // 只有一个0        // 遍历    set
         
          ::iterator it; for(it=s.begin();it!=s.end();it++) cout<<*it<

::reverse_iterator rit=s.rbegin();rit!=s.rend();rit++) cout<<*rit<

map

map映照容器的元素数据由key, value组成，也采用红黑树实现，不允许重复键，比较函数只对value值比较，各项数据可以通过key检索。

#include
    
     #include
     
      #include
      
       #include
       #include
        
         using namespace std;// sort指定的排序算法 bool Comp(const int &a, const int &b){        if(a!=b)            return a>b;        else            return a>b; } int main(void){    // 初始化     map
         
           m; // 插入元素 m["wang"] = 99.9; m["zhao"] = 100.0; // 前向遍历 map
          
           ::iterator it; for(it=m.begin();it!=m.end();it++) cout<<(*it).first<<":"<<(*it).second<

deque

双端队列，可以在两侧进行操作。

#include
    
     #include
     
      #include
      
       #include
       #include
        
          #include
         
          using namespace std;// sort指定的排序算法 bool Comp(const int &a, const int &b){ if(a!=b) return a>b; else return a>b; } int main(void){ // init deque
          
            d; deque
           
             dd(10); deque
            
              ddd(10, 1); // 尾部插入，扩张队列 d.push_back(1); d.push_back(2); d.push_back(3); // 头部插入，会覆盖原有元素 d.push_front(10); d.push_front(20); // 此时为 20, 10, 1 // 前向遍历 for(int i=0;i

::iterator it=d.begin();it!=d.end();it++) cout<<*it<

::reverse_iterator rit, rbegin, rend // 删除 d.pop_front(); d.pop_back(); d.erase(d.begin()); // 清空 d.clear(); return 0; }

list

双向链表，节点保存不在连续内存中，所以迭代器只能通过 ++ 或 -- 操作来移动到前驱或者后继节点，不能使用 +n 或者 -n 来操作。

#include
    
     #include
     
      #include
      
       #include
       #include
        
          #include
         
          using namespace std;// sort指定的排序算法 bool Comp(const int &a, const int &b){ if(a!=b) return a>b; else return a>b; } int main(void){ // init list
          
            l; list
           
             ll(10); // 插入，3种方法链表都会自动扩张 l.push_back(1); l.push_front(2); l.push_back(3); l.push_back(4); l.insert(l.begin(), 20); // 遍历同其他容器 // 删除 l.remove(1); // 删除值为 1的所有元素 l.pop_front(); l.pop_back(); l.erase(l.begin()); // 清空 l.clear(); // find l.find(l.begin(), l.end(), 5); // sort l.sort(); // 升序排序 // 删除重复元素 l.unique(); return 0; }

stack

#include
    
     #include
     
      using namespace std;// sort指定的排序算法 bool Comp(const int &a, const int &b){        if(a!=b)            return a>b;        else            return a>b; } int main(void){    // init    stack
      
        s;        s.push(1);    s.push(3);    s.pop();        s.top();        cout<
       
        <

queue

#include
    
     #include
     
      using namespace std;// sort指定的排序算法 bool Comp(const int &a, const int &b){        if(a!=b)            return a>b;        else            return a>b; } int main(void){    queue
      
        q;        q.push(1);    q.push(1);    q.push(1);        cout<
       
        <