前言

前面花了很多篇幅介绍红黑树的原理及其在 STL 中的实现。在 STL 中，红黑树不作为一种容器对外开放，而是作为 set 以及 map 的底层容器而使用，本节就将依次介绍它们。

set

set 的特性是，所有元素都会根据元素的键值自动被排序。set 的元素不像 map 那样可以同时拥有实值（value）和键值（key），set元素的键值就是实值，实值就是键值。set不允许两个元素有相同的键值。

由于 set 的元素值就是其键值，关系到 set 元素的排列规则，因此 set<T>::iterator 被定义为底层 RB-tree 的 const_iterator，杜绝写入操作。

STL 特别提供了一组 set/multiset 相关算法，包括交集 set_intersection 、联集 set_union、差集 set_difference 、对称差集set_synmetric_difference，会在介绍到算法部分时再做介绍。

由于 RB-tree 是一种平衡二叉搜索树，自动排序的效果很不错，所以标准的 STLset 即以 RB-tree 为底层机制。又由于 set 所开放的各种操作接口，RB-tree 也都提供了，所以几乎所有的 set 操作行为、都只是转调用 RB-tree 的操作行为而已。

代码也十分直观，以下直接列出 set 的代码，必要的解释已经包含在了注释中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
/// @brief 模板类 set，键值不允许重复
/// @tparam Key  键值类型
/// @tparam Compare  键值比较方式，缺省使用 tinystl::less
template <class Key, class Compare = tinystl::less<Key>>
class set {

public:  // set 的型别定义
    typedef Key            key_type;
    typedef Key            value_type;
    typedef Compare        key_compare;
    typedef Compare        value_compare;

private:  // 内部型别定义
    // 以 tinystl::rb_tree 作为底层机制
    typedef tinystl::rb_tree<value_type, key_compare> base_type;
    base_type tree_;  // 底层红黑树

public:  // 使用 rb_tree 定义的型别
    typedef typename base_type::node_type         node_type;
    
    // 不允许通过迭代器来更改 set 的键值，因此下述全部使用 const 
    typedef typename base_type::const_pointer          pointer; 
    typedef typename base_type::const_pointer          const_pointer;
    typedef typename base_type::const_reference        reference;
    typedef typename base_type::const_reference        const_reference;
    typedef typename base_type::const_iterator         iterator;
    typedef typename base_type::const_iterator         const_iterator;
    typedef typename base_type::const_reverse_iterator reverse_iterator;
    typedef typename base_type::const_reverse_iterator const_reverse_iterator;
    typedef typename base_type::size_type              size_type;
    typedef typename base_type::difference_type        difference_type;
    typedef typename base_type::allocator_type         allocator_type;

public:  // 构造、复制、移动函数
    set() = default;

    template <class InputIterator>
    set(InputIterator first, InputIterator last) : tree_() {
        tree_.insert_unique(first, last);
    }

    set(std::initializer_list<value_type> ilist) : tree_() {
        tree_.insert_unique(ilist.begin(), ilist.end());
    }

    set(const set& rhs) : tree_(rhs.tree_) {}

    set(set&& rhs) noexcept : tree_(tinystl::move(rhs.tree_)) {}

    set& operator=(const set& rhs) {
        tree_ = rhs.tree_;
        return *this;
    }

    set& operator=(set&& rhs) noexcept {
        tree_ = tinystl::move(rhs.tree_);
        return *this;
    }

    set& operator=(std::initializer_list<value_type> ilist) {
        tree_.clear();
        tree_.insert_unique(ilist.begin(), ilist.end());
        return *this;
    }

public:  // 相关接口
    key_compare   key_comp()       const { return tree_.key_comp(); }
    value_compare value_comp()     const { return tree_.key_comp(); }
    allocator_type get_allocator() const { return tree_.get_allocator(); }

public:  // 迭代器相关操作
    iterator               begin()         noexcept { return tree_.begin(); }
    const_iterator         begin()   const noexcept { return tree_.begin(); }
    iterator               end()           noexcept { return tree_.end(); }
    const_iterator         end()     const noexcept { return tree_.end(); }
    reverse_iterator       rbegin()        noexcept { return tree_.crbegin(); }
    const_reverse_iterator rbegin()  const noexcept { return tree_.crbegin(); }
    reverse_iterator       rend()          noexcept { return tree_.rend(); }
    const_reverse_iterator rend()    const noexcept { return tree_.rend(); }

