【C++】map和set——树形结构的关联式容器

目录

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

二、键值对pair

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

3.1 set

3.1.1.set的模板参数

3.1.2. set的构造

3.1.3. set的迭代器

3.1.4. set的容量

3.1.5. set的操作

3.1.6. set的修改

3.1.7 set的使用示范

3.2 map

3.2.1. map的模板参数说明

3.2.2. map的构造

3.2.3. map的迭代器

3.2.4. map的容量与元素访问

3.2.5. map中元素的修改

3.2.6 map的使用示范

3.3 multiset

3.4 multimap

---

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

在之前的学习中，我们学习到了部分容器，例如vector(动态数组)、list(双向链表)、deque(双端队列)、forward_list(单向链表)等，这些容器统称为序列式容器，它以线性序列的形式存储元素本身，并允许元素的快速插入、删除和访问。

与关联式容器不同，序列式容器中的元素按照它们被插入的顺序排列，而非根据键或值进行排序。

关联式容器是另一种容器，它通过键值对（key-value pair）的方式来组织和存储元素。关联式容器提供了根据键（key）快速查找、插入和删除元素的能力。

---

二、键值对pair

键值对（key-value pair）用来表示具有一一对应关系的一种结构，用于将一个键（key）和一个相应的值（value）相关联起来。在键值对中，键用于唯一标识或索引值，而值则是与该键相关联的数据或信息。

键值对通常用于构建映射关系，例如上一节二叉搜索树中讲到的KV模型就使用了的键值对，可以通过键快速查找、访问或修改对应的值。

SGI-STL中关于键值对的定义：

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

键值对的常用函数make_pair()的定义

template
pair make_pair(T1 x, T2 y)
{
    return (pair(x, y));
} 

在实际应用中，键值对的例子包括：
在字典中，每个单词（键）对应着它的解释（值）。
在数据库中，每条记录有一个唯一的标识（键），对应着记录的具体内容（值）。
在编程中，使用键值对来存储配置信息、缓存数据等。

键值对的优点在于快速查找和索引数据，使得数据的管理和操作更为高效和便捷。因此，在许多编程场景下，键值对都是一种常见且有用的数据结构。

---

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

根据应用场景的不同，STL实现了两种不同结构的关联式容器：树型结构与哈希结构。树型结
构的关联式容器主要有四种：map、set、multimap、multiset。这四种容器的共同点是：使
用平衡搜索树(即红黑树)作为其底层结果，容器中的元素是一个有序的序列。

3.1 set

set的特性：

• 存储唯一元素：set 是存储唯一元素的容器，每个元素的值同时也是其键，且键值必须是唯一的。
• 内部排序：set 内部的元素会根据特定的严格弱序关系进行排序，这一关系由其内部的比较对象（Compare 类型）指定。这确保了 set 中的元素始终保持有序状态。
• 不可修改的值：一旦元素被放入 set 容器，其值就无法再被修改（元素始终为 const）。但可以向容器中插入或移除元素。
• 底层实现：set 通常使用二叉搜索树来实现，确保了元素的快速查找和有序存储。
• 相对速度：与 unordered_set 相比，set 容器通常在按照键值访问单个元素时速度较慢，但允许基于其顺序直接进行子集迭代。
• 在set中找某个元素，时间复杂度为：O(log_2 N)
• 使用set时，要包含头文件。

3.1.1.set的模板参数

 T: set中存放元素的类型，实际在底层存储的键值对。
Compare：set中元素默认按照小于来比较
Alloc：set中元素空间的管理方式，使用STL提供的空间配置器管理

注：

• set中只放value，但在底层实际存放的是由构成的键值对。
• set中插入元素时，只需要插入value即可，不需要构造键值对。

3.1.2. set的构造

3.1.3. set的迭代器

3.1.4. set的容量

3.1.5. set的操作

3.1.6. set的修改

注：

• erase函数可与 find 函数配合使用。
• 若删除end对应的迭代器，则程序崩溃。
• 若删除一个不存在的值，则什么也不做。
• erase函数的返回值为size_type ，表示删除元素的个数，set中每个元素是唯一的，此返回值是为后面multiset预留的。同理，count函数也是为multiset预留的。

3.1.7 set的使用示范

#include
 
//整数比较
bool fcomp_set(int lhs, int rhs)
{
	return lhs < rhs;
}
 
//类比较
struct classcomp_set
{
	bool operator()(const int& lhs, const int& rhs) const
	{
		return lhs < rhs;
	}
};
 
