【重走C++学习之路】18、map和set

一、关联式容器

二、键值对

三、树形结构的关联式容器

3.1 set

1. set的构造函数

2. set的迭代器

3. set的容量操作

4. set的增删查操作

3.2 map

1. map的构造函数

2. map的迭代器

3. map的容量操作

4. map的增删查操作

5. operator[]

3.3 multiset

3.4 multimap

四、利用红黑树实现map和set

4.1 红黑树的改造

1. 红黑树的基本结构

2. 红黑树的迭代器类实现

3. 改造后的结构

4.2 封装map和set

结语

一、关联式容器

关联式容器是一种基于键组织数据的容器，通过键快速访问元素，与序列式容器（如 vector、list）的顺序存储不同，其里面存储的是<key, value>结构的键值对，在数据检索时比序列式容器效率更高。关联式容器分为有序和无序两类，有序的是基于红黑树的树形有序关联式容器，无序的是基于哈希表的无序关联式容器。

关联式容器适用于需要快速查找、键值映射或有序管理数据的场景：

有序容器：适合需要范围查询或顺序遍历的场景（如日志按时间排序）。

无序容器：适合高频单点查询（如缓存、哈希表去重）。
根据键的唯一性、排序需求和性能要求选择合适的容器类型。

二、键值对

用来表示具有一一对应关系的一种结构，该结构中一般只包含两个成员变量key和value，key代表键值，value表示与key对应的信息。

STL中pair的定义：

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

一般的两种方式创建键值对对象：

pair<T1, T2>(x, y) ，使用构造函数的方式构造一个匿名对象

make_pair(x, y) 是一个函数模板，其中返回的是一个pair的匿名对象

三、树形结构的关联式容器

STL总共实现了两种不同结构的管理式容器：树型结构与哈希结构。树型结构的关联式容器主要有四种：map、set、multimap、multiset。这四种容器的共同点是：使用平衡搜索树(即红黑树)作为其底层结果，容器中的元素是一个有序的序列。

3.1 set

std::set是一个基于红黑树实现的有序关联容器，用于存储唯一且按严格弱序排列的元素集合。

主要特点：

set是按照一定次序存储元素的容器
在set中，元素的value也标识它(value就是key，类型为T)，并且每个value必须是唯一的。set中的元素不能在容器中修改(元素总是const)，但是可以从容器中插入或删除它们。
在内部，set中的元素总是按照其内部比较对象(类型比较)所指示的特定严格弱排序准则进行排序。
set容器通过key访问单个元素的速度通常比unordered_set容器慢，但它们允许根据顺序对子集进行直接迭代。
set在底层是用二叉搜索树(红黑树)实现的。

1. set的构造函数

构造函数

构造空的set对象

拷贝构造函数

利用set对象构造新的set对象

迭代器构造

利用迭代器将set中的某个区间来构造新的set对象

2. set的迭代器

迭代器的出现是为了统一容器之间的遍历接口，因此每个容器的迭代器接口都是一致的，set也是如此，因此就不在这里在介绍了。

3. set的容量操作

empty

判断set是否为空

size

返回set中元素的个数

4. set的增删查操作

insert

在set中插入元素x，实际插入的是<x, x>构成的键值对，如果插入成功，返回<该元素在set中的位置，true>，如果插入失败，说明x在set中已经存在，返回<x在set中的位置，false>

erase

删除set中position位置上的元素

clear

将set中的元素清空

find

查找某个元素。这里find的时间复杂度为O(logN)，比算法中的find（时间复杂是O(N)）更高效，所以set容器一般是由自己的find进行查找。

示例：

void TestSet()
{set<int> s;s.insert(12);s.insert(9);s.insert(6);s.insert(16);s.insert(13);s.insert(s.begin(), 10);set<int>::iterator pos = s.find(15);// 底层是搜索二叉树，时间复杂度是O(logN)if (pos != s.end()){s.erase(pos);    // 没有会报错}//s.erase(1); // 没找到不会报错set<int>::iterator it = s.begin();while (it != s.end()){cout << *it << " ";++it;}cout << endl;for (auto e : s){cout << e << " ";}cout << endl;
}

3.2 map

主要特点：

map是关联容器，它按照特定的次序(按照key来比较)存储由键值key和值value组合而成的元素。
在map中，键值key通常用于排序和惟一地标识元素，而值value中存储与此键值key关联的内容。键值key和值value的类型可能不同，并且在map的内部，key与value通过成员类型value_type绑定在一起，为其取别名称为pair:typedef pair<const key, T>value_type;
在内部，map中的元素总是按照键值key进行比较排序的。
map中通过键值访问单个元素的速度通常比unordered_map容器慢，但map允许根据顺序对元素进行直接迭代(即对map中的元素进行迭代时，可以得到一个有序的序列)。
map支持下标访问符，即在[]中放入key，就可以找到与key对应的value。
map底层为平衡二叉搜索树(红黑树)。

1. map的构造函数