    const_iterator         cbegin()  const noexcept { return tree_.cbegin(); }
    const_iterator         cend()    const noexcept { return tree_.cend(); }
    const_reverse_iterator crbegin() const noexcept { return tree_.crbegin(); }
    const_reverse_iterator crend()   const noexcept { return tree_.crend(); }

public:  // 容量相关
    bool                   empty()    const noexcept { return tree_.empty(); }
    size_type              size()     const noexcept { return tree_.size(); }
    size_type              max_size() const noexcept { return tree_.max_size(); }

public:  // 插入删除相关
    template <class ...Args>
    pair<iterator, bool> emplace(Args&& ...args) {
        return tree_.emplace_unique(tinystl::forward<Args>(args)...);
    }

    template <class ...Args>
    iterator emplace_hint(iterator hint, Args&& ...args) {
        return tree_.emplace_unique_use_hint(hint, tinystl::forward<Args>(args)...);
    }

    pair<iterator, bool> insert(const value_type& value) {
        return tree_.insert_unique(value);
    }

    pair<iterator, bool> insert(value_type&& value) {
        return tree_.insert_unique(tinystl::move(value));
    }

    iterator insert(const_iterator hint, const value_type& value) {
        return tree_.insert_unique(hint, value);
    }

    iterator insert(const_iterator hint, value_type&& value) {
        return tree_.insert_unique(hint, tinystl::move(value));
    }

    template <class InputIterator>
    void insert(InputIterator first, InputIterator last) {
        tree_.insert_unique(first, last);
    }

    void      erase(iterator pos)                  { tree_.erase(pos); }
    size_type erase(const key_type& key)           { return tree_.erase_unique(key); }
    void      erase(iterator first, iterator last) { tree_.erase(first, last); }

    void      clear() { tree_.clear(); }

public:  // set 相关操作
    iterator       find(const key_type& key)              { return tree_.find(key); }
    const_iterator find(const key_type& key)        const { return tree_.find(key); }

    size_type      count(const key_type& key)       const { return tree_.count_unique(key); }

    iterator       lower_bound(const key_type& key)       { return tree_.lower_bound(key); }
    const_iterator lower_bound(const key_type& key) const { return tree_.lower_bound(key); }

    iterator       upper_bound(const key_type& key)       { return tree_.upper_bound(key); }
    const_iterator upper_bound(const key_type& key) const { return tree_.upper_bound(key); }

    pair<iterator, iterator> equal_range(const key_type& key) {
        return tree_.equal_range_unique(key);
    }

    pair<const_iterator, const_iterator> equal_range(const key_type& key) const {
        return tree_.equal_range_unique(key);
    }

    void swap(set& rhs) noexcept { tree_.swap(rhs.tree_); }

public:
    friend bool operator==(const set& lhs, const set& rhs) { return lhs.tree_ == rhs.tree_; }
    friend bool operator< (const set& lhs, const set& rhs) { return lhs.tree_ <  rhs.tree_; }
};

// 重载比较操作符
template <class Key, class Compare>
bool operator==(const set<Key, Compare>& lhs, const set<Key, Compare>& rhs) {
    return lhs == rhs;
}

template <class Key, class Compare>
bool operator<(const set<Key, Compare>& lhs, const set<Key, Compare>& rhs) {
    return lhs < rhs;
}

template <class Key, class Compare>
bool operator!=(const set<Key, Compare>& lhs, const set<Key, Compare>& rhs) {
    return !(lhs == rhs);
}

template <class Key, class Compare>
bool operator>(const set<Key, Compare>& lhs, const set<Key, Compare>& rhs) {
    return rhs < lhs;
}

template <class Key, class Compare>
bool operator<=(const set<Key, Compare>& lhs, const set<Key, Compare>& rhs) {
    return !(rhs < lhs);
}

template <class Key, class Compare>
bool operator>=(const set<Key, Compare>& lhs, const set<Key, Compare>& rhs) {
    return !(lhs < rhs);
}

