【算法竞赛C++STL基础】栈,链表,队列,优先队列,map,set以及迭代器的用法

发布时间:2024年01月23日

1,前知——模板函数的实现

函数模板的实现

template
T min (T a[] , int n ){

}

// 函数模板大致的书写方式,实际上就是多了个 template < class T > // 把 T 当成万能的数据结构




template <class T>
T min (T a[] , int n ){
    T minv = a[0] ;
    for(int i = 1 ; i < n ; i ++ ){
        minv = min(minv,a[i]) ; 
    }
    return minv;
}

2, hash 表

1,定义

哈希表实际上就是一种简单的映射关系,就和桶排序一样的效果,当前他一般只咉射到ASCII表的范围内,在范围外的咉射一般来说不是很好实现。

2,ASCII码表

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

记住几个重要的点 :

48 - 0 / / 9

65 - A // 25

97 - a // 25

3,咉射关系

#include <iostream>
using namespace std ;
const int N = 256 ; // 2的八次方
int hash[N] ; 
int main () {
    // hash[i] ++ ; 
    return 0 ; 
}



3,迭代器

#####在这里插入图片描述

在这里插入图片描述




4,STL关系

1,stl 的基础关系

o容器:可容纳各种数据类型的数据结构。

o迭代器:可依次存取容器中元素的东西 // 相当于数组的下标

泛化 :

一般来说容器中的迭代器为 vec.begin() , vec.end() | 数组中的迭代器为 q , q + n

迭代器中的差值一般是顺序存储的,插值个数 = 中间的个数

// 迭代器的存储 : iterator 变量名

o算法:用来操作容器中的元素的函数模板。例如,STL用sort()来对一个vector中的数据进行排序,用find()来搜索一个list中的对象。n函数本身与他们操作的数据的结构和类型无关,因此他们可以在从简单数组到高度复杂容器的任何数据结构上使用。



2,stl 的分类

1,相关分类
  1. 顺序容器

vector:后部插入/删除,直接访问
deque:前/后部插入/删除,直接访问
list:双向链表,任意位置插入/删除

  1. 关联容器

set:快速查找,无重复元素
multiset :快速查找,可有重复元素
map:一对一映射,无重复元素,基于关键字查找
multimap :一对一映射,可有重复元素,基于关键字查找

前2者合称为第一类容器

  1. 容器适配器

stack:LIFO
queue:FIFO
priority_queue:优先级高的元素先出


2,相关简介
顺序容器
  1. vector 头文件

实际上就是个动态数组。随机存取任何元素都能在常数时间完成O(1)。在尾端增删元素具有较佳的性能O(1)。

  1. deque 头文件

也是个动态数组,随机存取任何元素都能在常数时间完成(但性能次于vector,常数较大)。在两端增删元素具有较佳的性能O(1)。

  1. list 头文件

双向链表,在任何位置增删元素都能在常数时间完成O(N)。不支持随机存取。

上述三种容器称为顺序容器,是因为元素的插入位置同元素的值无关,只跟插入的时机有关。

关联容器
  1. set/multiset: 头文件

set 即集合。set中不允许相同元素,multiset中允许存在相同的元素。

  1. map/multimap: 头文件

map与set的不同在于map中存放的是成对的key/value。

并根据key对元素进行排序,可快速地根据key来检索元素

map同multimap的不同在于是否允许多个元素有相同的key值。

上述4种容器通常以平衡二叉树方式实现,插入、查找和删除的时间都是 O(logN)

适配容器
  1. stack :头文件

栈。是项的有限序列,并满足序列中被删除、检索和修改的项只能是最近插入序列的项。即按照后进先出的原则 O(1)

  1. queue :头文件

队列。插入只可以在尾部进行,删除、检索和修改只允许从头部进行。按照先进先出的原则。O(1)

  1. priority_queue :头文件

优先级队列。最高优先级元素总是第一个出列,O(logN)



3. STL 的相关函数的学习

3.1 STL函数中都含有的性质
  1. .empty() // 判断是否为空 为空 == true
  2. size() // 返回最多能放多少元素
  3. swap() // 交换两个容器中的内容


3.2 vector,deque,list 三个容器中的特殊成员函数
1,迭代器
  1. begin 返回指向容器中第一个元素的迭代器
  2. end 返回指向容器中最后一个元素后面的位置的迭代器
  3. rbegin 返回指向容器中最后一个元素的迭代器
  4. rend 返回指向容器中第一个元素前面的位置的迭代器

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传


2.顺序容器的基础函数

n.front() :返回容器中第一个元素的引用

n.back() : 返回容器中最后一个元素的引用

n.push_front() : 在容器的前面加入新元素 // list + dequeue

n.pop_front() : 在容器的前面删除新元素 // list + dequeue

n.push_back(): 在容器末尾增加新元素

n.pop_back(): 删除容器末尾的元素

3. 顺序函数的高级函数

list函数

  1. ls.unique() ; // 能够去重与前面一致的元素
  2. ls.reverse() ; // 反转
  3. ls.remove(x) // 删除与目标值x相同的所有元素


3.3 关联容器(QS: 我习惯称之为 hash类容器 )
1,Map/Multimap 的容器 (现在来说的话我们一般不会使用到multimap 和unordered_map,先留下位置以后再说)
1, 创建容器
#include <map>
map < 键值 ,>  
2.基础函数
  1. insert():插入操作的平均时间复杂度是O(log n)。

  2. operator[]:下标操作符的时间复杂度是O(log n)。如果键不存在,它会插入一个新元素,此时时间复杂度与insert()相同话说 他其实就是insert,但是一般情况下我们选用这种方式更加简单 。 //当没有的时候

  3. clear():清除所有元素的时间复杂度是O(n),其中n是map中元素的数量。

  4. count():检查键是否存在的时间复杂度是O(log n)。

  5. empty():判断map是否为空的时间复杂度是O(1)。

  6. erase():删除一个元素的时间复杂度是O(log n)。

  7. find():查找一个键的时间复杂度是O(log n)。

2.cpp

#include <iostream>
#include <map>
using namespace std ;
map <string , int > mp ; 
int main () {
    // make_pair(键值 , 内容值 ) ;
    // mp.insert(pair<,>) ; 
	mp.insert(make_pair("apple", 2)) ; 
	cout << mp["apple"] << endl ; 
	return 0 ; 
}
2,Set集合容器的常见函数
  1. 插入 (set1.insert() ) : 把当前这个名称插入进当前集合 // O(log(N))
  2. 查找有没有当前的值 : .count()

需要注意的是,这些时间复杂度是在平均情况下给出的。在某些特定情况下(例如,当map需要进行大量重新平衡时),某些操作的时间复杂度可能会更高。此外,实际的性能还会受到其他因素的影响,如内存分配和缓存效率等。



3,适配器容器 stack , queue , priority_queue

stack :

push / pop / top

queue :

push / pop / front / back

priority_queue :

push / pop / top

4. pair <>

// make_pair() 生成函数

文章来源:https://blog.csdn.net/wen030803/article/details/135759779
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。