
在C++编程的浩瀚宇宙中,标准模板库(STL)犹如一颗璀璨的星辰,为开发者们提供了强大的数据结构和算法支持。而在STL的众多容器中,Map与Set无疑是两颗尤为耀眼的明珠,它们以高效、有序的方式管理着数据,让键值对和集合的处理变得轻松自如。 本文将带你一起深入探索C++ STL中的Map与Set容器,揭开它们高效数据管理的神秘面纱。从基本用法到底层实现原理,再到实际应用中的
在C++的编程世界中,关联式容器是数据结构领域中的瑰宝,它们不仅提供了高效的数据存储和检索功能,还通过键值对的映射机制,极大地丰富了程序设计的灵活性和多样性。本文将深入探讨C++关联式容器的核心特性、工作原理以及创新应用,为您揭开这些强大工具的神秘面纱。
C++标准库中的关联式容器主要包括std::map、std::set、std::multimap和std::multiset等。它们共同的特点是基于键值对(key-value)或纯键(key-only)进行存储和检索,支持高效的查找、插入和删除操作。
std::map类似,但允许键的重复。std::set类似,但允许键的重复。关联式容器内部通常使用平衡二叉树(如红黑树)来实现高效的查找、插入和删除操作。这些操作的时间复杂度通常为O(log n),其中n是容器中元素的数量。平衡二叉树通过自动调整树的结构来保持平衡,从而确保操作的高效性。
std::map和std::set中的键是唯一的,这确保了数据的唯一性和一致性。std::map和std::multimap通过键值对的方式存储数据,这使得它们能够轻松地实现数据的映射和查找。在C++中,键值对(Key-Value Pair)是一种常见的数据结构,它由一个键(Key)和一个值(Value)组成。这种结构在编程中非常有用,因为它允许你通过键来快速查找、更新或删除与之关联的值。
在C++中,键值对通常通过以下几种方式实现:
std::map 和 std::unordered_map:    std::map 是一个关联容器,它存储键值对,并根据键的排序顺序自动排序这些对。默认情况下,std::map 使用 < 运算符来比较键。std::unordered_map 是另一个关联容器,它也存储键值对,但不保证元素的顺序。它使用哈希表来实现快速查找、插入和删除操作。std::pair:    std::pair 是一个模板类,它创建了一个包含两个数据成员的对象。这两个数据成员分别被称为 first 和 second,可以分别用作键和值。虽然 std::pair 本身不直接实现键值对的存储和查找功能,但它经常与 std::map、std::unordered_map 或其他容器一起使用来存储键值对。这些树形结构的关联式容器具有以下特点:
std::map和std::set):这些容器保证键的唯一性,即不允许插入具有相同键的多个元素(对于std::multimap和std::multiset则允许键的重复)。树形结构的关联式容器在C++中有广泛的应用场景,包括但不限于:
std::map和std::multimap可以用于实现字典和映射,其中键是单词或标识符,值是相应的定义或数据。std::set和std::multiset可以用于实现集合操作,如并集、交集和差集等。总之,树形结构的关联式容器是C++标准库中非常强大且灵活的数据结构,它们提供了高效的查找、插入和删除操作,并且保证了元素的排序顺序和键的唯一性(对于std::map和std::set)。
set<typename> name;,其中typename可以是任何基本类型(如int、double、char等),也可以是STL标准容器(如vector、set、queue等)。set<typename> name;,创建一个空的set。set<typename> name(const set<typename>& other);,创建一个新的set,它是现有set的副本。set<typename> name{val1, val2, ...};,使用初始化列表来构造set。set<typename> name(first, last);,使用一个迭代器范围[first, last)来构造set。insert(const typename& value);:将一个元素插入到set中。如果元素已存在,则插入操作将被忽略。pair<iterator, bool> insert(const typename& value);:返回一个pair,其中iterator指向插入的位置,bool表示插入是否成功。erase(iterator pos);:删除迭代器pos指向的元素。erase(const typename& value);:删除值为value的元素。erase(iterator first, iterator last);:删除范围[first, last)内的所有元素。find(const typename& value);:查找值为value的元素,返回一个指向该元素的迭代器。如果未找到,则返回end()。count(const typename& value);:返回值为value的元素在set中出现的次数。对于set来说,返回值只能是0或1。size();:返回set中元素的个数。empty();:判断set是否为空。如果为空,返回true;否则返回false。clear();:清空set中的所有元素。begin();:返回一个指向set中第一个元素的迭代器。end();:返回一个指向set末尾的迭代器(注意,这是一个“尾后迭代器”,不指向任何实际元素)。lower_bound(const typename& value);:返回指向第一个不小于value的元素的迭代器。upper_bound(const typename& value);:返回指向第一个大于value的元素的迭代器。equal_range(const typename& value);:返回一个pair,表示value在set中的范围(即[lower_bound, upper_bound))。set的迭代器是双向迭代器,支持正向和反向遍历。由于set中的元素是有序的,所以迭代器的遍历顺序也是有序的。此外,set的迭代器是const_iterator,这意味着不能通过迭代器直接修改元素的值。
以下是一个简单的使用示例,展示了如何创建set、插入元素、查找元素和遍历元素:
#include <iostream>  
#include <set>  
  
