数据结构

不喜勿喷，纯手搓。

我宣布，我对 C++ 的开发不足 $1\%$ ！

map

map 是 STL 中的一种容器，就像桶一样。

map 的头文件：#include<map>

map 是映射，反映的是： key -- value 一种关系。 map<type1,type2> type1 是 key 的类型，type2 是 value 的类型。

map 的遍历

for(auto it=a.begin();it!=a.end();it++){
    it->first//key
    it->second//value
    (*it).first//key
    (*it).second//value
}

---

map的种类及其特性

map : $key$ 唯一，默认按照 $key$ 升序。

multimap : $key$ 不唯一，默认按照 $key$ 升序

unordered_map : $key$ 唯一，默认无序。

unordered_multimap : $key$ 不唯一，默认无序。

map的时间复杂度

unordered_map	平均时间复杂度	最坏时间复杂度
插入	$O(1)$	$O(n)$
删除
查找
访问
遍历	$O(n)$

map/multimap	时间复杂度
插入	$O(\log n)$
删除
查找
访问
遍历	$O(n)$

---

set

set 是 STL 中的一种集合，是自动去重排序的集合，没有 key，只有 value。

set 的头文件：#include<set>。

定义

set<type> s 默认升序排序。

set<type,greater<int>()> s 默认降序排序。

set<pair<int,int>> s 默认先比较 $key-first$，再比较 $value-second$。

插入

s.insert(e)

删除

s.erase(e) 删除元素 $e$,如 $e$ 不存在,则删除无效。

s.erase(it) 删除迭代器 $it$ 指向的元素。

查找

s.find(e) 找元素 $e$,找到了返回迭代器,没找到返回 s.end() 。

存在

s.count(e) 判断元素 $e$ 是否存在（返回$0/1$）。

清空

s.clear()

大小

s.size()

判空

s.empty()

遍历

for(auto it=s.begin();it!=s.end();it++){
    cout<<(*it)<<" ";
}

最值

*s.begin() 最大值；

*s.rbegin() 最小值。

---

set的种类及其特性

$All:$ 没有 $key$，只有 $value$ 。

set : $value$ 唯一，默认升序。

multiset : $value$ 不唯一，默认升序。

unordered_set : $value$ 唯一，默认无序。

unordered_multiset : $value$ 不唯一，默认无序。

set的时间复杂度

set 的时间复杂度均同 map/multimap。

vector

vector 是 STL 中的一种容器；它是可变长数组。

vector 的头文件：#include<vector>

定义

vector<type> a; 定义一个类型为 type 的一维动态数组 a，size 可以为 n。

vector<vector<type>> a; 定义一个类型为 type 的二维动态数组 a，size 可以为 n,vector<type>()

长度

a.size(); $a$ 数组的元素个数。

分配空间

a.resize(n); 给 $a$ 数组分配 $n$ 个空间。

反转

reverse(itl,itr); 反转 itl 到 itr 部分。（二者均为迭代器）

排序

sort(a.begin(),a.end()) 对 $a$ 数组从小到大排序。

sort(a.begin(),a.end(),greater<type>()) 对 $a$ 数组从大到小排序

尾插法

a.push_back(e); 在 $a$ 数组的尾部插入元素 $e$。

尾删除

a.pop_back(); 删除 $a$ 数组的尾部元素。

清空数组

a.clear(); 清空 $a$ 数组。

首尾迭代器

a.begin(); $a$ 数组的首个迭代器。

a.end(); $a$ 数组的末尾迭代器。

首尾元素

a.front(); 取 $a$ 数组的首个元素。

a.back(); 取 $a$ 数组的尾部元素。

删除

a.erase(it); $it$ 为迭代器，删除迭代器是 $it$ 的元素。

去重

a.erase(unique(a.begin(),a.end()),a.end()) 在 $a$ 数组中，仅去除相邻重复的数字。

sort(a.begin(),a.end());
a.erase(unique(a.begin(),a.end()),a.end());

对 $a$ 数组进行去重+排序。

遍历

for(int i=0;i<a.size();i++){//一维vector
    cout<<a[i]<<" ";
}

结构体vector

struct node{//定义一个结构体node
    int x,y;    
};
vector<node> a;//定义一个一维动态数组a
cin>>n;
for(int i=1;i<=n;i++){
    cin>>x>>y;
    a.push_back((node){x,y});//a的尾部插入元素
}
for(int i=0;i<a.size();i++){
    node t=a[i];
    cout<<t.x<<" "<<t.y<<endl;
}

更新记录

2026.08.07 -- 创建讨论：数据结构

文章的最后

觉得本讨论还可以的，就点个赞吧！