一、C++ STL 关联式容器

二、pair 类模板

三、set

3.1 - set 的基本介绍

3.2 - set 的成员函数

3.1.1 - 构造函数

3.1.2 - 迭代器

3.1.3 - 修改操作

3.1.4 - 其他操作

四、map

4.1 - map 的基本介绍

4.2 - map 的成员函数

4.2.1 - 迭代器

4.2.2 - operator[]

五、multiset

六、multimap

七、相关练习

7.1 - 有效的括号

7.2 - 复制带随机指针的链表

7.3 - 两个数组的交集

7.4 - 前K个高频单词

一、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_typeclass Compare = less<T>,        // set::key_compare/value_compareclass 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;  // errorcout << *it << " ";++it;}// 13 23 42 65 75cout << endl;
set<int>::reverse_iterator rit = s.rbegin();while (rit != s.rend()){// *rit = 0;  // errorcout << *rit << " ";++rit;}// 75 65 42 23 13cout << endl;return 0;
}

注意：set 容器的迭代器类型为双向迭代器，并且 iterator 等价于 const_iterator，reverse_iterator 等价于 const_reverse_iterator。

这样就避免修改 set 容器中的元素。

3.1.3 - 修改操作

insert：

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 中已有的等效的元素。

erase：

(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);

clear：

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;  // 5for (const auto& e : s){cout << e << " ";}// 13 23 42 65 75cout << endl;return 0;
}

3.1.4 - 其他操作

find：

iterator find(const value_type& val) const;

count：

size_type count(const value_type& val) const;

返回 set 中值为 val 的元素的个数。

因为 set 中的元素都是唯一的，所以返回值只能是 1（元素找到了）或 0（元素没找到）。

lower_bound：

iterator lower_bound(const value_type& val) const;

upper_bound：

iterator upper_bound(const value_type& val) const;

equal_range：

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;elsecout << "元素不存在" << 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;  // 40cout << *itup << endl;  // 70s.erase(itlow, itup);for (const auto& e : s){cout << e << " ";}// 20 70 80 90cout << endl;
cout << *s.equal_range(20).first << endl;  // 20cout << *s.equal_range(20).second << endl;  // 70return 0;
}

四、map

4.1 - map 的基本介绍

map 容器以类模板的形式定义在 <map> 头文件中，并位于 std 命名空间中。

template < class Key,                                     // map::key_typeclass T,                                       // map::mapped_typeclass Compare = less<Key>,                     // map::key_compareclass 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// 香蕉 : 2return 0;
}

五、multiset

multiset 容器以类模板的形式定义在 <set> 头文件中，并位于 std 命名空间中。

template < class T,                        // multiset::key_type/value_typeclass Compare = less<T>,        // multiset::key_compare/value_compareclass 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 9cout << endl;
cout << s.count(7) << endl;  // 3
auto ret = s.equal_range(7);auto itlow = ret.first;auto itup = ret.second;cout << *itlow << endl;  // 7cout << *itup << endl;  // 8s.erase(itlow, itup);for (const auto& e : s){cout << e << " ";}// 3 5 8 9cout << endl;return 0;
}

六、multimap

multimap 容器以类模板的形式定义在 <map> 头文件中，并位于 std 命名空间中。

template < class Key,                                     // multimap::key_typeclass T,                                       // multimap::mapped_typeclass Compare = less<Key>,                     // multimap::key_compareclass 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// 张三 : 30return 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;elsest.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;}
};