set和map

# 铺垫知识

STL中包含序列式容器和关联式容器：

**序列式容器：**vector，list，deque
关联式容器：set、map、unordered_set、unordered_map set和map是树形结构（有序），底层由红黑树实现，时间复杂度为O(logn);unordered_set、unordered_map是哈希结构（无序），由哈希表实现,时间复杂度为O(1)。

pair键值对： 定义：

template <class T1, class T2>
struct pair {
	typedef T1 first_type;
	typedef T2 second_type;
	T1 first;
	T2 second;
	pair() : first(T1()), second(T2())
	{}
	pair(const T1& a, const T2& b) : first(a), second(b)
	{}
};

1
2
3
4
5
6
7
8
9
10
11
12

使用：

#include <utility>
int main() {
    int x = 10;
    string y = "Hello";
    pair<int, string> myPair = make_pair(x, y);
    // 现在myPair是一个包含{(10, "Hello")}的pair对象
    return 0;
}

1
2
3
4
5
6
7
8

# set

底层实现：通常基于红黑树，保证键的排序。
特性：不允许键值重复，所有元素自动按照升序排列,因此可以用来去重。
访问速度：通过键访问元素的时间复杂度为O(logn)，因为内部是平衡二叉搜索树结构。
set中的元素不能被修改，因为set在底层是用二叉搜索树来实现的，若是对二叉搜索树当中某个结点的值进行了修改，那么这棵树将不再是二叉搜索树。

insert

pair<iterator,bool> insert (const value_type& val);
iterator insert (iterator position, const value_type& val);

erase

erase (iterator position);
size_type erase (const value_type& val);
void erase (iterator first, iterator last);

# multiset

multiset容器与set容器的底层实现一样，都是平衡搜索树（红黑树），multiset容器和set容器的唯一区别就是，multiset允许键值冗余，即multiset容器当中存储的元素是可以重复的。

# map

map所有元素都是pair
pair由两个部分组成：key（键值），索引作用，value（实值），可以根据key快速找到value
所有元素会根据元素的键值自动排序，使用map的迭代器遍历map中的元素，可以得到有序序列
map容器中元素的键值key不能被修改，但是元素的值value可以被修改，因为map底层的二叉搜索树是根据每个元素的键值key进行构建的，而不是值value
map容器支持下标访问符，即在[]中放入key，就可以找到与key对应的value
map在底层是用平衡搜索树（红黑树）实现的，所以在map当中查找某个元素的时间复杂度为O(logN)

insert

pair<iterator,bool> insert (const value_type& val);

参数：pair对组返回值：

若待插入元素的键值key在map当中不存在，则insert函数插入成功，并返回插入后元素的迭代器和true
若待插入元素的键值key在map当中已经存在，则insert函数插入失败，并返回map当中键值为key的元素的迭代器和false

find

iterator find (const key_type& k);

若找到了，则返回对应元素的迭代器，若未找到，则返回容器中map::end()

erase

void erase (iterator position);
size_type erase (const key_type& k);

operator[]

mapped_type& operator[] (const key_type& k);

(*((this->insert(make_pair(k, mapped_type()))).first)).second

调用insert函数插入键值对。
拿出从insert函数获取到的迭代器。
返回该迭代器位置元素的值value。

mapped_type& operator[] (const key_type& k) {
	//1、调用insert函数插入键值对
	pair<iterator, bool> ret = insert(make_pair(k, mapped_type()));
	//2、拿出从insert函数获取到的迭代器
	iterator it = ret.first;
	//3、返回该迭代器位置元素的值value
	return it->second;
}

1
2
3
4
5
6
7
8

# multimap

multimap允许键值冗余，即multimap容器当中存储的元素是可以重复的。

# unordered_set

基于哈希表（Hash Table），内部采用链表解决哈希冲突。
不允许键值重复，但不保证元素的排序顺序。

# unordered_map

键值对存储无序，键也是唯一的，不允许两个相同的键。
不保证迭代器遍历时元素的顺序，而是依赖于哈希函数和哈希桶的布局。

上次更新: 2025/02/07, 18:31:39

← 多态 bitset→