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

时间：2024-03-04 17:14:09

目录

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

二、键值对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模型就使用了<Key, Value>的键值对，可以通过键快速查找、访问或修改对应的值。

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

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

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

template <class T1, class T2>
pair<T1, T2> make_pair(T1 x, T2 y)
{
    return (pair<T1, T2>(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中存放元素的类型，实际在底层存储<value, value>的键值对。
Compare：set中元素默认按照小于来比较
Alloc：set中元素空间的管理方式，使用STL提供的空间配置器管理

注：

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

3.1.2. set的构造

函数声明 功能介绍
set (const Compare& comp = Compare(), const Allocator& = Allocator() );  构造空的set
set (InputIterator first, InputIterator last, const Compare& comp = Compare(), const Allocator& = Allocator() ); 用[first, last)区间中的元素构造set
set ( const set<Key,Compare,Allocator>& x); set的拷贝构造

3.1.3. set的迭代器

函数声明 功能介绍
iterator begin() 返回set中起始位置元素的迭代器
iterator end() 返回set中最后一个元素后面的迭代器
const_iterator cbegin() const 返回set中起始位置元素的const迭代器
const_iterator cend() const 返回set中最后一个元素后面的const迭代器
reverse_iterator rbegin() 返回set第一个元素的反向迭代器，即end
reverse_iterator rend() 返回set最后一个元素下一个位置的反向迭代器，即rbegin
const_reverse_iterator crbegin() const 返回set第一个元素的反向const迭代器，即cend
const_reverse_iterator crend() const 返回set最后一个元素下一个位置的反向const迭代器，即crbegin

3.1.4. set的容量

函数声明 功能介绍
bool empty ( ) const 检测set是否为空，空返回true，否则返回true
size_type size() const 返回set中有效元素的个数

3.1.5. set的操作

函数声明 功能介绍
iterator find ( const key_type& x ) const 返回set中值为x的元素的位置
size_type count ( const key_type& x ) const 返回set中值为x的元素的个数
iterator lower_bound (const value_type& val) const 返回>=val值位置的迭代器
iterator upper_bound (const value_type& val) const 返回>=val值位置的迭代器

3.1.6. set的修改

函数声明 功能介绍
pair<iterator,bool> insert ( const value_type& x ) 在set中插入元素x，实际插入的是<x, x>构成的键值对，如果插入成功，返回<该元素在set中的位置，true>,如果插入失败，说明x在set中已经存在，返回<x在set中的位置，false>
void erase ( iterator position ) 删除set中position位置上的元素
size_type erase ( const key_type& x )  删除set中值为x的元素，返回删除的元素的个数
void erase ( iterator first, iterator last ) 删除set中[first, last)区间中的元素
void swap ( set<Key,Compare,Allocator>& st ); 交换set中的元素
void clear ( )  将set中的元素清空

注：

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

3.1.7 set的使用示范

#include<set>

//整数比较
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的构造

函数声明 功能介绍
map() 构造一个空的map

3.2.3. map的迭代器

函数声明 功能介绍
begin()和end() begin:首元素的位置，end最后一个元素的下一个位置
cbegin()和cend() 与begin和end意义相同，但cbegin和cend所指向的元素不
能修改
rbegin()和rend() 反向迭代器，rbegin在end位置，rend在begin位置，其
++和--操作与begin和end操作移动相反
crbegin()和crend() 与rbegin和rend位置相同，操作相同，但crbegin和crend所
指向的元素不能修改

3.2.4. map的容量与元素访问

函数声明 功能介绍
bool empty ( ) const 检测map中的元素是否为空，是返回true，否则返回false
size_type size() const 返回map中有效元素的个数
mapped_type& operator[] (const 
key_type& k)		 返回去key对应的value

注： 

  • 在元素访问时，有一个与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中元素的修改

函数声明 功能介绍
pair<iterator,bool> insert ( const value_type& x ) 在map中插入键值对x，注意x是一个键值对，返回值也是键值对：iterator代表新插入元素的位置，bool代表释放插入成功
void erase ( iterator position ) 删除position位置上的元素
size_type erase ( const key_type& x ) 删除键值为x的元素
void erase ( iterator first, iterator last ) 删除[first, last)区间中的元素
void swap ( map<Key,T,Compare,Allocator>& mp ) 交换两个map中的元素
void clear ( ) 将map中的元素清空
iterator find ( const key_type& x ) 在map中插入key为x的元素，找到返回该元素的位置的迭代器，否则返回end
const_iterator find ( const key_type& x ) const 在map中插入key为x的元素，找到返回该元素的位置的const迭代器，否则返回cend
size_type count ( const key_type& x ) const 返回key为x的键值在map中的个数，注意map中key是唯一的，因此该函数的返回值要么为0，要么为1，因此也可以用该函数来检测一个key是否在map中

注：

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

3.2.6 map的使用示范

#include <map>

//整数比较
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<char, int>('f', 1));
	pair<map<char, 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<const key_type,mapped_type>

	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中再底层中存储的是<value, value>的键值对。
        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<const Key, T> value_type;
  • 在内部，multimap 中的元素总是根据其键值及其内部比较对象（Compare 类型）指示的特定严格弱序关系进行排序。
  • 与 unordered_multimap 相比，multimap 容器通过其键访问单个元素时通常会更慢，但允许根据其顺序直接对子集进行迭代。
  • multimap 通常作为二叉搜索树实现。

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

相关文章