c++ STL笔记2

た入场券 2022-06-04 10:05 206阅读 0赞

## vector 头文件< vector> ##

自动调节长短的数组
    动态数组！！！。动态增容
    元素在内存连续存放。
    随机存取任何元素都能在常数时间完成。
    在尾端增删元素具有较佳的性能(大部分情况下是常数时间）。
    了解时间复杂度是怎么样的！！！！！！！！！！！！！
    迭代器是随机访问的迭代器
        支持通过下表随机访问每一个元素 常数级别的访问
        尾部添加元素速度很快
        中间插入很慢 本身实现就是一个数组 跟数组的大小有关 后面的元素需要移动
        所有的stl算法都可以作用于vector

vector() //无参构造函数 空
        vector(n)
        vector(int n,const T& val)
        vextor(iterator first,iterator last)  //传递迭代器来初始   化 用区间的内容来初始化 左闭右开的初始化   这里的迭代器就可以是指针 其实就是指针 也是指针底层实现的
        void pop_back() //删除末尾元素
        voi push_back(const T& val) //将val添加到容器末尾
        int size()//返回容器的元素个数
        T& font() //返回第一个元素的引用
        T& back() //返回最后一个元素的引用
        v.at(int num) //访问第几个元素从0开始  会做检查是否超过容量 安全
        v.insert(迭代器，被插入的值)  //查进去了 元素加一
        vector<元素类型> //就是一个模板
        //随机迭代器 迭代器相减操作 结果是两者位置之间元素的个数
    
        二位动态数组的定义： vector< vector<int> > v(3);  //嵌套定义
        //v有3个参数 每个参数都是vector<int> 容器

## deque头文件< deque> ##

双向 队列。
    所以能用在vector的操作都可以用在deque上
    还有push_front 
    pop_front 操作  
    元素在内存连续存放。
    随机存取任何元素都能在常数时间完成(但次于vector)。

## 在两端增删元素具有较佳的性能(大部分情况下是常数时间）。 ##

## list 头文件< list> ##

双向 链表。
    插入删除常数时间
    不可随机访问 没有下标索引
    所有顺序容器的函数都可以使用
        这里就是指一些算法 排序算法 查找算法等等
    元素在内存不连续存放。
    在任何位置增删元素都能在常数时间完成。 前提是找到了这个位置
    不支持随机存取。
    
    成员函数：
    push_front 在链表最前面插入
    pust_back  在链表的最后插入
    pop_front   删除链表最前面的元素
    pop_back    删除链表最后的元素
    sort  和stl的sort函数不一样 不支持随机访问 所以这个是自带的排序函数 
    remove  删除和指定值val一样的元素  注意和erase的区别 这个是根据位置删除 
    unique  删除所有和前一个元素一样的元素  排序之后用有意思
    merge   合并两个链表并且清空被合并的链表  将被插入的list元素合并在末尾 顺序不发生改变
    reverse  颠倒链表 
    splice(迭代器1，链表2，迭代器2，迭代器3)      在迭代器1前插入[迭代器2，迭代器3)区间的元素  并且在另一个链表里删除被插入的元素
    find(参数)算法 返回的是一个迭代器 
    
    
    
    list 不支持随机访问  
    使用自己的sort函数排序
    sort() 无参数的版本 是由小到大排序
    sort(compare) compare函数可以自己定义 
    只能支持双向迭代器
    不支持比大小 比较运算符 
    []运算符也不支持
    随机移动也不可以 list的迭代器+2 是不行的
    因为 双向迭代器只能找到上一个和下一个 不可以跳跃

--------------------

## 关联容器 ##

插入任何元素都按照相应的规则来确定其位置 目的就是为了查找  
**set multiset map multimap**  
特点就是内部都是从小到大排好序的  
什么是小什么是大是可以自己定义的！！  
除了容器所共有的函数以外还有：  
find：查找等于某个值的元素 ！！相等的概念 x小于y不成立 且y小于x也不成立的时候就是相等 这和一般意义的相等有所不同  
lower\_bound 查找某个下界  
upper\_bound 查找某个上界  
equal\_range 同时查找上界和下界  
count 计算等于某个值得元素的个数 这里的相等 ！！注意  
insert 插入一个元素或一个区间

## multiset头文件< set> ##

template<class key,class pred=less<key>,class A = allocator<key>>
         class multiset{....}
    
         //pred 的类型决定了multiset中的元素 对于一个比一个小的定义 
         //当multiset 运行的时候比较两个元素大小的时候 就是生成一个pred类型的变量op 函数对象 
         //再去判定表达式op(x,y)的返回值 若为true 则x比y小
         //pred的缺省类型是less<key>
    
        //less 模板的定义 
        template <class T>
        struct less:.....
        {
            bool operator()(const T& x,const T& y) const
            {
                return x<y;
            }
        };

multiset的成员函数  
iterator find(constT & val);  
在容器中查找值为val的元素，返回其迭代器。如果找不到，返回end()。  
iterator insert(constT & val); 将val插入到容器中并返回其迭代器。

void insert( iterator first,iteratorlast); 将区间[first,last)插入容器。 
    int count(constT & val);统计有多少个元素的值和val相等。
    
    iterator lower_bound(constT & val);
    查找一个最大的位置it,使得[begin(),it) 中所有的元素都比val小。
    iterator upper_bound(constT & val);
    查找一个最小的位置it,使得[it,end()) 中所有的元素都比val大。
    除了中间两个其他的时间复杂度都是log n 的
    
    pair<iterator,iterator> equal_range(constT & val);
    同时求得lower_bound和upper_bound。

## pair 模板 ##

就是说pair类型的对象可以接受两个返回值 并且赋予其成员变量first 和 second
    template<class _T1, class _T2>
    struct pair                      struct 声明的pair 所有的成员都是公有的
    {
    typedef _T1 first_type;
    typedef _T2 second_type;
    _T1 first;
    _T2 second;
    pair(): first(), second() { }
    
    pair(const _T1& __a, const _T2& __b)
    : first(__a), second(__b) { }
    
    template<class _U1, class _U2>
    pair(const pair<_U1, _U2>& __p)
    : first(__p.first), second(__p.second) { }
    };

iterator erase(iterator it);

## 小于号< 在这里很重要！！！！multiset 的第二个参数 默认是less 所以如果用的是默认的比价大小的方式 就必须对multiset里存放的对象的操作符<重载 ！！！！ ##

## set 头文件也是< set> ##

和multiset的差别就是 set里面是不能有重复元素的！！！！
    插入set里已有的元素 将忽略插入
    什么是重复？！ 有意思 不是说一般意义的相等 还是那个 两个都不相互小于
    一定要记得 set multiset 的模板参数有三个 第一个是指里面存放的对象类型 第二个是指排序的方式 有默认值可以传入函数指针也可以传入 函数对象 第三个参数不重要 一般不关注
    set的insert单个参数的定义
    pair<iterator,bool> insert (const value_type& val);
    set的多了一个bool返回值 用于判断是否插入成功
    multiset的单个单数insert定义
    iterator insert (const value_type& val);

## 注意区别 ##

map和multimap里放的东西一定是 pair 模板类的对象！！

对象一定是有first和second两个成员变量  
都是按照first成员变量将对象从小到大排序的

multimap  
template

## 添加数据和查询数据时间复杂度都是log n 的！！！！很快 ##

map  
不能有两个及以上的存储的对象的first成员变量是相同的！！！！  
一个和multimap最大的不同就是 map是有\[\]成员函数的！！！  
因为map里没有关键字重复的对象 所以可以通过关键字去查找对应的值  
map实例化的对象\[key\]  
返回的就是对应关键字的值也就是对应的second成员变量的 ！！引用！！！  
若没有该关键字 则会往里插入一个关键字为key的元素 其值为无参构造函数初始化 并返回其值得引用

--------------------

**容器适配器：**  
特殊的容器  
可以用某种顺序容器实现的 让已有的顺序容器以栈或者队列的方式工作

## stack：栈头文件< stack> ##

后进先出的方式  
只能插入删除访问栈顶的元素  
可以用vector list deque实现  
默认deque 实现  
vector和deque实现性能好于list实现

template

## queue：队列头文件 < queue> ##

先进先出  
可以用list deque实现  
缺省的情况下用deque实现  
template

## pop，top则都是发生在对头 这样也符合队列先进先出 ##

## priority\_queue 优先级队列头文件< queue> ##

最高优先级的元素总是第一个出队列  
可以通过vector和deque实现  
默认vector实现  
通常用堆排序技术实现保证最大的元素总是在最前面  
执行pop，top都是对最大的元素进行操作 注意优先级队列是不允许修改对头元素的！！！！  
第三个参数 默认用less比较  
适用于在一堆元素中取最大值的情况

通常包含3个成员函数：  
push：添加一个元素  
top:返回栈顶或者队列头部的元素的引用  
pop：删除一个元素

！！！容器适配器上没有迭代器！！！

## 那么 STL里所有的查找，排序，变序算法都不适用于容器适配器 ##

--------------------

顺序容器和关联容器中都有的成员函数

begin返回指向容器中第一个元素的迭代器
    end返回指向容器中最后一个元素后面的位置的迭代器
    rbegin返回指向容器中最后一个元素的迭代器
    rend 返回指向容器中第一个元素前面的位置的迭代器
    erase 从容器中删除一个或几个元素
    clear从容器中删除所有元素
    
    顺序容器的常用成员函数
    front:返回容器中第一个元素的引用
    back: 返回容器中最后一个元素的引用
    push_back : 在容器末尾增加新元素
    pop_back : 删除容器末尾的元素
    erase :删除迭代器指向的元素(可能会使该迭代器失效），或删除一个区间，返回被删除元素后面的那个元素的迭代器

--------------------

定义一个容器类的迭代器的方法可以是：  
前面的容器作用域声明不可以忘记  
容器类名::iterator 变量名;  
或：  
容器类名::const\_iterator 变量名;  
访问一个迭代器指向的元素：

*  迭代器变量名 表示取出相应迭代器指向的对象的数据值

**双向迭代器**  
若p和p1都是双向迭代器，则可对p、p1可进行以下操作：  
\++p, p++使p指向容器中下一个元素  
–p, p–使p指向容器中上一个元素  
\* p 取p指向的元素 切记与指针的使用类似  
p = p1赋值  
p == p1 , p!= p1判断是否相等、不等

**随机访问迭代器**  
若p和p1都是随机访问迭代器，则可对p、p1可进行以下操作：  
双向迭代器的所有操作  
p += i将p向后移动i个元素  
p -= i将p向向前移动i个元素  
p + i值为: 指向p 后面的第i个元素的迭代器  
p -i值为: 指向p 前面的第i个元素的迭代器  
p\[i\]值为: p后面的第i个元素的引用  
p < p1, p <= p1, p > p1, p>= p1  
这里小于的含义 就是 p所指向的元素在p1所指向的元素的前面  
容器容器上的迭代器类别

vector随机访问
    deque随机访问
    list 双向
    set/multiset双向
    map/multimap双向
    stack不支持迭代器
    queue不支持迭代器
    priority_queue不支持迭代器

## STL 查找 提到区间都是左闭右开的！！！ ##

STL中“相等”的概念  
有时，“x和y相等”等价于“x==y为真”  
例：在未排序的区间上进行的算法，如顺序查找find  
……  
有时“x和y相等”等价于“x小于y和y小于x同时为假”  
例：  
有序区间算法，如binary\_search  
关联容器自身的成员函数find  
……

## STL算法 头文件 < algorithm> ##

不变序列算法  
变值算法  
删除算法  
变序算法  
排序算法  
有序区间算法  
数值算法

算法 大多数都有两个版本  
大多重载的算法都是有两个版本的  
•用“==” 判断元素是否相等, 或用“<”来比较大小  
•多出一个类型参数“Pred” 和函数形参“Pred op” :  
通过表达式“op(x,y)” 的返回值: ture/false  
判断x是否“等于” y，或者x是否“小于” y  
如下面的有两个版本的min\_element: 返回值是一个迭代器 参数是两个迭代器 组成一个左闭右开的区间  
iterator min\_element(iterator first, iterator last); 这个版本是通过 小于号 来比较大小  
iterator min\_element(iterator first, iterator last, Pred op); 这个是通过自定义的比较方式来比较大小 可以传入函数对象或者函数名字

不变序列算法