C++：map 和 set 的使用

前言

平衡二叉搜索树 ( AVL树 )

由于二叉搜索树在特殊情况下，其增删查的效率会降低到 O ( N )，因此对二叉搜索树进行改良，通过旋转等方式将其转换为一个左右均衡的二叉树，这样的树就称为平衡二叉搜索树，又称 AVL树。

红黑树

而红黑树又是一种特化的 AVL 树，都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡，从而获得较高的查找性能。虽然复杂的，但其最坏情况运行时间也是非常良好的，并且在实践中是高效的。

map 和 set 简介

map 和 set 底层就是红黑树。

set 是 key 搜索场景的结构， map 是key/value搜索场景的结构。

此外，map 和 set 还分为允许重复值和不允许重复值：set 和 multiset 是不允许重复值和允许重复值的 set 容器；map 和 multimap 是不允许重复值和允许重复值的 map 容器。

set 系列的使用

T 就是 set 底层关键字的类型，T ⽀持小于比较，如果需要可以自行实现仿函数传给第⼆个模版参数。

set 的迭代器 ( begin( ) 和 end( ) )

迭代器遍历是走的搜索树的中序，所以是有序的。

要注意的是，set 的迭代器不允许修改，其底层结构为二叉搜索树，不支持修改。

set 的 insert ( )

支持插入单个值，一段迭代器区间的值，或在某个位置插入一个值。

set<int> s;
s.insert(7);
s.insert(5);
s.insert(9);
s.insert(6);
s.insert(10);set<int>::iterator it = s.begin();
s.insert(it, 16);int arr[] = { 3,6,15,7,1 };
s.insert(arr, arr + 5);for (auto x : s)
{cout << x << " ";
}
cout << endl;

set 的 erase ( )

删除某个值，或一段迭代器区间内的值。

set<int> s;
s.insert(7);
s.insert(5);
s.insert(9);
s.insert(6);
s.insert(10);set<int>::iterator it = s.begin();
s.insert(it, 16);int arr[] = { 3,6,15,7,1 };
s.insert(arr, arr + 5);for (auto x : s)
{cout << x << " ";
}
cout << endl;s.erase(5);for (auto x : s)
{cout << x << " ";
}
cout << endl;s.erase(++s.begin(), --s.end());for (auto x : s)
{cout << x << " ";
}
cout << endl;

set 的 find ( )

找某个值所对应的位置，并返回该位置的迭代器。

multiset 和 set 的区别

multiset 允许重复值的出现，因此在删除某个值时，如果该值有多个，会全部删除。

multiset<int> s;s.insert(7);
s.insert(5);
s.insert(9);
s.insert(6);
s.insert(10);set<int>::iterator it = s.begin();
s.insert(it, 16);int arr[] = { 3,6,15,7,1 };
s.insert(arr, arr + 5);for (auto x : s)
{cout << x << " ";
}
cout << endl;s.erase(6);for (auto x : s)
{cout << x << " ";
}
cout << endl;

map 系列的使用

Key 就是 map 底层关键字的类型，T 是 map 底层 value 的类型，set 默认要求 Key ⽀持小于比较，如果需要的话可以自行实现仿函数传给第⼆个模版参数。

pair 类简介

在 map 中，pair 类的使用很常见。其有两个参数，first 和 second ，其支持各种类型。

经常使用的是 pair 的构造函数和其实现的 make_pair( ) 方法。

构造函数

// 构造函数
pair<string, string> p("hello", "你好");
// 匿名函数
pair<string, string>("hello", "你好");

make_pair ( )

使用 make_pair ( ) 方法通过传两个参数就可以构造一个 pair( ) 对象。

pair<string, string> p;// 使用 make_pair() 方法
p = make_pair("你好", "hello");

map 中 pair 的使用

在 map 中，许多函数的返回值是 pair ，且 map 中的 key 和 value 也用 pair 进行了封装。

具体来说，map 的元素类型是 pair<K , T >，其中 K 是 key 的类型，T 是 vlaue 的类型。

map 的迭代器 ( begin( ) 和 end( ) )

由于迭代器遍历走的是中序，所以是按 key 有序顺序遍历的。

由于 map 使用 pair 进行了封装，所以迭代器在使用时要用 -> 来访问 key 和 value 。要注意 map 中的 key 是不能修改的，所以无论是普通迭代器还是 const 迭代器访问，无论是什么类型，其迭代器的第一个参数 first (也就是 key )，是不允许修改的。

map 的 insert ( )

可以看到，insert 的返回值和形参都是 pair 类型。但传参时也可以直接走隐式类型转换。

map<string, string> m;pair<string, string> p1("insert", "插入");
m.insert(p1);// 匿名pair
m.insert(pair<string, string>{ "erase", "删除" });// 使用 make_pair 
m.insert(make_pair("find", "查找"));// 隐式类型转换
m.insert({ "sort","排序" });map<string, string>::iterator it = m.begin();
while (it != m.end())
{cout << it->first << " : " << it->second << endl;it++;
}

map 的 erase ( )

其支持迭代器位置的删除、根据 key 值删除，以及迭代器区间删除。

map<string, string> m;pair<string, string> p1("insert", "插入");
m.insert(p1);// 匿名pair
m.insert(pair<string, string>{ "erase", "删除" });// 使用 make_pair 
m.insert(make_pair("find", "查找"));// 隐式类型转换
m.insert({ "sort","排序" });m.erase("erase");for (auto& x : m)
{cout << x.first << " : " << x.second << endl;
}

map 的 find ( )

用于根据 key 值查找位置，并返回一个迭代器。

map 的 operator [ ]

map 重载了 [ ] ，其功能十分强大，在 [ ] 内给定 key ，其会在 map 中进行查找，如果存在，返回其 value ，如果不存在，其会将其当作新元素插入 map 中，且其能修改 key 对应的 value 的值。

map<string, string> m;pair<string, string> p1("insert", "插入");
m.insert(p1);// 匿名pair
m.insert(pair<string, string>{ "erase", "删除" });// 使用 make_pair 
m.insert(make_pair("find", "查找"));// 隐式类型转换
m.insert({ "sort","排序" });m.erase("erase");for (auto& x : m)
{cout << x.first << " : " << x.second << endl;
}
cout << endl;m["sort"] = "排序，种类";
for (auto& x : m)
{cout << x.first << " : " << x.second << endl;
}
cout << endl;m["erase"] = "删除";
m["left"] = "左边";
for (auto& x : m)
{cout << x.first << " : " << x.second << endl;
}
cout << endl;