void Test1()
{
	int arr1[] = { 11,21,13,41,5 };
 
	set<int> first;	//空集合
	set<int> second(arr1, arr1 + 5);//数组初始化集合
	set<int> third(second);//集合初始化集合，拷贝构造
	set<int> fourth(second.begin(), second.end());//迭代器
	
	set<int, classcomp_set> fifth;	//类为比较
	
	bool(*fp)(int, int) = fcomp_set;//函数指针
	set<int, bool(*)(int, int)> sixth(fp);//函数指针作为比较
 
	//打印third
	cout << "third: ";
	for (auto x : third)
	{
		cout << x << " ";
	}
	cout << endl;
 
	//插入
	for (int i = 0; i < 5; i++)
	{
		fifth.insert(arr1[i]);
		sixth.insert(arr1[i]);
	}
 
	//打印fifth
	cout << "fifth: ";
	for (auto x : fifth)
	{
		cout << x << " ";
	}
	cout << endl;
 
	//打印sixth
	cout << "sixth: ";
	for (auto x : sixth)
	{
		cout << x << " ";
	}
	cout << endl;
 
	//删除
	cout << "------------------" << endl;
	set<int>::iterator it;
	cout << "third 直接删除5" << endl;
	third.erase(5);
	it = third.find(13);
	cout << "third 通过find删除13" << endl;
	third.erase(it);
	cout << "third 使用find返回值作为参数删除21" << endl;
	third.erase(third.find(21));
	cout << "third: ";
	for (auto x : third)
	{
		cout << x << " ";
	}
	cout << endl;
 
	cout << "清空sixth" << endl;
	sixth.clear();
	cout << "sixth元素个数：" << sixth.size() << endl;
}

3.2 map

map 的一些关键特性：

• 关联容器：map 是一种关联式容器，用于存储由键值和映射值组成的元素，按照特定顺序进行排序。
• 键值和映射值：在 map 中，键值通常用于对元素进行排序和唯一标识，而映射值存储与该键相关联的内容。键和映射值的类型可以不同，它们被组合在一起形成 value_type 成员类型，这是一个 pair 类型，结合了键和映射值。
• 内部排序：map 内部的元素始终根据其键按照特定的严格弱序关系进行排序，这一排序关系由其内部的比较对象（Compare 类型）指定。默认按照小于的方式对key进行比较
• 不可修改的键：一旦键(key)被放入 map 容器，它们的值也是不可修改的。但可以通过键直接访问对应的映射值(value)，使用方括号操作符（operator[]）实现。
• 底层实现：map 通常使用二叉搜索树（红黑树）来实现，确保了元素的有序存储和高效查找。
• 在map中找某个元素，时间复杂度为：O(log_2 N)
• 使用map时，要包含头文件。

总的来说，map 是一种能够存储键值对并按键排序的容器，适合需要按键快速查找映射值的场景，并支持基于顺序进行子集迭代。

3.2.1. map的模板参数说明

key: 键值对中key的类型
T： 键值对中value的类型
Compare: 比较器的类型，map中的元素是按照key来比较的，缺省情况下按照小于来比较，一般情况下(内置类型元素)该参数不需要传递，如果无法比较时(自定义类型)，需要用户自己显式传递比较规则(一般情况下按照函数指针或者仿函数来传递)
Alloc：通过空间配置器来申请底层空间，不需要用户传递，除非用户不想使用标准库提供的空间配置器

3.2.2. map的构造

3.2.3. map的迭代器

3.2.4. map的容量与元素访问

注： 

• 在元素访问时，有一个与operator[]类似的操作at()(该函数不常用)函数，都是通过key找到与key对应的value然后返回其引用，不同的是：当key不存在时，operator[]用默认value与key构造键值对然后插入，返回该默认value的引用，at()函数直接抛异常。
• 对[]的解释：

  mapped_type& operator[] (const key_type& k)

  {

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

  }

  关键： insert 返回的 pair 是 ， iterator 是插入元素的迭代器， bool 表示是否存在，false 表示已经存在

3.2.5. map中元素的修改

注：

• 范围for可以使用&引用，用于防止范围for的拷贝代价过大，
  不修改时用const，需要修改时不加const。
• map元素(pair)的first不能修改，但是second可以修改，因为map的value_type定义为pair

3.2.6 map的使用示范

#include 
 
//整数比较
bool fcomp_map(char lhs, char rhs)
{
	return lhs < rhs;
}
 
//类比较
struct classcomp_map
{
	bool operator()(const char& lhs, const char& rhs) const
	{
		return lhs < rhs;
	}
};
 