using namespace std;  
  
// set的基本使用
void test_set1() {
	// 排序+去重
	set<int> s;
	s.insert(2);
	s.insert(4);
	s.insert(5);
	s.insert(1);
	s.insert(7);
	s.insert(7); // 去重原理:一个值已经有了,我们就不插入
	
	auto it = s.begin();
	while (it != s.end()) {
		cout << *it << " ";
		++it;
	}
	cout << endl;
	
	for (auto e : s) {
		cout << e << " ";
	}
	cout << endl;
	/*auto pos = s.find(3);
	if(pos != s.end())
		s.erase(pos);*/
	s.erase(1);
	for (auto e : s) {
		cout << e << " ";
	}
	cout << endl;
}
// set迭代器的使用
void test_set2() {
	set<int> myset;
	set<int>::iterator itlow, itup;
	for (int i = 1; i < 10; i++)
		myset.insert(i * 10); // 10 20 30 40 50 60 70 80 90
	// 删除[30 60],但是迭代器是左闭右开
	itlow = myset.lower_bound(30);                // 下限 >=     
	itup = myset.upper_bound(60);                 // 上限 >
	// [itlow, itup)
	cout << *itlow << endl;
	cout << *itup << endl;
	myset.erase(itlow, itup);
	for (auto e : myset) {
		cout << e << " ";
	}
	cout << endl;
}
int main(){
    test_set1();
    cout << endl << endl;
    test_set2();
    
	return 0;
}综上所述,C++中的set是一种非常实用的容器,它提供了高效的查找、插入和删除操作,并且保证了元素的唯一性和有序性。
在C++中,multiset是一种非常有用的标准模板库(STL)容器,它用于存储一组按照特定顺序排列的元素,并且允许元素重复。以下是对multiset的详细介绍:
set容器不同,multiset允许存储重复的元素。multiset中的元素会根据一定的顺序(默认是升序)自动进行排序。multiset中的元素值在插入后不能直接被修改,因为元素值就是其键值,直接修改会破坏容器的有序性。不过,可以通过删除旧元素并插入新元素的方式来间接修改。multiset的底层通常使用红黑树这种平衡二叉搜索树结构来实现,以确保高效的查找、插入和删除操作。multiset<typename> name;,其中typename表示要存储的元素类型。multiset<typename> name;,创建一个空的multiset。multiset<typename> name(const multiset<typename>& other);,创建一个新的multiset,它是现有multiset的副本。multiset<typename> name{val1, val2, ...};,使用初始化列表来构造multiset。multiset<typename> name(first, last);,使用一个迭代器范围[first, last)来构造multiset。multiset提供了丰富的成员函数来操作容器中的元素,包括但不限于:
insert(const typename& value);:将一个元素插入到multiset中。如果元素已存在,则会在保持有序性的前提下,将新元素插入到已有元素的后面(因为允许重复)。iterator insert(const_iterator position, const typename& value);:在指定位置position前插入一个元素,并返回指向新插入元素的迭代器。如果position是end()迭代器,则元素会被添加到容器的末尾。insert函数,如使用范围插入、使用初始化列表插入等。erase(iterator pos);:删除迭代器pos指向的元素。erase(const typename& value);:删除值为value的所有元素。erase(iterator first, iterator last);:删除范围[first, last)内的所有元素。find(const typename& value);:查找值为value的元素,返回一个指向该元素的迭代器。如果未找到,则返回end()迭代器。count(const typename& value);:返回值为value的元素在multiset中出现的次数。size();:返回multiset中元素的个数。empty();:判断multiset是否为空。如果为空,返回true;否则返回false。clear();:清空multiset中的所有元素。begin();和end();:分别返回一个指向multiset中第一个元素和末尾元素的迭代器(尾后迭代器)。rbegin();和rend();:分别返回一个指向multiset中最后一个元素和第一个元素前面的位置的逆向迭代器。lower_bound(const typename& value);:返回指向第一个不小于value的元素的迭代器。upper_bound(const typename& value);:返回指向第一个大于value的元素的迭代器。equal_range(const typename& value);:返回一个pair,表示value在multiset中的范围(即[lower_bound, upper_bound))。默认情况下,multiset中的元素会按照其类型的默认比较函数(通常是<运算符)进行排序。如果需要自定义排序规则,可以在声明multiset时提供一个自定义的比较函数或比较类。例如:
struct Compare {  
    bool operator()(const int& a, const int& b) const {  
        return a > b; // 降序排序  
    }  
};  
  