// 重载 swap
template <class Key, class Compare>
void swap(set<Key, Compare>& lhs, set<Key, Compare>& rhs) noexcept {
    lhs.swap(rhs);
}

需要注意的是这里的 insert()，由于 set 不允许键值重复，因此在 set 中使用的是 RB-tree 的 insert_unique() 来进行插入操作，稍后我们会在 multiset 中看到他们的区别。

multiset

multiset 的特性与用法和 set 完全相同，唯一的差别在于它允许键值重复，因此它的插入操作采用的是底层 RB-tree 的 insert_equal() （此处为 insert_multi()）而非 insert_unique()。以下仅列出与 set 不同的一些部分。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
/// @brief 模板类 multiset，键值允许重复
/// @tparam Key  键值类型
/// @tparam Compare  键值比较方式，缺省使用 tinystl::less
template <class Key, class Compare = tinystl::less<Key>>
class multiset {

public:  // multiset 的型别定义

private:  // 内部型别定义

public:  // 使用 rb_tree 定义的型别

public:  // 构造、复制、移动函数
    multiset() = default;

    template <class InputIterator>
    multiset(InputIterator first, InputIterator last) : tree_() {
        tree_.insert_multi(first, last);
    }

    multiset(std::initializer_list<value_type> ilist) : tree_() {
        tree_.insert_multi(ilist.begin(), ilist.end());
    }

    multiset(const multiset& rhs) : tree_(rhs.tree_) {}

    multiset(multiset&& rhs) noexcept : tree_(tinystl::move(rhs.tree_)) {}

    multiset& operator=(const multiset& rhs) {
        tree_ = rhs.tree_;
        return *this;
    }

    multiset& operator=(multiset&& rhs) noexcept {
        tree_ = tinystl::move(rhs.tree_);
        return *this;
    }

    multiset& operator=(std::initializer_list<value_type> ilist) {
        tree_.clear();
        tree_.insert_multi(ilist.begin(), ilist.end());
        return *this;
    }

public:  // 相关接口

public:  // 迭代器相关

public:  // 容量相关

public:  // 插入删除相关
    template <class ...Args>
    iterator emplace(Args&& ...args) {
        return tree_.emplace_multi(tinystl::forward<Args>(args)...);
    }

    template <class ...Args>
    iterator emplace_hint(iterator hint, Args&& ...args) {
        return tree_.emplace_multi_use_hint(hint, tinystl::forward<Args>(args)...);
    }

    iterator insert(const value_type& value) {
        return tree_.insert_multi(value);
    }

    iterator insert(value_type&& value) {
        return tree_.insert_multi(tinystl::move(value));
    }

    iterator insert(const_iterator hint, const value_type& value) {
        return tree_.insert_multi(hint, value);
    }

    iterator insert(const_iterator hint, value_type&& value) {
        return tree_.insert_multi(hint, tinystl::move(value));
    }

    template <class InputIterator>
    void insert(InputIterator first, InputIterator last) {
        tree_.insert_multi(first, last);
    }

    void      erase(iterator pos)                  { tree_.erase(pos); }
    size_type erase(const key_type& key)           { return tree_.erase_multi(key); }
    void      erase(iterator first, iterator last) { tree_.erase(first, last); }

    void      clear() { tree_.clear(); }

public:  // multiset 相关操作
    iterator       find(const key_type& key)              { return tree_.find(key); }
    const_iterator find(const key_type& key)        const { return tree_.find(key); }

    size_type      count(const key_type& key)       const { return tree_.count_multi(key); }

    iterator       lower_bound(const key_type& key)       { return tree_.lower_bound(key); }
    const_iterator lower_bound(const key_type& key) const { return tree_.lower_bound(key); }

    iterator       upper_bound(const key_type& key)       { return tree_.upper_bound(key); }
    const_iterator upper_bound(const key_type& key) const { return tree_.upper_bound(key); }

    pair<iterator, iterator> equal_range(const key_type& key) {
        return tree_.equal_range_multi(key);
    }

    pair<const_iterator, const_iterator> equal_range(const key_type& key) const {
        return tree_.equal_range_multi(key);
    }

    void swap(multiset& rhs) noexcept { tree_.swap(rhs.tree_); }
};

