day01

STL标准模板库     STL中文名标准模板库，有惠普实验室(使用C++模板语言封装的常用的数据结构与算法)     STL中有六大组件：         *算法：以函数模板形式实现的常用算法，例如：swap、max、min、find、sort         *容器：以类模板的形式实现常用数据结构，例如vector(顺序表)、list、array、deque、map、set、multimap、multiset         *迭代器：泛型指针，是一种智能指针，它是容器的成员，用于帮助访问容器中的元素，使用方法类似于指针         适配器(配置器、配接器):一种用于修饰容器、仿函数、迭代器的东西，例如stack、queue(底层借助deque)、priority_queue(底层借助vector实现)         仿函数：行为类似函数的类，通过重载()运算符实现效果，目的是为了让算法功能更加灵活         空间适配器(分配器)：为容器提供自定义内存的管理和配置，由于只是高级用户才能有改变策略分配内存的权限，因此对于一般用户而言不常用，按照默认管理方式执行
        六大组件之间的关系：             容器通过空间适配器获取数据的存储空间，(容器中必定存在空间适配器)             *算法通过迭代器获取容器的元素和内存，容器必须提供迭代器，算法才能操作容器             仿函数协助完成算法的策略变化             适配器用于修饰容器、迭代器、仿函数         就目前而言，需要理解使用的：算法、容器(部分适配器)、迭代器         学习STL的三部曲：             能用、明理(了解泛型编程技术内涵、STL的底层源码)、能扩展         侯捷 STL
一、常用算法     1、max、min     找出两个数据中的最大、最小值     2、max_element、min_element     找出[strat,end)范围内的最大、最小值     注意：待比较的元素必须支持 < 运算符，且类型完全相同
    3、swap     交换两个数据，数据类型必须支持 = 运算符     4、iterator find(iterator start, iterator end, const TYPE& val);     功能：顺序查找     start：指向待查找的第一个元素的指针、迭代器类型     end：指向待查找的最后一个元素的下一个位置的指针、迭代器     val：待查找的数据     返回值：         找到[start,end)范围内的第一个值为val的迭代器         找不到返回 end位置的迭代器     5、sort         void sort( iterator start, iterator end );         void sort( iterator start, iterator end, StrictWeakOrdering cmp );         功能：对[start,end)范围排序         注意：元素要支持 < 运算符，否则后面需要提供比较回调函数         注意：默认升序，如果想要降序，也是提供比较的回调函数         cmp:         bool cmp(TYPE& a,TYPE& b)         {             return a>b;         }         sort采用什么排序算法？             用到了快排，但不只是快排，会根据数据状态结合上插入排序、堆排序             数据流很大时采用快排进行分段排序，一旦分段后的数据量小于一个阈值(16)，为了避免快排递归调用额外消耗，改用插入排序             如果递归层次数过深还会改用堆排序
