STL的基本概念

  1. 三大核心部分——容器、算法、迭代器
  2. 容器:可容纳各种数据类型的数据结构
  3. 迭代器:可依次存取容器中的元素,遍历容器中数据的对象,他可以按照预先定义的顺序在某些容器中的成员间移动,对普通的一维数组。向量、双端队列、列表来说,迭代器就是一种指针迭代器是STL的一个关键部分,因为它将算法和容器连在一起
  4. 算法:用来操作容器中的元素的函数模板,处理容器里面数据的方法和操作。
  5. 函数本身与他们操作的数据的结构和类型无关
容器

可容纳各种数据类型(基本类型的变量、对象等)的数据结构。例如,数组、堆、栈、队列、链表或二叉树(不过这些都不是STL标准容器)

  1. 顺序容器:
  • vector:后部插入/删除,直接访问
  • deque:前/后部插入/删除,直接访问
  • list:双向链表,任意位置插入/删除
  1. 关联容器
  • set:快速查找,无重复元素
  • multiset:快速查找,可有重复元素
  • map:一对一映射,无重复元素,基于关键字查找
  • multimap:一对一映射,可有重复元素,基于关键字查找

前二者合为第一类容器

  1. 容器适配器
  • stack:LIFO
  • queue:FIFO
  • priority_queue:优先级高的元素先出
  1. 容器的公有成员函数
  • 相当于按词典顺序比较两个容器大小的运算符:=, < , <= , > , >=, == , !=
  • empty : 判断容器中是否有元素
  • max_size: 容器中最多能装多少元素
  • size: 容器中元素个数
  • swap: 交换两个容器的内容
迭代器
  1. 定义:

    • 用于指向第一类容器中的元素。有const 和非 const两种

    • 通过迭代器可以读取它指向的元素,通过非const迭代器还能修改其指向的元素。迭代器用法和指针类似。

    • 定义一个容器类的迭代器的方法可以是:

      容器类名::iterator 变量名
      或者:
      容器类名::const_iterator 变量名
      
    • 访问一个迭代器指向的元素——*+迭代器变量名

向量(vector容器类)
  1. #include ,vector是一种动态数组,是基本数组的类模板。
  2. 支持随机访问迭代器,所有STL算法都能对vector操作
  3. 随机访问时间为常数。在尾部添加速度很快,在中间插入慢
关联容器
  1. set, multiset, map, multimap
    • 内部元素有序排列,新元素插入的位置取决于它的值,查找速度快
    • map关联数组:元素通过键来存储和读取
    • set大小可变的集合,支持通过键实现的快速读取
    • multimap支持同一个键多次出现的map类型
  2. 与顺序容器的主要区别:
    • 关联容器是通过键(key)存储和读取元素的
    • 而顺序容器则通过元素在容器中的位置顺序存储和访问元素。
Set
  1. Set的功能:
    • 表示集合
    • 支持插入,删除,查找,首元素,末元素等操作,就像一个集合一样
    • 所有的操作都是在严格logn时间之内完成,效率非常高.对于动态维护可以说是很理想的选择。
    • Set是一个有序的容器,里面的元素都是排好序的
  2. Set操作
    • base.begin() 求第1个元素,返回迭代器,由于是顺序的容器,所以第1个元素就是最小的元素
    • base.end() 求容器的末尾,表示容器到了末尾,返回迭代器,这个迭代器里没有元素,专门表示末尾
    • base.rbegin() 求倒数第1个元素,即最大元素,返回迭代器,(注意:这个迭代器是逆向迭代器和base.begin()的返回值类型不同)
    • base.size() 求容器里元素的数量,返回整数
    • base.empty() 判断容器是否是空,空返回true,否则返回false
    • base.find( a ) 查找元素a,如果查到了,返回指向a的迭代器,否则返回容器末尾迭代器,即base.end()
    • base.count( a ) 查找元素a的数量,返回整数
Map
  1. 可以用pairs[key] 访形式问map中的元素
    • pairs 为map容器名,key为关键字的值
    • 该表达式返回的是对关键值为key的元素的值的引用
    • 如果没有关键字为key的元素,则会往pairs里插入一个关键字为key的元素,并返回其值的引用
  2. 查找函数——find:来定位数据出现位置,它返回的一个迭代器,当数据出现时,它返回数据所在位置的迭代器,如果map中没有要查找的数据,它返回的迭代器等于end函数返回的迭代器。
  3. 删除函数——erase:int n = Pairs.erase(50);//用关键字删除,如果删除了会返回1,否则返回0。
算法
  1. #inlcude <algorithm>引入头文件
  2. STL中算法的**大部分都不作为某些特定容器类的成员函数,他们是泛型的,每个算法都有处理大量不同容器类中数据的使用。**值得注意的是,STL中的算法大多有多种版本,用户可以依照具体的情况选择合适版本
  3. 在STL的泛型算法中有4类基本的算法:
    • 变序型队列算法:可以改变容器内的数据
    • 非变序型队列算法:处理容器内的数据而不改变他们
    • 排序值算法:包涵对容器中的值进行排序和合并的算法,还有二叉搜索算法、通用数值算法。(注:STL的算法并不只是针对STL容器,对一般容器也是适用的。)
    • 变序型队列算法:又叫可修改的序列算法。这类算法有复制(copy)算法、交换(swap)算法、替代(replace)算法、删除(clear)算法,移动(remove)算法、翻转(reverse)算法等等。这些算法可以改变容器中的数据(数据值和值在容器中的位置)
排序和查找算法
  1. Sort:

    template<class RanIt>

    void sort(RanIt first, RanIt last);

  2. find

    template<class InIt, class T>

    InIt find(InIt first, InIt last, const T& val);

  3. binary_search 折半查找,要求容器已经有序

    template<class FwdIt, class T>

    bool binary_search(FwdIt first, FwdIt last, const T& val);

  4. sort 实际上是快速排序,时间复杂度 O(n*log(n));

    平均性能最优。但是最坏的情况下,性能可能非常差

  5. 如果要保证**“最坏情况下”**的性能,那么可以使用stable_sort

    • stable_sort 实际上是归并排序(将两个已经排序的序列合并成一个序列),特点是能保持相等元素之间的先后次序
    • 在有足够存储空间的情况下,复杂度为 n * log(n),否则复杂度为 n *log(n) * log(n)
    • stable_sort 用法和 sort相同:
    • 排序算法要求随机存取迭代器的支持,所以list 不能使用排序算法,要使用list::sort
Logo

权威|前沿|技术|干货|国内首个API全生命周期开发者社区

更多推荐