map

map 的特性是，所有元素都会根据元素的键值自动被排序。map 的所有元素都是 pair，同时拥有实值（value）和键值（key）。 pair 的第一元素被视为键值，第二元素被视为实值。map 不允许两个元素拥有相同的键值。关于 pair 的介绍已经在 rb-tree 预备知识 中介绍了，这里就不再赘述。

与 set 类似，我们也不能通过 map 的迭代器来修改 key，因为 key 关系到 map 的排序规则，但我们可以修改 value 的值。因此，map iterators 既不是一种 constant iterators，也不是一种 mutable iterators。

map 的几乎所有操作也都是转调用了 RB-tree 的接口，以下直接列出 map 的代码，删去了部分不太重要的内容。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
/// @brief 模板类 map，键值不允许重复
/// @tparam Key  键值类型
/// @tparam T  实值类型
/// @tparam Compare  键值比较方式，缺省使用 tinystl::less
template <class Key, class T, class Compare = tinystl::less<Key>>
class map {

public:  // map 的嵌套型别定义
    typedef Key                             key_type;
    typedef T                               mapped_type;
    typedef tinystl::pair<const Key, T>     value_type;
    typedef Compare                         key_compare;

public:  // 用于比较两个元素的仿函数
    class value_compare : public tinystl::binary_function<value_type, value_type, bool> {
        friend class map<Key, T, Compare>;
    private:
        Compare comp;
        value_compare(Compare c) : comp(c) {}
    public:
        bool operator()(const value_type& lhs, const value_type& rhs) const {
            return comp(lhs.first, rhs.first);  // 比较键值的大小
        }
    };

private:  // 以 tinystl::rb_tree 作为底层机制
    typedef tinystl::rb_tree<value_type, key_compare> base_type;
    base_type tree_;  // 底层红黑树

public:  // 使用 rb_tree 定义的型别
    typedef typename base_type::node_type              node_type;
    
    // map 不允许修改键值，但允许修改实值
    typedef typename base_type::pointer                pointer;
    typedef typename base_type::const_pointer          const_pointer;
    typedef typename base_type::reference              reference;
    typedef typename base_type::const_reference        const_reference;
    typedef typename base_type::iterator               iterator;
    typedef typename base_type::const_iterator         const_iterator;
    typedef typename base_type::reverse_iterator       reverse_iterator;
    typedef typename base_type::const_reverse_iterator const_reverse_iterator;
    typedef typename base_type::size_type              size_type;
    typedef typename base_type::difference_type        difference_type;
    typedef typename base_type::allocator_type         allocator_type;

public:  // 构造、复制、移动、赋值函数
    map() = default;

    template <class InputIterator>
    map(InputIterator first, InputIterator last) : tree_() {
        tree_.insert_unique(first, last);
    }

    map(std::initializer_list<value_type> ilist) : tree_() {
        tree_.insert_unique(ilist.begin(), ilist.end());
    }

    map(const map& rhs) : tree_(rhs.tree_) {}

    map(map&& rhs) noexcept : tree_(tinystl::move(rhs.tree_)) {}

    map& operator=(const map& rhs) {
        tree_ = rhs.tree_;
        return *this;
    }

    map& operator=(map&& rhs) noexcept {
        tree_ = tinystl::move(rhs.tree_);
        return *this;
    }

    map& operator=(std::initializer_list<value_type> ilist) {
        tree_.clear();
        tree_.insert_unique(ilist.begin(), ilist.end());
        return *this;
    }

public:  // 相关接口
    key_compare    key_comp()      const { return tree_.key_comp(); }
    value_compare  value_comp()    const { return value_compare(tree_.key_comp()); }
    allocator_type get_allocator() const { return tree_.get_allocator(); }

public:  // 迭代器相关操作

public:  // 容量相关操作
    bool                   empty()    const noexcept { return tree_.empty(); }
    size_type              size()     const noexcept { return tree_.size(); }
    size_type              max_size() const noexcept { return tree_.max_size(); }

public:  // 访问元素相关
    