void Test2()
{
	map<char, int> first;
	first['a'] = 10;
	first['b'] = 20;
	first['c'] = 30;
	first['d'] = 40;
	//If k matches the key of an element in the container,
	// the function returns a reference to its mapped value.
	//If k does not match the key of any element in the container,
	//the function inserts a new element with that keyand returns a reference to its mapped value.
 
	//迭代器拷贝
	map<char, int> second(first.begin(),first.end());
	//拷贝构造
	map<char, int> third(second);
	//类为比较
	map<char, int, classcomp_map> fourth;
	//函数指针为比较
	bool (*fp2)(char, char) = fcomp_map;
	map<char, int, bool (*)(char, char)> fifth(fp2);
	//map的初始化方法比set少了数组初始化
 
	//插入
	fourth.insert(pair<char, int>('e', 50));
 
	//fourth.insert(pair('f', 1));
	pairchar, int>::iterator,bool> tmp1;
	tmp1 = fourth.insert(pair<char, int>('f', 60));//insert的返回值的类型要与接受值的保持一致
	if (tmp1.second == false)
	{
		cout << "'e' 已经存在 " << "，值为：" << tmp1.first->second << endl;;
	}
 
	map<char, int>::iterator it = fourth.begin();
	fourth.insert(it, pair<char, int>('g', 70));
	fourth.insert(it, pair<char, int>('h', 80));
 
	//使用make_pair
	fourth.insert(it, make_pair('i', 90));
	it = fourth.begin();
	while (it!= fourth.end())
	{
		cout << (*it).first << ":" << (*it).second << endl;
		//数据是自定义类型时多用箭头访问，返回一个pair的指针
		cout << it->first << ":" << it->second << endl;//相当于it.operator->()->first
		cout << it.operator->()->first << ":" << it.operator->()->second << endl;
		//三种方法结果相同
		it++;
	}
	cout << "----------------" << endl;
 
	map<char, int> sixth;
	sixth.insert(fourth.begin(), fourth.end());
 
	//使用&引用，防止范围for拷贝代价过大，不修改时用const，修改时不加
	//注意，first不能修改，但是second可以修改
	//因为map的value_type定义为pair
 
	cout << "third:" << endl;
	for (const auto& x : third)
	{
		cout << x.first << " => " << x.second << endl;
	}
	cout << "fourth:" << endl;
	for (const auto& x : fourth)
	{
		cout << x.first << " => " << x.second << endl;
	}
	fifth.insert(fourth.begin(), fourth.find('h'));
	cout << "fifth:" << endl;
	for (const auto& x : fifth)
	{
		cout << x.first << " => " << x.second << endl;
	}
 
	//删除
	cout << "----------------" << endl;
	it = sixth.find('f');
	sixth.erase(it);
	sixth.erase('h');
	cout << "sixth:" << endl;
	for (const auto& x : sixth)
	{
		cout << x.first << " => " << x.second << endl;
	}
 
	it = second.find('b');
	second.erase(it, second.end());
	cout << "second:" << endl;
	for (const auto& x : second)
	{
		cout << x.first << " => " << x.second << endl;
	}
}

3.3 multiset

multiset（多重集）是一种存储元素并按特定顺序排列的容器，其中可以存在多个具有相同值的元素。

• 在 multiset 中，元素的值本身也是其标识（值本身即为键，类型为 T）。在容器中，元素的值一旦被放入就无法修改（元素始终为 const），但可以向容器中插入或移除元素。
• 在内部，multiset 中的元素总是根据其内部比较对象（Compare 类型）指示的特定严格弱序关系进行排序。
• 与 unordered_multiset 相比，multiset 容器访问单个元素时通常会更慢，但允许根据其顺序直接对子集进行迭代。
• multiset 通常作为二叉搜索树实现。

注：

        1. multiset中再底层中存储的是的键值对。
        2. mtltiset的插入接口中只需要插入即可，相同时继续插入。
        3. 与set的区别是，multiset中的元素可以重复，set是中value是唯一的
        4. 使用迭代器对multiset中的元素进行遍历，可以得到有序的序列
        5. multiset中的元素不能修改
        6. 在multiset中找某个元素，时间复杂度为：O(log_2 N)
        7. multiset的作用：可以对元素进行排序

3.4 multimap

multimap（多重映射）是一种关联容器，用于存储由键值和映射值组成的元素组合，遵循特定顺序，并且其中可以存在多个具有相同键的元素。

• 在 multimap 中，键值通常用于对元素进行排序和唯一标识，而映射值则存储与此键相关联的内容。键和映射值的类型可以不同，并且它们被组合在一起形成成员类型 value_type，这是一个结合了键和映射值的 pair 类型：
  typedef pair value_type;
• 在内部，multimap 中的元素总是根据其键值及其内部比较对象（Compare 类型）指示的特定严格弱序关系进行排序。
• 与 unordered_multimap 相比，multimap 容器通过其键访问单个元素时通常会更慢，但允许根据其顺序直接对子集进行迭代。
• multimap 通常作为二叉搜索树实现。

注： 
        1. multimap中的key是可以重复的，而map中的key是唯一的。
        2. multimap中的元素默认将key按照小于来比较
        3. multimap中没有重载operator[]操作。
        4. 使用时与map包含的头文件相同