当前位置：首页 > article >正文

C++STL之 set 和 map：介绍及基本使用

article 2024/11/7 18:31:15

一、关联式容器

关联式容器

键值对

树形结构的关联式容器

二、set

set的介绍

set的使用

insert插入

编辑

拷贝构造

erase删除

find查找

三、map

map的介绍

map的使用

operator[]运算符重载

operator[]小结

map的总结

四、multiset 和 multimap

multiset的介绍和使用

multimap的介绍和使用

五、例题

前K个高频单词

两个数组的交集I

一、关联式容器

关联式容器

我们已经接触过STL中的部分容器，比如：vector、list、deque、 forward_list(C++11)等，这些容器统称为序列式容器，因为其底层为线性序列的数据结构，里面存储的是元素本身。

那什么是关联式容器？它与序列式容器有什么区别？

关联式容器也是用来存储数据的，与序列式容器不同的是，其里面存储的是结构的键值对，在数据检索时比序列式容器效率更高。

键值对

用来表示具有一一对应关系的一种结构，该结构中一般只包含两个成员变量 key 和 value，key 代表键值，value 表示与 key 对应的信息。

比如：在一个商店的库存管理系统中，商品编号可以作为键，商品的库存数量作为值。比如，商品编号 “001” 是键，库存数量 “100” 是值，键值对（“001”，“100”）表示编号为 001 的商品有 100 件库存。当有商品销售或进货时，通过商品编号（键）来更新对应的库存数量（值）。

树形结构的关联式容器

树型结构的关联式容器主要有四种：map、set、multimap、multiset。这四种容器的共同点是：使用平衡搜索树(即红黑树)作为其底层结构，容器中的元素是一个有序的序列。

在搜索时候分两种：一种是 key 的模型，一种是 key-value 模型。

set 就是 key 的模型， map 就是 key-value 的模型。

二、set

set的介绍

一、存储特点

set是一种按照特定次序存储元素的容器，其中每个元素的 “值” 同时也作为它的标识（即value就是key）。每个元素的值必须是唯一的，这意味着不能有重复的元素存在于set中。

二、元素特性

虽然可以从set中插入或删除元素，但元素在容器中不能被修改，因为元素总是被视为常量。这是为了保证容器中元素的唯一性和有序性不被破坏。

三、内部排序

在内部，set中的元素按照其内部比较对象所指示的特定严格弱排序准则进行排序。通常默认按照小于来比较元素。

四、性能与结构

与unordered_set相比，通过key访问单个元素时，set的速度通常较慢。然而，set允许根据顺序对子集进行直接迭代，因为其元素是有序的。
set在底层是用二叉搜索树（红黑树）实现的，这使得插入、删除和查找操作的时间复杂度为㏒(n)。

五、与map的区别及注意事项

与map/multimap不同，map/multimap中存储的是真正的键值对<key, value>，而set中虽然只放value，但在底层实际存放的是由<value, value>构成的键值对。
向set中插入元素时，只需要插入value即可，不需要构造键值对。
set中的元素不可以重复，因此可以利用这一特性进行去重操作。
使用set的迭代器遍历set中的元素，可以得到有序序列。

至于为什么set中的元素不允许修改，主要是因为修改元素可能会破坏容器的有序性和唯一性。如果允许修改元素，可能会导致元素的排序位置发生变化，或者出现重复元素，这与set的设计目标和内部实现机制不符。

set的使用

insert插入

使用set之前，你应该联想到，set的底层是一棵搜索树。

五个值只打印了4个，是平衡搜索树，走的是中序遍历，打印出来就是有序的。

key模型：排序 + 去重。

迭代器的正向，反向迭代器，const迭代器，非const迭代器，和以前学的序列式容器都是一样使用的。