    /// @brief 访问以 key 为键值的实值，若不存在则抛出异常
    /// @param key  键值
    /// @return 实值
    mapped_type& at(const key_type& key) {
        // it 指向大于等于 key 的第一个节点的位置，若 map 中存在 key，则这个节点的键值一定等于 key
        // 否则，map 中不存在 key，抛出异常
        iterator it = lower_bound(key);
        THROW_OUT_OF_RANGE_IF(it == end() || key_comp()(it->first, key),
            "map<Key, T> no such element exists");
        return it->second;
    }

    const mapped_type& at(const key_type& key) const {
        iterator it = lower_bound(key);
        THROW_OUT_OF_RANGE_IF(it == end() || key_comp()(it->first, key),
            "map<Key, T> no such element exists");
        return it->second;
    }

    /// @brief 访问以 key 为键值的实值，若不存在则插入一个新节点
    /// @param key 键值 
    /// @return  实值
    mapped_type& operator[](const key_type& key) {
        iterator it = lower_bound(key);
        // 若不存在 key，则插入一个新节点
        if (it == end() || key_comp()(key, it->first)) {
            // 默认构造一个 mapped_type 类型的右值，作为新节点的实值
            it = emplace_hint(it, key, mapped_type());
        }
        return it->second;
    }

    mapped_type& operator[](key_type&& key) {
        iterator it = lower_bound(key);
        if (it == end() || key_comp()(key, it->first)) {
            it = emplace_hint(it, tinystl::move(key), mapped_type());
        }
        return it->second;
    }

public:  // 插入删除相关，调用 rb_tree 的接口

    template <class ...Args>
    tinystl::pair<iterator, bool> emplace(Args&& ...args) {
        return tree_.emplace_unique(tinystl::forward<Args>(args)...);
    }

    template <class ...Args>
    iterator emplace_hint(const_iterator hint, Args&& ...args) {
        return tree_.emplace_unique_use_hint(hint, tinystl::forward<Args>(args)...);
    }

    tinystl::pair<iterator, bool> insert(const value_type& value) {
        return tree_.insert_unique(value);
    }

    tinystl::pair<iterator, bool> insert(value_type&& value) {
        return tree_.insert_unique(tinystl::move(value));
    }

    iterator insert(iterator hint, const value_type& value) {
        return tree_.insert_unique(hint, value);
    }

    iterator insert(iterator hint, value_type&& value) {
        return tree_.insert_unique(hint, tinystl::move(value));
    }

    template <class InputIterator>
    void insert (InputIterator first, InputIterator last) {
        tree_.insert_unique(first, last);
    }

    void erase(iterator pos) { tree_.erase(pos); }
    size_type erase(const key_type& key) { return tree_.erase_unique(key); }
    void erase(iterator first, iterator last) { tree_.erase(first, last); }

    void clear() { tree_.clear(); }

public:  // map 相关操作
    iterator        find(const key_type& key)                { return tree_.find(key); }
    const_iterator  find(const key_type& key)          const { return tree_.find(key); }
    
    size_type       count(const key_type& key)         const { return tree_.count_unique(key); }
    
    iterator        lower_bound(const key_type& key)         { return tree_.lower_bound(key); }
    const_iterator  lower_bound(const key_type& key)   const { return tree_.lower_bound(key); }

    iterator        upper_bound(const key_type& key)         { return tree_.upper_bound(key); }
    const_iterator  upper_bound(const key_type& key)   const { return tree_.upper_bound(key); }

    tinystl::pair<iterator, iterator> equal_range(const key_type& key) {
        return tree_.equal_range_unique(key);
    }

    tinystl::pair<const_iterator, const_iterator> equal_range(const key_type& key) const {
        return tree_.equal_range_unique(key);
    }

    void swap(map& rhs) noexcept { tree_.swap(rhs.tree_); }

public:
    friend bool operator==(const map& lhs, const map& rhs) { return lhs.tree_ == rhs.tree_; }
    friend bool operator< (const map& lhs, const map& rhs) { return lhs.tree_ <  rhs.tree_; }
};

// 重载比较操作符


// 重载 swap
template <class Key, class T, class Compare>
void swap(map<Key, T, Compare>& lhs, map<Key, T, Compare>& rhs) noexcept {
    lhs.swap(rhs);
}