multiset<int, Compare> myMultiset;在这个例子中,我们定义了一个比较类Compare,它重载了operator()来指定降序排序规则。然后,我们使用这个比较类来创建一个multiset对象myMultiset,它将按照降序对元素进行排序。
以下是一个简单的使用示例,展示了如何创建multiset、插入元素、查找元素和遍历元素:
#include <iostream>  
#include <set>  
  
using namespace std;  
  
int main() {  
    multiset<int> myset;
	multiset<int>::iterator itlow, itup;
	
    // 插入元素,允许重复
	myset.insert(1);
	myset.insert(3);
	myset.insert(1);
	myset.insert(4);
	myset.insert(1);
	myset.insert(1);
	for (auto e : myset) {
		cout << e << " ";
	}
	cout << endl;
	// count返回1的个数
	cout << myset.count(1) << endl;
    // 返回一个pair,表示value在multiset中的范围(即[lower_bound, upper_bound))。
	auto ret = myset.equal_range(1);
	itlow = ret.first;
	itup = ret.second;
	// 删除区间内的所有1
	myset.erase(itlow, itup);
	for (auto e : myset) {
		cout << e << " ";
	}
	cout << endl;
  
    return 0;  
}在C++中,map是一种非常有用的标准模板库(STL)容器,它用于存储键值对(key-value pairs),其中每个键都是唯一的,并且与一个特定的值相关联。以下是map的使用与定义的详细介绍:
map的定义通常使用以下语法:
map<KeyType, ValueType> mapName;其中,KeyType表示键的类型,ValueType表示值的类型,mapName是map对象的名称。
例如,定义一个存储字符串到整数的映射的map:
map<string, int> myMap;向map中插入元素有多种方法:
insert成员函数:myMap.insert(pair<string, int>("key1", 100));或者:
myMap.insert(make_pair("key2", 200));[]直接赋值(如果键不存在,则插入新键值对;如果键已存在,则更新对应的值):myMap["key3"] = 300;举例:
void test_map1() {
	map<string, string> dict;
	// 1.有名对象
	pair<string, string> kv1("insert", "插入");
	dict.insert(kv1);
	// 2.匿名对象
	dict.insert(pair<string, string>("sort", "排序"));
	// 3.make_pair
	dict.insert(make_pair("string", "字符串"));
	// 4.C++11 多参数的构造函数的隐式类型转换:构造+拷贝构造优化成一步
	dict.insert({ "list", "双向链表" });
	auto it = dict.begin();
	while (it != dict.end()) {
		cout << it->first << ":" << it->second << " ";
		++it;
	}
	cout << endl;
}可以使用find成员函数来查找元素:
auto it = myMap.find("key1");  
if (it != myMap.end()) {  
    cout << "Found: " << it->first << " => " << it->second << endl;  
} else {  
    cout << "Key not found." << endl;  
}find函数返回一个迭代器,如果找到了指定的键,则迭代器指向该元素;否则,迭代器等于end()。
可以使用迭代器来遍历map中的所有元素:
for (auto it = myMap.begin(); it != myMap.end(); ++it) {  
    cout << it->first << " => " << it->second << endl;  
}或者使用范围for循环(C++11及以上):
for (const auto& pair : myMap) {  
    cout << pair.first << " => " << pair.second << endl;  
}可以使用erase成员函数来删除元素:
myMap.erase("key1");auto it = myMap.find("key2");  
if (it != myMap.end()) {  
    myMap.erase(it);  
}auto it_begin = myMap.find("key_start");  
auto it_end = myMap.find("key_end");  
if (it_begin != myMap.end() && ++(it_end.first) != myMap.end()) {  
    myMap.erase(it_begin, it_end);  
}注意:在删除范围内的元素时,需要确保迭代器是有效的,并且it_end应该指向要删除范围之外的第一个元素的位置(因此需要对it_end的迭代器进行自增操作,但这里需要注意it_end可能是end()迭代器,此时不能自增)。然而,上面的代码示例在逻辑上是有问题的,因为find返回的是单个元素的迭代器,而不是一个可以表示范围的迭代器对。正确的做法应该是使用其他方式来确定要删除的范围,比如使用lower_bound和upper_bound函数。
map还提供了其他有用的成员函数,如:
size():返回map中元素的个数。empty():判断map是否为空。clear():清空map中的所有元素。count(const Key& key):返回键为key的元素个数(对于map来说,返回值只能是0或1,因为键是唯一的)。lower_bound(const Key& key)和upper_bound(const Key& key):分别返回指向第一个不小于(大于)key的元素的迭代器。equal_range(const Key& key):返回一个pair,表示key在map中的范围(即[lower_bound, upper_bound))。默认情况下,map中的元素会按照键的升序进行排序。如果需要自定义排序规则,可以在声明map时提供一个自定义的比较函数或比较类。例如:
struct Compare {  
    bool operator()(const int& a, const int& b) const {  
        return a > b; // 降序排序  
    }  
};  
  