构造函数

构造空的map对象

拷贝构造函数

利用map对象构造新的set对象

迭代器构造

利用迭代器将map中的某个区间来构造新的set对象

2. map的迭代器

迭代器接口与set一致，也和其它的容器一致，这里就不介绍了。

3. map的容量操作

empty

判断map是否为空

size

返回map中元素的个数

4. map的增删查操作

insert

在map中插入键值对x，返回值也是键值对：iterator代表新插入元素的位置，bool代表释放插入成功

erase

删除position位置上的元素

clear

将map中的元素清空

find

在map中查找key为x的元素，找到返回该元素的位置的const迭代器，否则返回一个迭代器map::end

5. operator[]

其中，mapped_type是KV模型中V的类型，也就是返回value值的引用。我们可以对这个value进行修改。
分析：((this->insert(make_pair(k,mapped_type()))).first这是一个迭代器，迭代器指向键值对中的第二个元素就是value。所以operato[]的底层是用到了插入，同时可以对value进行修改和访问。
总结： operator[]的三个用处：插入、修改和访问。

示例：

void TestMap1()
{map<string, int> countMap;string fruitArray[] = {"西瓜", "桃子", "橘子", "桃子", "苹果", "西瓜", "香蕉", "苹果", "香蕉", "西瓜", "桃子", "西瓜", "橘子", "桃子", "橘子", "桃子", "西瓜", "桃子", "香蕉", "桃子", "苹果", "西瓜" };// 方法一for (auto& e : fruitArray){map<string, int>::iterator ret = countMap.find(e);if (ret != countMap.end())// 找到了，说明容器里有，第二个参数加1即可{++ret->second;}else{// 没有就插入，第二个参数记为1countMap.insert(make_pair(e, 1));}}// 方法二for (auto& e : fruitArray){	// countMap无此元素，pair的第一个参数返回新的迭代器，第二个参数返回true// countMap有此元素，pair的第一个参数返回旧的迭代器，第二个参数返回falsepair<map<string, int>::iterator, bool> ret = countMap.insert(make_pair(e, 1));// 插入失败，只需要++value即可 if (ret.second == false){++ret.first->second;}}// 方法三for (auto& e : fruitArray){countMap[e]++;// 有插入、查找和修改的功能   返回value的值的引用 }countMap["哈密瓜"];        // 插入countMap["哈密瓜"] = 5;    // 修改cout << countMap["哈密瓜"] << endl;// 查找  // 一般不用operator[]来进行查找，没找到会进行插入从而打乱表的内容countMap["橙子"] = 3;    // 插入+修改for (auto& e : countMap){cout << e.first << ":" << e.second << endl;}
}

3.3 multiset

主要特点：

multiset是按照特定顺序存储元素的容器，其中元素是可以重复的。
在multiset中，元素的value也会识别它(因为multiset中本身存储的就是<value, value>组成的键值对，因此value本身就是key，key就是value，类型为T)。multiset元素的值不能在容器中进行修改(因为元素总是const的)，但可以从容器中插入或删除。
在内部，multiset中的元素总是按照其内部比较规则(类型比较)所指示的特定严格弱排序准则进行排序。
multiset容器通过key访问单个元素的速度通常比unordered_multiset容器慢，但当使用迭代器遍历时会得到一个有序序列。
multiset底层结构为二叉搜索树(红黑树)。

void TestMultiSet()
{int array[] = { 2, 1, 3, 9, 6, 0, 5, 8, 4, 7, 6, 10, 3, 2, 7, 9, 8};// 注意：multiset在底层实际存储的是<int, int>的键值对multiset<int> ms(array, array + sizeof(array)/sizeof(array[0]));for (auto& e : s)cout << e << " ";cout << endl;
}

3.4 multimap

主要特点：

Multimaps是关联式容器，它按照特定的顺序，存储由key和value映射成的键值对<key,value>，其中多个键值对之间的key是可以重复的。
在multimap中，通常按照key排序和唯一地标识元素，而映射的value存储与key关联的内容。key和value的类型可能不同，通过multimap内部的成员类型value_type组合在一起，value_type是组合key和value的键值对:typedef pair<const Key, T> value_type;
在内部，multimap中的元素总是通过其内部比较对象，按照指定的特定严格弱排序标准对key进行排序的。
multimap通过key访问单个元素的速度通常比unordered_multimap容器慢，但是使用迭代器直接遍历multimap中的元素可以得到关于key有序的序列。
multimap在底层用二叉搜索树(红黑树)来实现。

注意：multimap和map的唯一不同就是：map中的key是唯一的，而multimap中key是可以
重复的

void TestMultiMap()
{// multimap 和 map 的区别：可以有不同的key // 不支持operator[]  因为有多个key时，不知道返回哪个key对应的value的引用multimap<int, int> mm;mm.insert(make_pair(1, 1));mm.insert(make_pair(1, 2));mm.insert(make_pair(1, 3));mm.insert(make_pair(2, 1));mm.insert(make_pair(2, 2));for (auto& e : mm){cout << e.first << ":" << e.second << endl;}}

四、利用红黑树实现map和set

4.1 红黑树的改造

1. 红黑树的基本结构

template<class K, class V>
class RBTree
{typedef RBTreeNode<K, V> Node;
private:Node* _root = nullptr;
};

可以看到红黑树是一种KV模型的二叉搜索树，想用一颗红黑树的结构同时实现K模型的set和KV模型的map，势必要对红黑树进行改造，利用仿函数统一接口，实现结点中的取值操作。

template<class K, class V>
class map
{struct MAPOFV{const K& operator()(const pair<K, V>& kv){return kv.first;}};
};template<class K>
class set
{struct SETOFV{const K& operator()(const K& key){return key;}};
};

在这里我们定义出了一个特有的类，方便取出结点中的数据。

2. 红黑树的迭代器类实现

template<class T, class Ptr, class Ref>
struct __rbtree_iterator
{typedef __rbtree_iterator<T, Ptr, Ref> Self;typedef RBTreeNode<T> Node;Node* _node;__rbtree_iterator(Node* node):_node(node){}// 返回值（data）的地址Ptr operator->(){return &_node->_data;}// 返回值（data）的引用Ref operator*(){return _node->_data;}// 实现左中右的中序遍历Self& operator++(){// 1.先判断右子树是否为空，不为空就去右子树找最左节点// 2.右子树为空，去找孩子是其左孩子的祖先Node* cur = _node;if (cur->_right){cur = cur->_right;while (cur->_left){cur = cur->_left;}}else{Node* parent = cur->_parent;while (parent && parent->_right == cur){cur = parent;parent = parent->_parent;}cur = parent;}_node = cur;return *this;}// 实现右中左的中序遍历Self& operator--(){// 1.先判断左子树是否为空，不为空就去左子树找最右节点// 2.右子树为空，去找孩子是其右孩子的祖先Node* cur = _node;if (cur->_left){cur = cur->_left;while (cur->_right){cur = cur->_right;}}else{Node* parent = cur->_parent;while (parent && parent->_left == cur){cur = parent;parent = parent->_parent;}cur = parent;}_node = cur;return *this;}bool operator!=(const Self& s){return _node != s._node;}
};

3. 改造后的结构

template<class K, class T, class KOFV>
class RBTree
{typedef RBTreeNode<T> Node;public:typedef __rbtree_iterator<T, T*, T&> iterator;typedef __rbtree_iterator<T, const T*, const T&> const_iterator;iterator begin(){Node* cur = _root;while (cur && cur->_left){cur = cur->_left;}return iterator(cur);}iterator end(){return iterator(nullptr);}iterator begin() const{Node* cur = _root;while (cur && cur->_left){cur = cur->_left;}return const_iterator(cur);}iterator end() const{return const_iterator(nullptr);}private:Node* _root = nullptr;
};

这里第二个参数变成了T，这个T可以是pair<K,V>也可以是K，让T来做节点中的数据类型，然后用第三个参数取出T中的K来进行取数的操作。

具体的增删查操作在上一篇博客中，有需要的可以去查看【重走C++学习之路】17、红黑树，只需要将其中的数值对比部分加上取数的操作，例如：

data < cur->data 变为 kofv(data) < kofv(cur->_data)，其中kofv为KOFV的一个实例化对象

4.2 封装map和set

template<class K, class V>
class map
{struct MAPOFV{const K& operator()(const pair<K, V>& kv){return kv.first;}};typedef RBTree<K, pair<K, V>, MAPOFV> RBTree;public:// typename 告诉编译器这只是一个名字，暂时不用堆模板进行实例化typedef typename RBTree::iterator iterator;typedef typename RBTree::const_iterator const_iterator;iterator begin(){return _rbt.begin();}iterator end(){return _rbt.end();}const_iterator begin() const{return _rbt.begin();}const_iterator end() const{return _rbt.end();}pair<iterator, bool> insert(const pair<K, V>& kv){return _rbt.Insert(kv);}bool erase(const K& key){return _rbt.Erase(key);}V& operator[](const K& key){pair<iterator, bool> ret = insert(make_pair(key, V()));return ret.first->second;}private:RBTree _rbt;
};template<class K>
class set
{struct SETOFV{const K& operator()(const K& key){return key;}};typedef RBTree<K, K, SETOFV> RBTree;public:// typename 告诉编译器这只是一个名字，暂时不用堆模板进行实例化typedef typename RBTree::iterator iterator;typedef typename RBTree::const_iterator const_iterator;iterator begin(){return _rbt.begin();}iterator end(){return _rbt.end();}const_iterator begin() const{return _rbt.begin();}const_iterator end() const{return _rbt.end();}pair<iterator, bool> insert(const K& key){return _rbt.Insert(key);}bool erase(const K& key){return _rbt.Erase(key);}private:RBTree _rbt;
};