二、vector  向量容器(变长)     #include <vector>     采用顺序结构存储数据，可以使用下标进行随机访问，有时候也叫数组容器(C++11中增加了array的容器(定长数组容器)，相比普通数组它是类类型，增加了成员函数，提高安全性)     vector是可变长的顺序表结构，可以自动扩容，容器中的元素存储在连续的内存，支持随机访问，尾插入、尾删除效率 O(1)，但是在指定位置进行插入、删除效率 O(n)，因为要保证数据的连续性
    构造函数：         vector( size_type num, const TYPE& val = TYPE() );             num：数组的长度             val：初始化数据，全部赋为val，不给默认0，自建类型通过该类型的无参构造的结果来初始化         vector( input_iterator start, input_iterator end );         功能：使用一段范围[start,end)中的数据进行初始化向量
        支持的运算符             ==, !=, <=, >=, <, >,   对容器整体比较，会对两个容器中的元素按顺序依次比较，一旦某个元素比较出结果就立即结束             元素需要支持 < 运算符 才能比较             =             [] 跟普通数组一样，不会检查下标是否合法，如果访问的下标>=size()的个数,可能段错误
    成员函数：         void assign( size_type num, const TYPE& val );         功能：给向量的前num个元素赋值为val         void assign( input_iterator start, input_iterator end );         功能：使用[start,end)的数据给向量赋值
        TYPE& at( size_type loc );         const TYPE& at( size_type loc ) const;         功能：访问向量loc下标，功能相当于[]，当loc越界时，at成员函数会抛异常，相比[]更加安全
        TYPE& back();         const TYPE& back() const;         功能：访问向量中的最后一个元素
        TYPE& front();         const TYPE& front() const;         功能：访问向量中的第一个元素
        iterator begin();         功能：返回指向第一个元素的正向迭代器         const_iterator begin() const;         功能：返回指向第一个元素的正向常迭代器                 使用：vector<int>::iterator it = v.begin();
        注意：需要通过容器中的迭代器来操作容器的数据和内存             vector<类型> v;             vector<类型>::iterator it = v.begin();             在C++11中auto可以用于自动识别数据类型，并定义该类型的变量，可以很方便地定义迭代器类型             auto num = 10;          //num int             auto it = v.begin();    //it vector<类型>::iterator it = v.begin();         注意：虽然迭代器在vector用处不大，但是对于其他容器，迭代器是唯一一种遍历的方式
        iterator end();         功能：返回指向最后一个元素的下一个位置的正向迭代器         const_iterator end() const;         功能：返回指向最后一个元素的下一个位置的正向常迭代器
        reverse_iterator rbegin();         功能：返回一个逆向迭代器，它指向最后一个元素         const_reverse_iterator rbegin() const;         功能：返回一个逆向常迭代器，它指向最后一个元素
        reverse_iterator rend();         功能：返回一个逆向迭代器，它指向第一个元素的前一个位置         const_reverse_iterator rend() const;         功能：返回一个逆向常迭代器，它指向第一个元素的前一个位置
        注意：你想迭代器也是指向一个位置，与正向迭代器的区别是，执行++操作时是往前一个元素逆向移动
        size_type capacity() const;         功能：获取该向量的容量
        void clear();         功能：清空向量中的所有元素             容量不变，从中删除释放所有元素，如果元素是类类型，会执行析构函数，元素数量变0
        bool empty() const;         功能:当向量为空返回真
        iterator erase( iterator loc );         功能：删除loc位置的元素         返回删除后loc的位置的迭代器         iterator erase( iterator start, iterator end );         功能：删除[start,end)范围的元素         返回删除后start的位置的迭代器         注意：只能提供迭代器进行删除，数量-1，释放，容量不变
        iterator insert( iterator loc, const TYPE& val );         功能：在loc位置插入值为val的元素         返回值：获取loc的迭代器，loc会随着函数结束有可能发送变化，如果想要连续往同一个loc位置插入，需要宠幸接收         void insert( iterator loc, size_type num, const TYPE& val );         功能：在loc位置插入num个值为val的元素         void insert( iterator loc, input_iterator start, input_iterator end );         功能：在loc位置插入一组[start,end)元素
        注意：如果插入、添加数据时、向量刚好没有空余位置时，向量会进行自动扩容，一般在原容量基础上翻倍
        size_type max_size() const;         功能：用于计算理论上向量能存储的最大元素数量，受到元素的类型影响
        void pop_back();         功能：在末尾位置删除元素         void push_back( const TYPE& val );         功能：在末尾位置添加一个值为val的元素         效率：O(1)
        void reserve( size_type size );         功能：修改向量的容量为size，只能比原来容量大才能修改         可以进行预分配，从而提高效率，减少扩容次数(耗时)         但是意味着内存可能会闲置         每次扩容可能会拷贝原向量中的所有对象进行拷贝构造，还要把原向量中的对象进行析构，如果频繁地扩容会严重影响vector性能，因此需要在合适的时候进行预分配
        shrink_to_fit() 取消闲置的内存
        void resize( size_type num, const TYPE& val = TYPE() );         功能：修改向量的元素数量             如果num>size() 在末尾增加到num个值为val元素             如果num<size() 相当于在末尾删除到num个元素
        size_type size() const;         功能：获取向量的元素数量
        void swap( container& from );         功能：交换两个向量的元素