map<int, string, Compare> myMap;在这个例子中,我们定义了一个比较类Compare,它重载了operator()来指定降序排序规则。然后,我们使用这个比较类来创建一个map对象myMap,它将按照降序对键进行排序。
#include <iostream>
using namespace std;
void test_map2() {
	map<string, string> dict;
	dict.insert(make_pair("string", "字符串"));
	dict.insert(make_pair("sort", "排序"));
	dict.insert(make_pair("insert", "插入"));
	// 不插入,不覆盖,只看key,右值value不相同无所谓
	dict.insert(make_pair("insert", "xxxxx"));
	auto it = dict.begin();
	while (it != dict.end()) {
		// cout << (*it).first << ":" << (*it).second;
		cout << it->first << ":" << it->second << " ";
		++it;
	}
	cout << endl;
	for (const auto& kv : dict) {
		cout << kv.first << ":" << kv.second << " ";
	}
}
// map.operator[],通过key,返回value
void test_map3() {
	// 统计次数
	string arr[] = { "西瓜", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };
	map<string, int> countmap;
	for (auto e : arr) {
		/*auto it = countmap.find(e);
		if (it == countmap.end()) {
			countmap.insert(make_pair(e, 1));
		}
		else {
			it->second++;
		}*/
		// value_type& operator[](const key_type k)
		countmap[e]++;
	}
	for (const auto& kv : countmap)
	{
		cout << kv.first << ":" << kv.second << endl;
	}
}
void test_map4()
{
	map<string, string> dict;
	dict.insert(make_pair("string", "字符串"));
	dict.insert(make_pair("sort", "排序"));
	dict.insert(make_pair("insert", "插入"));
	cout << dict["sort"] << endl; // 查找和读
	dict["map"];                  // 插入
	dict["map"] = "映射,地图";     // 修改
	dict["insert"] = "xxx";       // 修改
	dict["set"] = "集合";         // 插入+修改
	for (const auto& kv : dict){
		cout << kv.first << ":" << kv.second << endl;
	}
}
int main() {
	test_map2();
    cout << endl << endl;
    cout << endl << endl;
    
    test_map3();
    cout << endl << endl;
    cout << endl << endl;
    
    test_map4();
    cout << endl << endl;
    cout << endl << endl;
	return 0;
}综上所述,map在C++中是一个功能强大的容器,它提供了方便的键值对存储和查找功能,并且支持自定义排序规则。
在C++中,multimap是一个关联容器,它与map相似,但允许键值对中的键可以重复。以下是对multimap的定义与使用的详细介绍:
multimap的定义通常使用以下语法:
multimap<KeyType, ValueType> multimapName;其中,KeyType表示键的类型,ValueType表示值的类型,multimapName是multimap对象的名称。
例如,定义一个存储字符串到整数的映射的multimap:
multimap<string, int> myMultimap;向multimap中插入元素有多种方法,通常使用insert成员函数:
myMultimap.insert(pair<string, int>("key1", 100));或者:
myMultimap.insert(make_pair("key2", 200));由于multimap允许键重复,因此可以插入多个具有相同键的元素。
查找元素时,可以使用find成员函数,但需要注意的是,find函数只返回第一个找到的具有指定键的元素。如果需要查找所有具有相同键的元素,可以使用equal_range、lower_bound和upper_bound成员函数。
find成员函数:auto it = myMultimap.find("key1");  
if (it != myMultimap.end()) {  
    cout << "Found: " << it->first << " => " << it->second << endl;  
} else {  
    cout << "Key not found." << endl;  
}equal_range成员函数:返回一个pair,其中first成员是指向第一个不小于给定键的元素的迭代器,second成员是指向第一个大于给定键的元素的迭代器。这可以用于查找所有具有相同键的元素。auto range = myMultimap.equal_range("key1");  
for (auto it = range.first; it != range.second; ++it) {  
    cout << it->first << " => " << it->second << endl;  
}lower_bound和upper_bound成员函数:分别返回指向第一个不小于(大于)给定键的元素的迭代器。auto lb = myMultimap.lower_bound("key1");  
auto ub = myMultimap.upper_bound("key1");  
for (auto it = lb; it != ub; ++it) {  
    cout << it->first << " => " << it->second << endl;  
}可以使用迭代器来遍历multimap中的所有元素:
for (auto it = myMultimap.begin(); it != myMultimap.end(); ++it) {  
    cout << it->first << " => " << it->second << endl;  
}或者使用范围for循环(C++11及以上):
for (const auto& pair : myMultimap) {  
    cout << pair.first << " => " << pair.second << endl;  
}可以使用erase成员函数来删除元素:
myMultimap.erase("key1");auto it = myMultimap.find("key2");  
if (it != myMultimap.end()) {  
    myMultimap.erase(it); // 注意:这将只删除找到的第一个元素,如果有多个相同键的元素,需要额外处理  
}注意:上面的代码只会删除找到的第一个具有指定键的元素。如果需要删除所有具有相同键的元素,应该使用equal_range或lower_bound和upper_bound来找到所有相关元素,并逐个删除。
auto it_begin = myMultimap.lower_bound("key_start");  
auto it_end = myMultimap.upper_bound("key_end");  
myMultimap.erase(it_begin, it_end);multimap还提供了其他有用的成员函数,如:
size():返回multimap中元素的个数。empty():判断multimap是否为空。clear():清空multimap中的所有元素。count(const Key& key):返回键为key的元素个数(对于multimap来说,这个值可能大于1)。multimap中的元素是按照键的顺序存储的,默认情况下是按照键的升序进行排序。如果需要自定义排序规则,可以在声明multimap时提供一个自定义的比较函数或比较类。multimap允许键重复,因此在插入、查找和删除元素时需要特别注意处理多个相同键的情况。综上所述,multimap在C++中是一个功能强大的容器,它提供了方便的键值对存储和查找功能,并且支持自定义排序规则和处理多个相同键的情况。
最后,需要强调的是,虽然Map与Set提供了高效的数据管理方式,但在使用时仍需注意其性能特点和适用场景。只有深入了解并合理利用这些容器的特性,我们才能在程序中充分发挥它们的作用,实现更加高效、稳定的数据管理。希望本文能够为你提供有益的参考和帮助,让你在C++编程的道路上更加游刃有余。
今天的分享到这里就结束啦!如果觉得文章还不错的话,可以三连支持一下,17的主页还有很多有趣的文章,欢迎小伙伴们前去点评,您的支持就是17前进的动力!