526互联

STL模板 -- day01

发布时间 2023-09-04 18:55:47作者: BigBig飞
STL标准模板库
一、STL是Standard Template Library 的缩写
  • 中文名标准模板库，由惠普实验室提供(使用C++模板语言封装的常用的数据结构与算法)
  • STL容器所提供的都是值(value)寓意，而非引用(reference)寓意，也就是说当我们给容器中插入元素的时候，容器内部实施了拷贝动作，将我们要插入的元素再另行拷贝一份放入到容器中，而不是将原数据元素直接放进容器中。
    也就是说我们提供的元素必须能够被拷贝。
二、 STL中六大组件

  • 算法：以函数模板形式实现的常用算法，例如：swap\max\min\find\sort

  • 容器：以类模板的形式实现的常用数据结构，例如：vector\list\array\deque\map\set\multimap\multiset

  • 迭代器：泛型指针，是一种智能指针，它是容器的成员，用于帮助访问容器中的元素，使用方法类似于指针

  • 适配器（配置器\配接器）：一种用于修饰容器、仿函数、迭代器的东西，例如：stack、queue(底层借助deque实现)、priority_queue(底层借助vector)

  • 仿函数：行为类似函数的一些类，通过重载( )运算符实现效果，目的为了让算法功能更加灵活

  • 空间适配器（分配器）：为容器提供自定义内存的管理和配置，由于只是高级用户才能有改变内存分配策略的权限，因此对于一般用户而言不常用，按照默认管理方式执行

三、六大组件之间的关系

  • 容器通过空间适配器获取数据的存储空间，容器中必定存在空间适配器

  • 算法通过迭代器获取容器的元素和内存，容器必须提供迭代器，算法才能操作容器

  • 仿函数能够协助完成算法的一些策略变化

  • 适配器用于修饰容器、迭代器、仿函数

就目前而言，需要理解和使用的算法、容器(部分适配器)，迭代器

四、常用算法
  1. max \ min找出两个数据中的最大值、最小值
#include <algorithm>
cout << max(10,20) << endl;

  1. max_element \ min_element 找出[start，end)范围内的最大值、最小值

    • 注意：待比较的元素必须支持 < 运算符，且类型完全相同

  2. swap 交换两个数据

    • 注意：数据类型必须支持 = 运算符，且类型完全相同

  3. find 查找

    • 功能：顺序查找

    • start：指向待查找的第一个元素的指针、迭代器

    • end ：指向待查找的最后一个元素的下一个位置的指针、迭代器

    • val：待查找的数据

    • 返回值：

      • 找到 返回 [start,end) 范围内的第一个值为val的迭代器

      • 找不到 返回 end位置的迭代器

    iterator find(iterator start,iterator end,const TYPE& val);

  4. sort 排序

    • 功能：对 [start,end) 范围排序

    • 注意：元素要支持 < 运算符，否则后面需要提供比较回调函数

    • 默认升序，如果想要降序，也是提供比较的回调函数

    • sort 采用什么排序算法？

      • 用到了快排，但不只是快排，会根据数据状态结合上插入排序、堆排序

      • 数据量很大时采用快排进行分段排序，一旦分段后的数据量小于一个阈值(16)，为了避免快排递归调用额外，改用插入排序

      • 如果递归的层次数过深还会改用堆排序

    void sort(iterator start , iterator end);
void sort(iterator start , iterator end, StrictWeakOrdering cmp);

//cmp：降序
bool cmp(TYPE& a, TYPE& b)
{
    return a > b;
}
五、容器
  1. vector向量容器

  • 头文件 #include < vector >

  • 采用顺序结构存储数据，可以使用下标进行随机访问，有时候也叫做数组容器(C++11中增加了array容器，定长数组容器，相比于普通数组它是类类型，增加成员函数，提高安全性)

  • vector是可变长的顺序表结构，可以自动扩容，容器中的元素存储在连续内存，支持随机访问O(1)，尾插入、尾删除效率O(1)，但是在指定位置进行插入删除效率O(n)，因为要保证数据连续性

  • 构造函数

    vector(size_type num, const TYPE& val = TYPE());
// num：数组的长度
// val：初始化数据，全部初始化。不给默认 0，自建类型通过该类型的无参构造的结果来初始化
vector(input_iterator start, input_iterator end);
// 功能：使用一段[start,end)范围中的数据进行初始化向量

  • 支持的运算符

    • == != <= >= < >

      • 对容器整体比较，会对两个容器中的元素按顺序依次比较，一旦某个元素比较出结果就立即返回

      • 元素需要支持 < 运算符 才能比较

    • [ ]和普通的数组一样不会检查下标是否合法，如果访问的下标 >= size( ) 个数，可能段错误

  • 成员函数

    void assign(size_type num , const TYPE& val);