#include <iostream>
using namespace std;
#include <set>
void test_set1()
{
	set<int> s;
	s.insert(3);
	s.insert(1);
	s.insert(4);
	s.insert(3);
	s.insert(7);
	//遍历
	set<int>::iterator it = s.begin();
	while (it != s.end())
	{
		cout << *it << " ";
		++it;
	}
	cout << endl;
	//支持迭代器就支持范围for
	for (auto e : s)
	{
		cout << e << " ";
	}
	cout << endl;

}
int main()
{
	test_set1();
	return 0;
}

拷贝构造

void test_set1()
{
	set<int> s;
	s.insert(3);
	s.insert(1);
	s.insert(4);
	s.insert(3);
	s.insert(7);
	//拷贝构造
	set<int> copy(s);
	for (auto e : copy)
	{
		cout << e << " ";
	}
	cout << endl;
}
int main()
{
	test_set1();
	return 0;
}

erase删除

我们在使用 set 删除之前，先进行查找。但是这样删除不好，如果这个值没有找到了，去删除的话，程序直接崩溃，所以需要判断一下。

void test_set2()
{
	set<int> s;
	s.insert(1);
	s.insert(4);
	s.insert(3);
	s.insert(7);
	//删除
	set<int>::iterator pos = s.find(3); //但是这样删除不好，如果这个值没有找到了，删除程序直接崩溃，所以需要判断一下
	s.erase(pos);
	for (auto e : s)
	{
		cout << e << " ";
	}
}
int main()
{
	test_set2();
	return 0;
}

修改之后的代码

void test_set2()
{
	set<int> s;
	s.insert(1);
	s.insert(4);
	s.insert(3);
	s.insert(7);
	//删除
	set<int>::iterator pos = s.find(3); 
	if (pos != s.end())
		s.erase(pos);
	for (auto e : s)
	{
		cout << e << " ";
	}
}

我们还可以使用 set 里面的 erase 进行删除

如果先进行查找，给迭代器，你必须是找到一个合法的位置，如果不判断是否合法，程序就是报错，而 set 里面的 erase 直接删除。如果没有找到，erase不会进行任何操作。

void test_set3()
{
	set<int> s;
	s.insert(1);
	s.insert(4);
	s.insert(3);
	s.insert(7);
	//删除
	set<int>::iterator pos = s.find(3); 
	if (pos != s.end())
		s.erase(pos);
	//使用set里面的erase进行删除
	s.erase(4);
	s.erase(40); //如果没有不会进行任何操作
	for (auto e : s)
	{
		cout << e << " ";
	}
	cout << endl;

}

find查找

我们以前学过 vector、list、queue、deque 都没有 find，我们使用的是算法里面的 find，这里 set 有属于自己的 find。

//find查找
set<int>::iterator pos1 = s.find(30); //自己的find

set<int>::iterator pos2 = find(s.begin(), s.end(), 3);//算法里面的find

两者有什么区别？？？

上面这个 find 时间复杂度是 O(logN) -> 二叉搜索树的查找。

算法里面的 find 时间复杂度是 O(N)

为什么set有自己的 find 呢？？

因为set按自己的规则进行搜索的，效率高一点。

三、map

map的介绍

一、关联容器特性

map是一种关联容器，它以特定的次序存储由键值（key）和值（value）组合而成的元素。其中键值通常用于排序和唯一标识元素，值则存储与键值相关联的具体内容。键值和值的类型可以不同。

二、内部存储结构

在map内部，元素是按照键值进行比较排序的。通过成员类型value_type，将键值和值绑定在一起，其类型为pair<const key, T>，即一个包含常量键值和值的pair类型。

三、性能特点

与unordered_map相比，通过键值访问单个元素时，map的速度通常较慢。这是因为unordered_map基于哈希表实现，而map通常被实现为平衡二叉搜索树（如红黑树）。但是，map允许根据顺序对元素进行直接迭代，即对map中的元素进行迭代时，可以得到一个有序的序列。

四、下标访问

