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

C++set与map容器

article 2024/11/15 11:15:37

一、关联式容器和序列式容器

二、树形结构的关联式容器

三、set容器

1.set容器的定义

2.set的构造

3.set的迭代器

4.set的容量

5.set的修改操作（set容器不支持修改数据）

6.set的一些其他常用接口

（1）find函数

（2）lower_bound函数

（3）upper_bound函数

（4）count函数

四、multiset容器

五、map容器

1.map容器的定义

2.map的构造

3.map的迭代器

编辑 4.map的容量

5.map的修改操作

6.map的[ ]

7.map的一些其他常用接口

六、multimap容器

一、关联式容器和序列式容器

曾经学过的vector、list、stack、queue等这些统称为序列式容器，因为它们底层都为线性的数据结构，只存储数据元素本身

而关联式容器是一种基于树或者哈希表的数据结构，当存储的数据是<key,value>结构的键值对，不仅存储数据元素key本身，还会存储与key相关联的数据value，数据检索时比序列式容器效率更高。关联式容器中的元素会根据键值自动排序，或者根据哈希值分布

二、树形结构的关联式容器

根据应用场景的不同，STL一共设计了两种不同结构的关联式容器：树形结构和哈希结构

树形结构的关联式容器主要有四种：map、set、multimap、multiset，其底层都是使用红黑树（平衡搜索树）

三、set容器

set容器底层使用的是K模型的红黑树（平衡搜索树）

二叉搜索树的查找和删除效率都很高，通常为logN，10亿的数据最多只要查找30次

1.set容器的定义

set容器是一个类模板，提供了一个仿函数。因为如果存储的数据时Date*这样的自定义类型，在比较大小时直接通过指针判断大小会出错，所以我们可以自己定义一个仿函数传进去使用就可以解决问题

2.set的构造

全缺省构造、迭代器区间构造、拷贝构造

3.set的迭代器

4.set的容量

5.set的修改操作（set容器不支持修改数据）

set容器不会插入重复数据，遇到重复数据不会插入

6.set的一些其他常用接口

（1）find函数

为什么算法库中有find函数，set容器自己还要提供一个find查找函数呢？

因为set容器自己提供的find函数可以根据二叉搜索树的特性来查找数据，比根值大就向右找，比根值小向左找。

函数原型：

iterator find (const value_type& val) const;

找到了则返回迭代器指向元素位置，找不到则返回迭代器指向最后一个元素的下一个位置

（2）lower_bound函数

函数原型：

iterator lower_bound (const value_type& val) const;

返回一个迭代器，该迭代器指向大于等于val值的一个元素位置

（3）upper_bound函数

函数原型：

iterator upper_bound (const value_type& val) const;

返回一个迭代器，该迭代器指向大于val值的一个元素位置

void test2()
{
	set<int> s;
	for (size_t i = 0; i < 10; ++i)
		s.insert(i * 10);

	set<int>::iterator itlow = s.lower_bound(30);
	auto itup = s.upper_bound(80);
	//[30,80)
	s.erase(itlow, itup);//删除[30,80)区间的数据
	for (auto e : s)
		cout << e << " ";
	cout << endl;
}

（4）count函数

函数原型：

size_type count (const value_type& val) const;

在容器中搜索val数据的个数，在set容器中不允许数据冗余，所以通常只返回0或1，可以用来快速判断该数据是否在set容器中

四、multiset容器

multiset容器与set容器没有太大区别，不同点在于multiset容器支持存储重复数据（可以规定重复数据插在左孩子或右孩子）。对于重复数据的遍历，multiset容器找到一个数据后并不会立即返回该数据的位置，而是会继续遍历（以重复数据插在左孩子为例）左子树，如果左子树中没有相同的数据了才会返回数据的位置。

五、map容器

1.map容器的定义

Key是键值对中的key类型；T是键值对中的value类型；Compare是仿函数

map中存储的类型实际上是一个键值对pair<const Key first, T second>

关于pair模板类详见文章：C++中的模板类pair_pair c++-CSDN博客

2.map的构造

全缺省构造、迭代器构造、拷贝构造

3.map的迭代器

4.map的容量

5.map的修改操作

map的insert函数，如果插入的key不存在，插入成功，返回pair<新插入键值对的迭代器,true>;如果插入的key；如果插入的key存在，插入失败，返回pair<已存在的key键值对的迭代器,false>

6.map的[ ]

map的[ ]和vector等容器的[ ]不同，vector容器的[ ]传入的是下标随机访问容器数据，而map的[ ]传入的是key值，如果key存在于map中就返回其对应value的引用，如果不存在就使用该key和默认的value（调用value类型的默认构造，例如int类型就调用int类的默认构造，string类型就调用string类的默认构造）构建一个键值对插入，并返回其value引用（）

void test()
{
	map<string, int> countMap;
	string arr[] = { "苹果","西瓜","苹果","苹果","西瓜","苹果","西瓜","香蕉","西瓜","香蕉" };
	for (auto& e : arr)
	{
		countMap[e]++;
		//map<string, int>::iterator ret = countMap.find(e);
		//if (ret != countMap.end())
		//{
		//	ret->second++;
		//}
		//else
		//{
		//	countMap.insert({ e,1 });
		//}
	}
	for (auto& e : countMap)
		cout << e.first << ":" << e.second << endl;
}