// 功能：给向量前num个数据赋值给A
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;
// 功能：返回指向第一个元素的正向常迭代器

iterator end();
// 功能：返回指向最后一个元素的下一个位置的正向迭代器
const_iterator end() const;
// 功能：返回指向最后一个元素的下一个位置的正向常迭代器

reverse_iterator rebegin();
// 功能：返回一个逆向迭代器，它指向最后一个元素
const_reverse_iterator rebegin() const;
// 功能：返回一个逆向常迭代器，它指向最后一个元素

reverse_iterator rend();
// 功能：返回指向一个逆向迭代器，它指向第一个元素的前一个位置
const_reverse_iterator end() const;
// 功能：返回指向一个逆向常迭代器，它指向第一个元素的前一个位置

注意：需要通过容器中的迭代器来操作容器的数据类型

vector <类型> v;
vector <类型>::iterator it = vegin();

在C++11中auto可以用于自动识别数据，并定义该类型的变量，可以很方便地定义迭代器类型

auto num = 10;    // num int
auto it = v.begin();    //it vector<类型>::iterator

注意：虽然迭代器在vector用处不大，但是对于其它容器，迭代器是唯一一种遍历的方式

注意：逆向迭代器也是指向一个位置，与正向迭代器的区别是，执行++操作时是往前一个元素逆向移动

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性能，因此需要在合适的时候进行reserve

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);
// 功能：交换两个向量的元素
  1. list 链表容器

  • 头文件 #include < list > 是一个功能齐全的双向链表

  • 支持的运算符

    • == != <= >= < > =

    • 也是链表之间的比较和赋值

    • 注意：链表中元素必须支持 < 运算符才能使用

  • 成员函数

    void assign(size_type num , const TYPE& val);
// 功能：向链表中赋值 num 个值为 val 的元素
void assign(input_iterator start , input_iterator end);
// 功能：向链表中赋值 [start,end)范围的元素
// 对整个链表进行了赋值，原来内容清空

TYPE& back();
const TYPE& back() const;
//功能：访问链表中的最后一个函数

TYPE& front();
const TYPE& front()const;
// 功能：访问链表中的第一个元素

iterator begin();
// 功能：返回指向的第一个元素的正向迭代器

iterator end();
// 功能：返回指向最后一个元素的下一个位置的正向迭代器

reverse_iterator rebegin();
// 功能：返回一个逆向迭代器，它指向最后一个元素

reverse_iterator rend();
// 功能：返回指向一个逆向迭代器，它指向第一个元素的前一个位置

void clear();
// 功能：清空向量中的所有元素
//       容量不变，删除所有元素，如果元素是类类型，会执行析构函数，元素数量变 0

bool empty() const;
// 功能：当向量为空，返回真

iterator erase(iterator loc);
// 功能：删除loc位置的元素，只能提供迭代器，不能直接提供地址
// 返回删除后loc的位置的迭代器

iterator erase(iterator start, iterator end);
// 功能：删除[start,end)范围的元素
// 返回删除后start位置的迭代器
// 注意：只能提供迭代器进行删除，数量-1，释放，容量不变
// 注意：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 的元素
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的元素

void resize(size_type num,const TYPE& val = TYPE());
// 功能：修改list的元素数量
// 如果num>size() 在末尾增加到num个值为val的元素
// 如果num<size() 相当于在末尾删除到num个元素

void swap(container& from);
// 功能：交换两个链表

  • 不同点：

    void merge(list &lst);
// 功能：按照顺序合并两个链表
// 如果合并前是无序的，合并后也是无序的
// 如果合并两个有序链表，合并后也有序，默认下只对升序链表合并后才有序
void merge(list &lst, BinPred compfunction);
// 如果想要进行降序，需要以回调形式提供compfunction比较方式
// 如果想要有序合并，链表元素必须支持小于号运算符，否则也需要提供比较方法才能合并
// 合并结束后 lst 的元素数量为 0 

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 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 splic(iterator pos, list& lst, tierator del);
// 功能：把lst的del位置合并到当前链表的pos位置，并且lst中del位置会删除
void splic(iterator pos, list& lst, tierator del);
// 功能：把lst的[start,end)位置合并到当前链表的pos位置，并且lst中[start,end)位置会删除

void unique();
// 功能：删除链表中的重复元素
void unique(BinPred pr);
// 功能：删除链表中满足条件的重复元素