map支持下标访问符，在[]中放入键值，就可以找到与该键值对应的值。如果键值不存在，map会自动插入一个默认构造的值，并返回该值的引用。

总的来说，map适合需要有序存储和根据键值快速查找对应值的场景，同时也方便进行顺序遍历。但在对单个元素的访问速度要求极高且不关心顺序的情况下，unordered_map可能是更好的选择。

map的使用

key-value的模型，这里的T其实是value。

在学习 map 之前，我们需要先学习一下 pair 这个结构体，pair有两个模版参数，有一个叫fist 一个叫 second，带一个构造函数，k-v的键值对。

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)
 {}
 }

以下的代码编译不通过，为什么编译不通过呢？？？我们需要再次对pair进行分析

我们再次来看文档，所以我们会发现，当我们插入值的时候，传的是pair的对象，map的节点里面存的是pair结构体。

为什么map的节点里面存的是 pair 结构体呢？？？

因为和它的遍历有关系。

以下代码中，*it 里面存的是两个值，C+++不允许返回两个值，所以节点里面存的是 pair 这个结构，这个pair结构体有两个值。

这里就不能用 *it 进行访问了，这种写法是错误的。

#include <map>
void test_map1()
{
	map<int, int> m;
	m.insert(pair<int, int>(1, 1));
	m.insert(pair<int, int>(3, 3));
	m.insert(pair<int, int>(2, 2));
	map<int, int>::iterator it = m.begin();
	while (it != m.end())
	{
		cout << *it << endl;
		++it;
	}
	cout << endl;
}
int main()
{
	test_map1();
	return 0;
}

纠正后的代码：

#include <map>
void test_map1()
{
	map<int, int> m;
	m.insert(pair<int, int>(1, 1));
	m.insert(pair<int, int>(3, 3));
	m.insert(pair<int, int>(2, 2));
	map<int, int>::iterator it = m.begin();
	while (it != m.end())
	{
		cout << (*it).first << ":" << (*it).second << endl; // operator* 解引用返回是节点里面的值，相当于pair
		++it;
	}
}

但是更习惯于以下这种方式遍历：

it->->first,其实是这样写的，it->，拿到的是pair<K,V>指针，在对指针进行访问里面的元素即 it->->first，但是重载operator->就是为了增强可读性，编译器做了优化，这里省略了一个->。

即 operator-> 返回的是节点中值的指针，也就是pair<K,V>指针，即pair<K,V>*，再对这个指针进行访问里面的元素，为了增强可读性，编译器这里省略了一个->。

#include <map>
void test_map1()
{
	map<int, int> m;
	m.insert(pair<int, int>(1, 1));
	m.insert(pair<int, int>(3, 3));
	m.insert(pair<int, int>(2, 2));
	map<int, int>::iterator it = m.begin();
	while (it != m.end())
	{
		cout << it->first << ":" << it->second << endl;
		++it;
	}
}

支持迭代器就支持范围for

void test_map1()
{
	map<int, int> m;
	m.insert(pair<int, int>(1, 1));
	m.insert(pair<int, int>(3, 3));
	m.insert(pair<int, int>(2, 2));
	map<int, int>::iterator it = m.begin();
	while (it != m.end())
	{
		cout << it->first << ":" << it->second << endl;
		++it;
	}
	//支持范围for
	for (auto& e : m)
	{
		cout << e.first << ":" << e.second << endl;
	}
}

有时候插入值的时候，会使用 make_pair, make_pair 使用的更多。

使用场景，为什么通常使用make_pair？？？

在工程项目中通常不允许展开std，make_pair写起来就比较简洁

#include <map>
void test_map2()
{
	std::map<std::string, std::string> dict;
	dict.insert(pair<std::string, std::string>("sort", "排序"));
	dict.insert(make_pair("string", "排序")); //make_pair比较简洁，传过去自动推导类型
	std::map<std::string, std::string>::iterator it = dict.begin();
	while (it != dict.end())
	{
		cout << it->first << ";" << it->second << endl;
		++it;
	}
	cout << endl;
}
int main()
{
	test_map2();
	return 0;
}