三、链表容器 List     #include <list>     是一个功能齐全的双向链表     支持的运算符：          ==, !=, <=, >=, <, >, =          也是链表与链表之间的比较和赋值          注意：链表中元素必须支持 < 运算符才能使用
    void assign( size_type num, const TYPE& val );     功能：向链表中赋值num个值为val的元素     void assign( input_iterator start, input_iterator end );     功能：向链表中赋值[start,end)范围的元素     对整个链表进行赋值
    back    访问第一个     front   访问最后一个元素     begin   返回第一个位置的正向迭代器     end     返回最后一个位置的下一个位置的正向迭代器     rbegin  返回最有一个位置的逆向迭代器     rend    返回第一个位置的前一个位置的逆向迭代器     clear   清空链表中的元素     empty   判断是否为空链表     max_size    理论上最多能存储的个数
    iterator erase( iterator loc );         删除位置loc的元素，只能提供迭代器对象，不能直接提供地址     iterator erase( iterator start, iterator end );    
    注意：list的迭代器不允许 it+n it+=n语法，因为list是链式结构不支持随机访问         但是 it++ ++it 是通过结点的next找下一个结点 是允许的
    iterator insert( iterator loc, const TYPE& val );     功能：在loc位置插入值为val的元素     void insert( iterator loc, size_type num, const TYPE& val );     功能：在loc位置插入num个值为val的元素     template<TYPE> void insert( iterator loc, input_iterator start,input_iterator end );     功能：在loc位置插入一组[start,end)范围的元素
    void merge( list &lst );     功能：按照顺序合并两个链表         1、如果合并前是无序的，则合并后也是无序         2、如果合并两个有序链表，合并后也有序             默认下只对升序链表合并后才是升序有序     void merge( list &lst, BinPred compfunction );         如果想要进行降序排序，需要以回调形式提供compfunction比较方法         想要有序合并，链表元素必须支持 < 运算符，否则也需要提比较方法才能合并         合并结束后 lst的元素数量为0
    pop_front       头删除     push_front      头添加
    void remove(const TYPE &val);     功能：删除链表中值为val的所有元素     void remove_if( UnPred pr);     功能：删除符合条件pr的所有元素     pr         bool cmp(const TYPE& val)         {             return val >= left && val <=right;             // 符合[left,right]范围的数据删除         }
    void resize( size_type num, const TYPE& val = TYPE() );     功能：修改向量的元素数量         如果num>size() 在末尾增加到num个值为val元素         如果num<size() 相当于在末尾删除到num个元素
    void sort();     功能：对list进行升序排序，要求元素支持 < 运算符     void sort( BinPred p );     功能：对list进行排序，可以通过提供二元谓词比较 > 运算符比较进行降序排序，如果元素不支持 < 运算符，也需要提供比较回调函数         p:             bool cmp(TYPE& a,TYPE& b)             {                 return a > b;//降序             }
    void splice( iterator pos, list& lst );     功能：把链表lst合并到当前链表的pos指定位置，结束后lst数量为0     void splice( iterator pos, list& lst, iterator del );     功能：把lst的del位置开始合并到当前链表的pos位置，并且lst中del位置会删除
    void splice( iterator pos, list& lst, iterator start, iterator end );     功能：把lst的[strat,end)位置合并到当前链表的pos位置，并且lst中[start,end)位置会删除
    void swap( container& from);     功能：交换两个链表
    void unique();     功能：删除链表中的重复元素     void unique( BinPred pr);     功能：删除链表中满足条件pr的重复元素