C++:STL(标准模板库)

STL：主要是一些“容器”的集合；“容器”有：vector(数组)、list(双向链表)、deque(双向队列)、set(集合)、map(图：内部结构红黑树)

STL也是算法和其他一些组件的集合，是泛型编程的一个经典范例。

STL的目的是标准化组件，这样就不用重新开发，可以使用现成的组件。

• STL六个组成部分

  1、容器：特殊的数据结构，实现了数组、链表、队列等，实质是类模板。

  2、迭代器：一种复杂的指针，可以通过其读写容器中的对象，实质是运算符重载。

  3、算法：读写容器对象的逻辑算法：排序、遍历、查找.......，实质是模板函数。

  4、空间配置器：分配空间。

  
  （图片来源网络，侵删）

  5、配接器：用来修饰容器、仿函数、迭代器接口，配合仿函数使用。

  6、仿函数：类似函数，通过重载()运算符来模拟函数行为的类

  • 组件间的关系

    容器通过配置器取得数据存储空间，算法通过迭代器存取容器内容，仿函数可以协助算法完成不同的策略变化，配接器可以修饰或套接仿函数。

    • vector(单向数组)

      规定只能从尾巴进行插入、尾巴进行删除，数组空间可扩容。

      可以在中间插入删除，但不建议使用。

      成员函数(迭代器相关)

      
      （图片来源网络，侵删）

      begin：返回指向元素首地址的迭代器(指向元素开头)，++操作(后)右走iterator

      end：返回指向元素末尾的迭代器，最后一个元素的下一个位置。iterator

      rbegin：逆向迭代器(指向元素末尾)，++操作(前)左走reverse_iterator

      rend：逆向迭代器(指向元素开头)reverse_iterator

      cbegin：返回一个常量迭代器，指向vector容器的第一个元素的位置。const_iterator

      cend：返回一个常量迭代器，指向容器中最后一个元素的下一个位置。const_iterator

      容量

      size：返回元素个数。

      max_size：容量

      resize：改变大小

      empty：判空

      重载

      [ ]

      at

      使用方法

      push_back：入栈。

      back：返回最后一个元素。

      pop_back：出栈，删除，无返回值。

      insert：插入

      swap：交换

      clear：清空

      sort：排序，头文件

      erase：删除迭代器指向元素/删除一段元素

      例:

      vector   arr;         //定义了一个名为arr的vector容器，arr容器中每个元素为int类型。

      vector  arr;  //定义了一个名为arr的二维容器，此容器中每个元素是一个int类型的容

      器。

      vector  arr  (5);  //定义了一个名为arr的vector容器，vector容器中共有5个元素，每个元素为int类型。

      vector  arr  (3,100);  //定义了一个名为arr的vector容器，vector容器中共有3个元素，每个元素都初始化为100。

      push_back：自动扩容

      

      [ ]：会自动扩容

      

      at：需要设置容量

      

      迭代器:指针,vector成员iterator

      

      swap：交换元素值

      

      sort：升序排序 头文件

      

      erase：删除迭代器指向元素

      

      erase：删除一段元素

      

      总结

      vector向量相当于一个数组，在内存中分配一块连续的内存空间进行存储。支持不指定vector大小的存储。

      优点：

      可以不指定大小，使用push_back、pop_back来进行动态操作。

      随机访问方便，即支持[ ]操作符与at()

      节省空间

      缺点：

      在内部进行插入、删除的效率低。

      只能在最后进行push和pop。

      当动态添加的数据超过vector默认分配的大小时要进行整体的重新分配、拷贝与释放。

      • list(双向链表)

               每一个节点都包含一个信息块Infor，一个前驱指针Pre，一个后驱指针Post。可以不分配必须的内存大小，方便进行增加和删除操作。使用的是非连续的内存空间进行存储。常使用迭代器进行操作。

        优点：

        不使用连续内存完成动态操作；

        在内部方便得进行插入和删除操作；

        可在两端进行push、pop

        缺点：

        不能在内部进行随机访问，即不支持.at()、[ ]操作符

        相对于vector占用内存多(vector只有数据块，list多了指针)

        访问list一般情况都使用迭代器。

        函数

        push_front：头插

        push_back：尾插

        pop_front：头出

        pop_back：尾出

        成员函数(迭代器相关)

        begin、end、rbegin、rend、cbegin、cend、crbegin、crend

        

        容量

        empty、size、max_size

        

        使用方法

        insert、erase、swap、resize、clear

        

        

        示例

        begin、end

        

        rbegin、rend返回reverse_iterator逆向迭代器

        

        cbegin、cend返回const_iterator常量迭代器

        

        总结

        双向链表；插入和删除在任意位置效率都很高；不能随机访问，不支持[ ]，at()；访问list一般情况都使用迭代器。

        • deque(双向队列)

          存储方式采用分块存储；deque在功能上合并了vector和list。

          优点：

          随机访问方便，即支持[ ]和vector.at()；

          在内部方便地进行插入和删除操作；

          可在两端进行push、pop。

          缺点：

          占用内存多。

          

          

          

          

          erase：删除迭代器所指位置/一段数据

          deque  mydeque;

          1、mydeque.erase(mydeque.begin()+5);   //begin()返回的是迭代器(指针)

          2、mydeque.erase(mydeque.begin(),mydeque.begin()+3);

          C++11新特性

          emplace : insert

          emplace_front : push_front

          emplace_back : push_back

          使用区分

          如果你需要高效的随即存取，而不在乎插入和删除的效率，使用vector；

          如果你需要大量的插入和删除，而不关心随机存取，则应使用list；

          如果你需要随机存取，而且关心两端数据的插入和删除，则应使用deque。

          STL序列容器：vector、deque、list

          STL关联容器：set、multiset、map、multimap

          STL迭代器：iterator

          • set(集合)

            set是一个有序的集合，其中的元素插入后就会按照某种规则进行排序，从小到大。

            内部红黑树，无值相同的元素。

            

            

            

            

            s.find：返回指向查找的指定元素的迭代器

            s.count：查找指定数据是否存在，存在则1，不存在则0

            lower_bound:函数返回的迭代器指向的元素是集合中第一个不小于给定值的元素。

            upper_bound:函数返回一个指向大于给定值的元素的迭代器，即返回指向第一个大于给定值的元素的迭代器。

            示例

            从小到大排列，且插入相同的值，只有第一次有效。

            

            count：查找指定数据是否存在，存在则1，不存在则0

            

            红黑树排列：12578

            erase：删除2-8之间的元素(包括2，不包括8)

            find：返回指向查找的指定元素的迭代器。

            

            排序：12578

            lower_bound：由于有5，则返回指向5的迭代器，无则指向5的下一位数7

            upper_bound：指向给定值7的下一位数8

            erase：删除5-8之间的数(包括5，不包括8)

            

            • map(图)

              内部红黑树

                     是一种关联容器，用于存储键值对。每个键值对称为一个元素，键和值可以是任意数据类型。Map中的元素按照键的大小自动排序，并且每个键只能在map中出现一次。

              

              

              

              

              

              map中键不能重复，重复则第二次为修改。

              map中值可以相同。

              map中会按照键从小到大排列

              

              C++官网：www.cplusecpluse.com