`operator[]`运算符重载

统计次数

#include <map>
void test_map3()
{
	string strs[] = { "西瓜","香蕉","西瓜","苹果","西瓜","西瓜","西瓜","苹果" };
	map<string, int> countMap;
	for (auto& str : strs)
	{
		map<string, int>::iterator ret = countMap.find(str);
		if (ret != countMap.end())
		{
			//(*ret).second++;
			ret->second++;
		}
		else
		{
			countMap.insert(make_pair(str, 1));
		}
	}
	for (auto& e : countMap)
	{
		cout << e.first << ":" << e.second << endl;
	}
	cout << endl;
}
int main()
{
	test_map3();
	return 0;
}

有一种更简洁的方式统计次数：map有一个operator[]，底层是调用 insert 实现的

要搞懂operator[]就需要搞懂insert

#include <map>
void test_map4()
{
	string strs[] = { "西瓜","哈密瓜","西瓜","苹果","西瓜","西瓜","西瓜","苹果" };
	map<string, int> countMap;
	for (auto& str : strs)
	{
	   //1.如果水果没在map中，则插入成功
       //2.如果水果已经在map中，插入失败。通过返回值拿到水果所在的节点迭代器，++次数
		pair<map<string, int>::iterator, bool> ret = countMap.insert(make_pair(str, 1));
		if (ret.second == false)
		{
			ret.first->second++;
		}
	}
	for (auto& e : countMap)
	{
		cout << e.first << ":" << e.second << endl;
	}
	cout << endl;
}
int main()
{
	test_map4();
	return 0;
}

但是我们以后也不会这样使用，这里 insert 主要为了理解 operator[] 的原理，返回value的引用

operator[]的理解

假设是 int 类型，pair<str，int()> 即 pair<str，0>。

1、如果水果不在map中，则operator[]会插入pair<str，0〉，返回映射对象(次数)的引用进行了++。

2、如果水果在map中，则operator[]返回水果对应的映射对象(次数)的引用，对它++。

#include <map>
void test_map5()
{
	string strs[] = { "西瓜","樱桃","西瓜","苹果","西瓜","西瓜","西瓜","苹果" };
	map<string, int> countMap;
	for (auto& str : strs)
	{
		countMap[str]++;
	}
	for (auto& e : countMap)
	{
		cout << e.first << ":" << e.second << endl;
	}
	cout << endl;
}
int main()
{
	test_map5();
	return 0;
}

operator[]可以进行插入、查找、修改对应的映射对象

countMap["香蕉"]; //插入,value给默认的缺省值是""
countMap["香蕉"] = 1; //修改
cout << countMap["香蕉"] << endl; //查找 K 对应的 V
countMap["哈密瓜"] = 5; // 插入 + 修改

std::map<std::string, std::string> dict;
dict.insert(make_pair("sort", "排序"));
dict["string"]; //key是string，value是默认的缺省参数""
dict["string"] = " 字符串";//key=string有了，返回value的引用还可以修改它
dict["left"] = "左边";//插入同时把这个修改了

operator[]小结

operator[]的本质还是insert，为什么这里不用 find 呢？？？

假设用find，如果map中没有这个K，如何返回。
这里用 insert的好处：

如果key不在map中，则插入pair<K,mapped_type()>.再返回映射对象的引用，没有这个值int类型返回0
如果K在map中，则插入失败，返回K所在节点中的映射对象的引用，正是因为返回的是引用，所以可以修改value的值。
综上所述：
        map的 operator[] 三层作用

        1、插入

        2、查找k对应的映射对象

        3、修改k对应的映射对象

map的总结

map是一种关联容器，它以特定的顺序存储由键值对组成的元素，其中键值对的类型为std::pair<const Key, T>（通常表示为<k,v>，即键k和值v）。