从型别定义中可以看出，value_type 被定义为 first_type 为 const key，second_type 为 T 的 pair，因此我们只能修改实值而不能修改键值。

这里博主比较疑惑的是名称，一般我们都认为 map 的结构是 <key, value> 这样的键值对，但从型别定义来看，似乎 value 对应着 mapped_type 而 <key_type, mapped_type> 整体才算作 value_type。

1
2
3
typedef Key                             key_type;
typedef T                               mapped_type;
typedef tinystl::pair<const Key, T>     value_type;

multimap

与 multiset 一样，multimap 与 map 唯一的区别就在于允许键值重复，因此使用的是 insert_multi() 而非 insert_unique()，以下还是列出与 map 的不同之处。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
/// @brief 模板类 multimap，键值允许重复
/// @tparam Key  键值类型
/// @tparam T  实值类型
/// @tparam Compare  键值比较方式，缺省使用 tinystl::less
template <class Key, class T, class Compare = tinystl::less<Key>>
class multimap {

public:  // multimap 的嵌套型别定义

public:  // 用于比较两个元素的仿函数

private:  // 以 tinystl::rb_tree 作为底层机制

public:  // 使用 rb_tree 定义的型别

public:  // 构造、复制、移动、赋值函数

public:  // 相关接口

public:  // 迭代器相关操作

public:  // 容量相关操作

// 由于允许多个键值相同，所以不提供访问元素相关的接口

public:  // 插入删除相关，调用 rb_tree 的接口

    template <class ...Args>
    iterator emplace(Args&& ...args) {
        return tree_.emplace_multi(tinystl::forward<Args>(args)...);
    }

    template <class ...Args>
    iterator emplace_hint(const_iterator hint, Args&& ...args) {
        return tree_.emplace_multi_use_hint(hint, tinystl::forward<Args>(args)...);
    }

    iterator insert(const value_type& value) {
        return tree_.insert_multi(value);
    }

    iterator insert(value_type&& value) {
        return tree_.insert_multi(tinystl::move(value));
    }

    iterator insert(iterator hint, const value_type& value) {
        return tree_.insert_multi(hint, value);
    }

    iterator insert(iterator hint, value_type&& value) {
        return tree_.insert_multi(hint, tinystl::move(value));
    }

    template <class InputIterator>
    void insert(InputIterator first, InputIterator last) {
        tree_.insert_multi(first, last);
    }

    void erase(iterator pos) { tree_.erase(pos); }
    size_type erase(const key_type& key) { return tree_.erase_unique(key); }
    void erase(iterator first, iterator last) { tree_.erase(first, last); }

    void clear() { tree_.clear(); }

public:  // multimap 相关操作
    iterator        find(const key_type& key)                { return tree_.find(key); }
    const_iterator  find(const key_type& key)          const { return tree_.find(key); }
    
    size_type       count(const key_type& key)         const { return tree_.count_multi(key); }
    
    iterator        lower_bound(const key_type& key)         { return tree_.lower_bound(key); }
    const_iterator  lower_bound(const key_type& key)   const { return tree_.lower_bound(key); }

    iterator        upper_bound(const key_type& key)         { return tree_.upper_bound(key); }
    const_iterator  upper_bound(const key_type& key)   const { return tree_.upper_bound(key); }

    tinystl::pair<iterator, iterator> equal_range(const key_type& key) {
        return tree_.equal_range_multi(key);
    }

    tinystl::pair<const_iterator, const_iterator> equal_range(const key_type& key) const {
        return tree_.equal_range_multi(key);
    }

    void swap(multimap& rhs) noexcept { tree_.swap(rhs.tree_); }

public:
    friend bool operator==(const multimap& lhs, const multimap& rhs) { return lhs.tree_ == rhs.tree_; }
    friend bool operator< (const multimap& lhs, const multimap& rhs) { return lhs.tree_ <  rhs.tree_; }
};

// 重载比较操作符

// 重载 swap

总结

本节简要介绍了 STL 中以 RB-tree 为底层容器的四种容器：set、multiset、map、multimap；这些容器仅仅是转调用了底层 RB-tree 的一些接口，无论是理解还是实现都十分简单。

下一节将开始介绍 STL 中的最后一个容器 ———— hashtable。