目录
一、C++ STL 关联式容器
C++ 容器可以分为序列式容器和关联式容器，我们在前面的章节中对序列式容器（包括 array、vector、list、deque 和 forward_list）已经做了详细的介绍，下面，我们也将对 C++ STL 中的所有关联式容器做详细的介绍。
和序列式容器不同的是，使用关联式容器存储的元素都是一个一个的 "键值对"（<key, value>），并且使用关联式容器存储的元素默认会根据各元素的键值 key 的大小做升序排序。
由于不同的应用场景，C++ STL 实现了树形结构和哈希结构的关联式容器。树形结构的关联式容器（包括 map、set、multimap、multiset）使用了平衡搜索树（即红黑树）作为其底层结构；哈希结构的关联式容器（包括 unordered_map、unordered_set、unordered_multimap、unordered_multise）则使用了哈希表作为其底层结构。
二、pair 类模板
我们知道，关联式容器存储的是 "键值对" 形式的数据，因为 "键值对" 并不是普通数据类型，所以 C++ STL 提供了 pair 类模板，并将其定义在 <utility> 头文件中。
template < class T1, class T2 > struct pair; pair 类模板在 SGI-STL 版本中的实现：
#pragma once
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) {}
};
template<class T1, class T2>
inline bool operator==(const pair<T1, T2>& lhs, const pair<T1, T2>& rhs)
{
return lhs.first == rhs.first && lhs.second == rhs.second;
}
template<class T1, class T2>
inline bool operator!=(const pair<T1, T2>& lhs, const pair<T1, T2>& rhs)
{
return !(lhs == rhs);
}
template<class T1, class T2>
inline bool operator<(const pair<T1, T2>& lhs, const pair<T1, T2>& rhs)
{
return lhs.first < rhs.first ||
(!(rhs.first < lhs.first) && lhs.second < rhs.second);
}
template<class T1, class T2>
inline bool operator<=(const pair<T1, T2>& lhs, const pair<T1, T2>& rhs)
{
return !(rhs < lhs);
}
template<class T1, class T2>
inline bool operator>(const pair<T1, T2>& lhs, const pair<T1, T2>& rhs)
{
return rhs < lhs;
}
template<class T1, class T2>
inline bool operator>=(const pair<T1, T2>& lhs, const pair<T1, T2>& rhs)
{
return !(lhs < rhs);
}
template<class T1, class T2>
inline pair<T1, T2> make_pair(const T1& x, const T2& y)
{
return pair<T1, T2>(x, y);
}三、set
3.1 - set 的基本介绍
set 容器以类模板的形式定义在 <set> 头文件中，并位于 std 命名空间中。
template < class T, // set::key_type/value_type
class Compare = less<T>, // set::key_compare/value_compare
class Alloc = allocator<T> // set::allocator_type
> class set;set 是按照特定次序存储唯一元素的容器。
在 set 中，元素的 value 也标识它（value 就是 key，类型为 T），并且每个 value 必须是唯一的。set 中的元素不能在容器中修改（元素始终是 const），但可以在容器中插入或删除它们。
在内部，set 中的元素始终按照其内部比较对象（类型为 Compare）指定的特定严格弱序标准（strict weak ordering criterion）进行排序。
set 容器通过 key 访问单个元素的速度通常比 unorder_sort 容器慢，但是 set 容器允许根据子集的顺序直接迭代子集。
set 底层是用二叉搜索树（红黑树）实现的。
3.2 - set 的成员函数
3.1.1 - 构造函数
empty (1) explicit set(const key_compare& comp = key_compare(),
const allocator_type& alloc = allocator_type());
range (2) template<class InputIterator>
set <InputIterator first, InputIterator last,
const key_compare& comp = key_compare(),
const allocator_type& alloc = allocator_type()>;
copy (3) set(const set& x);-
默认构造函数：构造一个没有元素的空容器。
-
范围构造函数：用 [first, last) 区间中的元素构造一个容器。
-
拷贝构造函数。
3.1.2 - 迭代器
示例：
#include <set>
#include <iostream>
using namespace std;
int main()
{
int arr[] = { 75, 23, 65, 42, 13 };
int sz = sizeof(arr) / sizeof(arr[0]);
set<int> s(arr, arr + sz);
set<int>::iterator it = s.begin();
while (it != s.end())
{
// *it = 0; // error
cout << *it << " ";
++it;
}
// 13 23 42 65 75
cout << endl;
set<int>::reverse_iterator rit = s.rbegin();
while (rit != s.rend())
{
// *rit = 0; // error
cout << *rit << " ";
++rit;
}
// 75 65 42 23 13
cout << endl;
return 0;
}注意：set 容器的迭代器类型为双向迭代器，并且 iterator 等价于 const_iterator，reverse_iterator 等价于 const_reverse_iterator。
这样就避免修改 set 容器中的元素。
3.1.3 - 修改操作
single element (1) pair<iterator, bool> insert(const value_type& val);
with hint (2) iterator insert(iterator position, const value_type& val);
range (3) template<class InputIterator>
void insert(InputIterator first, InputIterator last);注意：在 set 中插入 val，实际上插入的是 <val, val> 构成的键值对。
因为 set 中的元素都是唯一的，所以在插入操作中会检查每个插入的元素是否重复，如果是，则不插入该元素。
而允许插入重复元素的类似容器是 multiset。
返回值：
如果插入成功，即插入的元素不重复，返回
pair<指向新插入的元素的迭代器, true>；如果插入失败，即插入的元素重复，返回pair<指向 set 中已有的等效元素的迭代器, false>。返回一个迭代器，它指向新插入的元素，或者指向 set 中已有的等效的元素。
(1) void erase(iterator position);
(2) size_type erase(const value_type& val);
(3) void erase(iterator first, iterator last);swap：
void swap(set& x);void clear();示例：
#include <set>
#include <iostream>
using namespace std;
int main()
{
set<int> s;
s.insert(75);
s.insert(23);
s.insert(65);
s.insert(42);
cout << s.insert(13).second << endl; // 1（说明插入成功）
cout << s.insert(13).second << endl; // 0（说明插入失败）
cout << s.size() << endl; // 5
for (const auto& e : s)
{
cout << e << " ";
}
// 13 23 42 65 75
cout << endl;
return 0;
}3.1.4 - 其他操作
find：
iterator find(const value_type& val) const;size_type count(const value_type& val) const;返回 set 中值为 val 的元素的个数。
因为 set 中的元素都是唯一的，所以返回值只能是 1（元素找到了） 或 0（元素没找到）。
iterator lower_bound(const value_type& val) const;iterator upper_bound(const value_type& val) const;pair<iterator, iterator> equal_range(const value_type& val) const;因为 set 中的元素都是唯一的，所以返回的范围中最多包含一个元素。
示例：
#include <set>
#include <iostream>
using namespace std;
int main()
{
set<int> s;
for (int i = 1; i < 10; ++i)
{
s.insert(i * 10);
}
set<int>::iterator pos = s.find(10);
if (pos != s.end())
s.erase(pos);
if (s.count(20)) // 等价于 s.find(20) != s.end()
cout << "元素找到了" << endl;
else
cout << "元素不存在" << endl;
// 元素找到了
// lower_bound 返回指向第一个 >= val 的元素的迭代器
set<int>::iterator itlow = s.lower_bound(30);
// upper_bound 返回指向第一个 > val 的元素的迭代器
set<int>::iterator itup = s.upper_bound(60);
cout << *itlow << endl; // 40
cout << *itup << endl; // 70
s.erase(itlow, itup);
for (const auto& e : s)
{
cout << e << " ";
}
// 20 70 80 90
cout << endl;
cout << *s.equal_range(20).first << endl; // 20
cout << *s.equal_range(20).second << endl; // 70
return 0;
}四、map
4.1 - map 的基本介绍
map 容器以类模板的形式定义在 <map> 头文件中，并位于 std 命名空间中。
template < class Key, // map::key_type
class T, // map::mapped_type
class Compare = less<Key>, // map::key_compare
class Alloc = allocator<pair<const Key,T> > // map::allocator_type
> class map;map 是关联式容器，它按照特定次序存储由键值 key 和值 value 组合而成的元素。
在 map 中，key 用于排序和唯一地标识元素，而 value 中存储与此 key 关联的内容。key 和 value 的类型可能不同，它们通过成员类型 value_type 绑定在一起：
typedef pair<const Key, T> value_type;在内部，map 中的元素始终按照其内部比较对象（类型为 Compare）指定的严格弱排序标准（strict weak ordering criterion）通过 key 进行排序。
map 容器通过 key 访问单个元素的速度通常比 unordered_map 容器慢，但它允许根据子集的顺序直接迭代子集。
使用 [] 可以直接通过 key 找到对应的 value。
map 底层是用二叉树搜索树（红黑树）实现的。
4.2 - map 的成员函数
4.2.1 - 迭代器
示例：
#include <map>
#include <iostream>
using namespace std;
int main()
{
map<string, string> dict;
pair<string, string> kv("insert", "插入");
dict.insert(kv);
dict.insert(pair<string, string>("erase", "删除"));
dict.insert(make_pair("find", "查找"));
dict.insert({ "map", "地图;映射" }); // 多参数的构造函数的隐式类型转换
auto it = dict.begin();
while (it != dict.end())
{
// (*it).first = "xxx"; // error
// (*it).second = "yyy"; // ok
// cout << (*it).first << " : " << (*it).second << endl;
// 或者：
cout << it->first << " : " << it->second << endl;
// 为了可读性，编译器将 it->->first/second 优化成了 it->first/second
++it;
}
cout << endl;
auto rit = dict.rbegin();
while (rit != dict.rend())
{
cout << rit->first << " : " << rit->second << endl;
++rit;
}
return 0;
}map 容器的迭代器类型为双向迭代器。
4.2.2 - operator[]
mapped_type& operator[](const key_type& k);-
如果 k 与容器中的某个元素的 key 匹配，函数则返回该元素的 key 对应的 value 的引用。
-
如果 k 与容器中所有元素的 key 都不匹配，函数则将插入键值为 k 的新元素，并返回其对应的 value 的引用（使用默认构造函数构造出来的）。
即：
mapped_type& operator[](const key_type& k)
{
std::pair<iterator, bool> x = insert(make_pair(k, mapped_type()));
return x.first->second;
}示例：
#include <map>
#include <iostream>
using namespace std;
int main()
{
string fruits[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜",
"苹果", "香蕉", "苹果", "香蕉" };
map<string, int> countMap;
for (const auto& e : fruits)
{
++countMap[e];
}
for (const auto& e : countMap)
{
cout << e.first << " : " << e.second << endl;
}
// 苹果 : 6
// 西瓜: 3
// 香蕉 : 2
return 0;
}五、multiset
multiset 容器以类模板的形式定义在 <set> 头文件中，并位于 std 命名空间中。
template < class T, // multiset::key_type/value_type
class Compare = less<T>, // multiset::key_compare/value_compare
class Alloc = allocator<T> > // multiset::allocator_type
> class multiset;和 set 容器不同的是，multiset 容器中的元素可以重复。
示例：
#include <set>
#include <iostream>
using namespace std;
int main()
{
multiset<int> s;
s.insert(5);
s.insert(3);
s.insert(8);
s.insert(7);
s.insert(7);
s.insert(9);
s.insert(7);
for (const auto& e : s)
{
cout << e << " ";
}
// 3 5 7 7 7 8 9
cout << endl;
cout << s.count(7) << endl; // 3
auto ret = s.equal_range(7);
auto itlow = ret.first;
auto itup = ret.second;
cout << *itlow << endl; // 7
cout << *itup << endl; // 8
s.erase(itlow, itup);
for (const auto& e : s)
{
cout << e << " ";
}
// 3 5 8 9
cout << endl;
return 0;
}六、multimap
multimap 容器以类模板的形式定义在 <map> 头文件中，并位于 std 命名空间中。
template < class Key, // multimap::key_type
class T, // multimap::mapped_type
class Compare = less<Key>, // multimap::key_compare
class Alloc = allocator<pair<const Key,T> > // multimap::allocator_type
> class multimap;和 map 容器不同的是，mutimap 容器中的元素的 key 可以是重复的，因此 multimap 没有重载 operator[]。
示例：
#include <map>
#include <iostream>
using namespace std;
int main()
{
multimap<string, int> info;
info.insert(make_pair("张三", 18));
info.insert(make_pair("李四", 20));
info.insert(make_pair("王五", 19));
info.insert(make_pair("张三", 30));
for (const auto& e : info)
{
cout << e.first << " : " << e.second << endl;
}
// 李四 : 20
// 王五: 19
// 张三 : 18
// 张三 : 30
return 0;
}七、相关练习
7.1 - 有效的括号
class Solution {
public:
bool isValid(string s) {
stack<char> st;
map<char, char> matchMap;
matchMap['('] = ')';
matchMap['['] = ']';
matchMap['{'] = '}';
for (const auto& ch : s)
{
if (matchMap.count(ch))
{
st.push(ch); // 左括号入栈
}
else
{
if (st.empty())
return false;
if (ch != matchMap[st.top()]) // 右括号去匹配栈顶的左括号
return false;
else
st.pop();
}
}
return st.empty();
}
};7.2 - 复制带随机指针的链表
class Solution {
public:
Node* copyRandomList(Node* head) {
Node* cur = head;
Node* copyHead = nullptr;
Node* copyTail = copyHead;
map<Node*, Node*> curCopyMap;
while (cur)
{
Node* copy = new Node(cur->val);
curCopyMap[cur] = copy;
if (copyHead == nullptr)
{
copyHead = copyTail = copy;
}
else
{
copyTail->next = copy;
copyTail = copyTail->next;
}
cur = cur->next;
}
cur = head;
copyTail = copyHead;
while (cur)
{
if (cur->random == nullptr)
{
copyTail->random = nullptr;
}
else
{
copyTail->random = curCopyMap[cur->random];
}
cur = cur->next;
copyTail = copyTail->next;
}
return copyHead;
}
};7.3 - 两个数组的交集
class Solution {
public:
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
// 去重
set<int> s1(nums1.begin(), nums1.end());
set<int> s2(nums2.begin(), nums2.end());
// 求交集
vector<int> ret;
set<int>::iterator it1 = s1.begin();
set<int>::iterator it2 = s2.begin();
while (it1 != s1.end() && it2 != s2.end())
{
if (*it1 < *it2)
{
++it1;
}
else if (*it2 < *it1)
{
++it2;
}
else
{
ret.push_back(*it1);
++it1;
++it2;
}
}
return ret;
}
};拓展：如何求
nums1和nums2的差集？首先仍然是去重，然后和求交集不同的是，当按序比较两个数组中的元素时，值较小的元素属于差集，相等的两个元素则跳过。
7.4 - 前K个高频单词
class Solution {
public:
struct Greater
{
bool operator()(const pair<string, int>& lhs, const pair<string, int>& rhs)
{
return lhs.second > rhs.second;
}
};
vector<string> topKFrequent(vector<string>& words, int k)
{
map<string, int> countMap;
for (const auto& e : words)
{
++countMap[e];
}
vector<pair<string, int>> v(countMap.begin(), countMap.end());
// 注意：
// 因为 v 已经按字典顺序排好序了，
// 所以此时只需要按单词出现的频率由高到低进行（稳定）排序即可。
stable_sort(v.begin(), v.end(), Greater());
vector<string> ret;
for (int i = 0; i < k; ++i)
{
ret.push_back(v[i].first);
}
return ret;
}
};因为 map 的迭代器类型为双向迭代器，无法使用 sort，所以只能借助 vector 进行排序。
又因为当不同的单词有相同的出现频率时，按字典顺序排序，所以必须使用稳定排序，即 stable_sort。