增（插入元素）：可以使用insert方法向map中插入键值对。例如，map.insert(std::make_pair(key, value))。
删（删除元素）：通过erase方法可以删除指定键的元素或者一个范围内的元素。例如，map.erase(key)删除键为key的元素。
查（查找元素）：使用find方法可以查找特定键的元素，如果找到则返回指向该元素的迭代器，否则返回map.end()。
改（修改元素）：可以通过operator[]运算符来访问和修改map中的元素。如果键不存在，会自动插入一个默认构造的值，并返回该值的引用，然后可以对其进行赋值修改。
遍历（迭代元素）：可以使用迭代器和范围for循环来遍历map中的元素。例如，for (const auto& pair : map) { /* 处理键和值 */ };

四、multiset 和 multimap

multiset的介绍和使用

一、存储特点

multiset是一种按照特定顺序存储元素的容器，与set不同的是，它允许存储重复的元素。
在multiset中，元素的 “值” 同时也作为它的标识，即底层存储的是<value, value>组成的键值对，类型为T。并且元素在容器中是常量，不能被修改，但可以插入或删除。

二、内部排序与性能

在内部，multiset中的元素按照特定严格弱排序准则进行排序，这是由其内部比较规则（类型比较）决定的。
与unordered_multiset相比，通过键访问单个元素的速度通常较慢，但使用迭代器遍历时可以得到一个有序序列。
multiset在底层结构为二叉搜索树（通常是红黑树），因此在其中查找某个元素的时间复杂度为O(logN)。

，其中N是容器中元素的数量。

三、与set的区别及作用

与set的主要区别在于multiset中的元素可以重复，而set中的元素是唯一的。
multiset的作用之一是可以对元素进行排序，方便进行有序遍历和特定范围的查找。

#include <set>  //头文件还是这个
void test_multi()
{
	//根set的区别就是允许键值冗余
	multiset<int> ms;
	ms.insert(3);
	ms.insert(2);
	ms.insert(3);
	ms.insert(1);
	ms.insert(4);
	ms.insert(5);
	//查找到的是第一个出现的3
	auto pos = ms.find(3);
	cout << *pos << endl;
	--pos; //这个3 的前一位是 2
	cout << *pos << endl; //2
	for (auto& e : ms)
	{
		cout << e << " ";
	}
	cout << endl;
}
int main()
{
	test_multi();
	return 0;
}

multimap的介绍和使用

Multimap 是一种关联式容器，它以特定顺序存储由键（key）和值（value）组成的键值对<key, value>。与普通的映射容器不同，multimap 允许存在多个具有相同键的键值对，即键可以重复。

二、存储结构与排序

在 multimap 中，通常键用于排序和唯一标识元素（尽管实际上不唯一），值存储与键关联的内容。键和值的类型可以不同，通过内部成员类型value_type（即typedef pair<const Key, T> value_type）将键和值组合在一起。
在内部，multimap 中的元素按照特定严格弱排序标准对键进行排序，这是由其内部比较对象决定的。

三、性能特点与底层实现

与unordered_multimap相比，通过键访问单个元素的速度通常较慢。但是，使用迭代器遍历 multimap 中的元素可以得到关于键有序的序列。
multimap 在底层通常用二叉搜索树（如红黑树）来实现，这使得插入、删除和查找操作的时间复杂度为O(logN)。

，其中n是容器中元素的数量。

四、与 map 的区别

Multimap 和 map 的唯一不同之处在于 map 中的键是唯一的，而 multimap 中的键可以重复。

Multimap 和 multiset 是一样的使用，multimap 没有 operator[] ,会有多个相同的 key，不知道返回哪个key对应的 value。

总之，multimap 适用于需要存储可重复键的键值对并保持键有序的场景。

#include <map>
void test_multi()
{
	multimap<string, int> mm;
	mm.insert(make_pair("苹果", 1));
	mm.insert(make_pair("苹果", 1));
	mm.insert(make_pair("西瓜", 2));
	mm.insert(make_pair("西瓜", 1));
	for (auto& e : mm) 
	{
		cout << e.first << ":" << e.second << endl;
	}
}
int main()
{
	test_multi();
	return 0;
}

五、例题

前K个高频单词

. - 力扣（LeetCode）

使用 map 统计频率

首先定义一个 map<int, int> countMap，这个 map 的作用是统计数组中每个元素出现的频率。
通过遍历输入的数组 nums，对于每个元素 e，将其作为键，对应的值（出现的次数）进行累加。这样遍历完整个数组后，countMap 中就存储了每个不同元素及其出现的次数。

使用 multimap 进行排序

接着定义一个 multimap<int, int, greater<int>> sortMap，这个 multimap 的作用是根据元素出现的次数进行降序排序。
再次遍历之前统计好频率的 countMap，对于每个键值对 kv，将出现次数 kv.second 作为 multimap 的键，元素值 kv.first 作为值，插入到 sortMap 中。由于 multimap 的第三个模板参数设置为 greater<int>，所以会按照键（出现次数）从大到小进行排序。

提取前 k 个高频元素

创建一个空的 vector 用于存储最终结果。
然后使用迭代器 it 遍历排序后的 sortMap，每次将迭代器指向的元素的第二个值（即元素值）放入结果向量 v 中，并减少 k 的值。当 k 变为 0 时，说明已经找到了前 k 个高频元素，停止遍历。

返回结果

最后返回存储了前 k 个高频元素的vector。

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) 
    {
        map<int,int> countMap;
        for(auto e : nums) 
        {
            countMap[e]++;
        }
        multimap<int,int,greater<int>> sortMap;
        for(auto kv : countMap) 
        {
            sortMap.insert(make_pair(kv.second,kv.first));
        }
        vector<int> v;
        auto it =  sortMap.begin();
        while(it != sortMap.end()) 
        {
            if(k == 0) 
                break;
            v.push_back(it->second);
            ++it;
            --k;
        }
        return v;
    }
};

两个数组的交集I

. - 力扣（LeetCode）

使用 set 去重和排序

首先定义两个 set<int> 类型的集合 s1 和 s2。
分别遍历 nums1 和 nums2，将其中的元素插入到对应的集合中。这样做有两个好处，一是可以自动去除重复元素，二是 set 会自动对元素进行排序。

遍历两个集合找交集

定义两个迭代器 it1 和 it2，分别指向 s1 和 s2 的开头。
进入循环，只要两个迭代器都没有到达各自集合的末尾，就进行以下操作：
如果 *it1 < *it2，说明当前 s1 中的元素小于 s2 中的元素，那么将 it1 向后移动一位，继续比较下一个元素。
如果 *it2 < *it1，说明当前 s2 中的元素小于 s1 中的元素，那么将 it2 向后移动一位，继续比较下一个元素。
如果 *it1 == *it2，说明找到了共同的元素，将这个元素（*it1）加入结果vector 中，然后同时将 it1 和 it2 都向后移动一位，继续寻找下一个共同元素。

返回结果

最后返回存储了交集元素的向量 v。

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) 
    {
        set<int> s1;
        for(auto& e: nums1) 
        {
            s1.insert(e);
        }
        set<int> s2;
        for(auto& e : nums2) 
        {
            s2.insert(e);
        }
        vector<int> v;
        set<int>::iterator it1 = s1.begin();
        set<int>::iterator it2 = s2.begin();
        while(it1 != s1.end() && it2 != s2.end()) 
        {
            if(*it1 < *it2) 
            {
                ++it1;
            }  
            else if(*it2 < *it1) 
            {
                ++it2;
            }  
            else
            {
                v.push_back(*it1);
                ++it1;
                ++it2;
            }
        }
        return v;
    }
};

查看全文

http://www.kler.cn/a/377203.html