关联式容器

在之前的文章中，我们了解并模拟实现了一些序列式容器，例如 vector、list 等。这些容器的底层都是线性数据结构，所以叫做序列式容器，其中存储的都是数据本身，数据与数据之间并没有太强的关联性

而关联式容器，不仅可以存储数据本身，还可以用来表示数据与数据之间的关系，体现出它们的关联性，而且在搜索时比序列式容器的效率高很多

键值对

关联式容器中存储的是 <key, value> 形式的键值对结构，这种结构在 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 有两个成员变量：first 和 second，其中 first 表示键key，second 表示与 key 对应的值value

以下是 pair 的使用方法

vector<pair<int, int>> v;
pair<int, int> p1(1, 1); // 1.构造有名对象
v.push_back(p1);
v.push_back(pair<int, int>(2, 2)); // 2.构造匿名对象
v.push_back(make_pair(3, 3)); // 3.调用 make_pair
v.push_back({ 4,4 }); // 4.隐式类型转换

// 输出
for (auto e : v)
{
        cout << e.first << "->" << e.second << endl;
}

其中，make_pair()是一个函数，用来构造一个pair对象

树形结构的关联式容器

根据不同的场景和使用需求，关联式容器分为两种：树形结构的关联式容器和哈希结构的关联式容器

而 map 和 set 就属于树形结构，它们的底层数据结构一般都是红黑树

set

相关文档：set

简介

set 有如下特性：

• set 中只会存储 key，它的 key 就是它的 value
• set 中每个元素的 key 都是唯一的，set 中不允许出现重复元素，因此 set 可以用来数据去重
• set 中的元素不允许修改，但是允许插入和删除元素
• 中序遍历 set，可以得到有序的序列
• set 的查找数据效率是 O(log n)

使用

模板参数

• T：set 中的元素类型
• Compare：set 中元素的比较逻辑，默认是小于
• Alloc：set 中元素的管理方式，使用默认即可

构造

函数声明	功能介绍
set (const Compare& comp = Compare(), const Allocator& = Allocator());	构造空的 set
set (Inputlterator first, Inputlterator last, const Compare& comp = Compare(), const Allocator& = Allocator());	用[first,last)区间中的元素构造 set
set (const set<Key,Compare, Allocator>& x);	set 的拷贝构造

vector<int> v = { 1,2,3,4,5,6,7 };

// 迭代器区间构造
set<int> s1(v.begin(), v.end());

for (auto e : s1)
{
        cout << e << " ";
}
cout << endl;

迭代器

函数声明	功能介绍
iterator begin()	返回 set 中起始位置元素的迭代器
iterator end()	返回 set 中最后一个元素下一个位置的迭代器
reverse_iterator rbegin()	返回 set 第一个元素的迭代器，即 end
reverse_iterator rend()	返回 set 最后一个元素下一个位置的反向迭代器，即 begin

容量

函数声明	功能介绍
bool empty() const	检测 set 是否为空，空返回 true，否则返回 false
size_type size() const	返回 set 中有效元素的个数

修改

函数声明	功能介绍
pair<iterator, bool> insert(const value_type& x)	在 set 中插入元素 x。如果插入成功，返回<该元素在 set 中的位置, true>；如果插入失败，说明 x 在 set 中已经存在，返回<x 在 set 中的位置, false>
void erase(iterator position)	删除 set 中 position 位置上的元素。
size_type erase(const key_type& x)	删除 set 中值为 x 的元素，返回删除的元素的个数
void erase(iterator first, iterator last)	删除 set 中[first, last)区间中的元素
void swap(set<Key,Compare,Allocator>& st)	交换 set 中的元素
void clear()	将 set 中的元素清空

一般情况下，insert 的返回值类型都是 bool 类型，用来表示插入成功或者插入失败。

而这里的 insert 的返回值类型是一个 pair<iterator, bool>，其中

• bool 用来表示插入成功或者失败，iterator则是指向插入元素的迭代器，方便我们对元素进行修改

但是 set 不支持修改元素，只能当作 find 来使用

set<string> s1;

string s;
while (cin >> s)
{
        auto ret = s1.insert(s);
        if (ret.second)
                cout << "插入成功：" << *(ret.first) << endl;
        else
                cout << "插入失败，key已存在：" << *(ret.first) << endl;
}

修改操作在 map 中是允许的，所以这种写法在 map 中就会体现出它的精妙之处

其他操作

函数声明	功能介绍
iterator find (const key_type& key) const;	查找指定元素 key，找到就返回它的迭代器，找不到则返回 end() 迭代器
size_type count (const key_type& key) const;	统计指定键值 key 在容器中出现的次数，因为 set 不允许重复元素，所以结果只能是 1 或 0
iterator lower_bound (const key_type& key) const;	返回一个迭代器，指向第一个大于等于给定键值 key 的元素；如果没有，则返回 end()
iterator upper_bound(const key_type& key);	返回一个迭代器，指向第一个大于给定键值 key 的元素；如果没有，则返回 end()
pair<iterator,iterator> equal_range (const key_type& key) const;	返回一个包含两个迭代器的 pair，这两个迭代器分别指向范围等于给定键值的第一个元素和最后一个元素之后的位置

lower_bound 和 upper_bound 通常都是一起配合使用，寻找一个左闭右开的区间 [first, last)。例如有一个set = [1,2,3,4,5,6,7]，通过lower_bound(3) 和 upper_bound(5)就可以找到区间 [3, 6)

vector<int> v = { 1,2,3,4,5,6,7 };

// 迭代器区间构造
set<int> s1(v.begin(), v.end());
// 寻找 [3, 6) 区间
set<int>::iterator first = s1.lower_bound(3);
auto last = s1.upper_bound(5);
// 输出
while (first != last)
{
        cout << *first << " ";
        ++first;
}
cout << endl;

equal_range 寻找的是一个范围，范围中的元素键值相同。由于 set 不允许键值重复，所以这个范围一般只有一个元素或者为空

map

map 的许多特性和 set 是相同的，因此在 set 讲过的东西可能在这里就不再详细说明了

相关文档：map

简介

• map 中存储的是键值对<key, value>
• map 中每个元素的 key 都是唯一的，不允许出现重复 key，但是不同 key 对应的 value 可以重复
• map 中的元素的 key 不允许修改，但是允许修改 value，也可以进行元素的插入与删除
• 中序遍历 map，可以得到有序的序列
• map 的查找数据效率是 O(log n)

使用

模板参数

• Key：键值对中 key 的类型
• T：键值对中 value 的类型
• Compare：set 中元素的比较逻辑，默认是小于
• Alloc：set 中元素的管理方式，使用默认即可

构造

与 set 一样，map 有空构造、迭代器区间构造、拷贝构造，这里演示一下迭代器区间构造

迭代器

函数声明	功能介绍
begin()和 end()	begin：首元素的位置，end：最后一个元素的下一个位置
rbegin()和 rend()	反向迭代器，rbegin 在 end 位置，rend 在 begin 位置，其 ++和 – 操作与 begin 和 end 操作移动相反

容量

函数声明	功能简介
bool empty() const	检测 map 中的元素是否为空，是返回 true，否则返回 false
size_type size() const	返回 map 中有效元素的个数

修改

函数声明	功能简介
pair<iterator,bool> insert (const value_type& x)	在 map 中插入键值对 x，注意 x 是一个键值对，返回值也是键值对：iterator 代表新插入元素的位置，bool 代表是否插入成功
void erase (iterator position)	删除 position 位置上的元素
size_type erase (const key_type& x)	删除键值为 x 的元素，返回删除的元素的个数
void erase (iterator first, iterator last)	删除[first,last)区间中的元素
void swap (map<Key,T,Compare,Allocator>& mp)	交换两个 map 中的元素
void clear()	将 map 中的元素清空

operator[]

map 支持[]访问。[]内填的不是下标，而是键值key，通过 key 可以访问到对应的 value，如下

而 operator[] 是这样实现的

mapped_type& operator[] (const key_type& key)
{
        return (*((this->insert(make_pair(key, mapped_type()))).first)).second;
}

看着有点复杂，尝试拆分一下：

// 伪代码
mapped_type& operator[] (const key_type& key)
{
        pair<iterator, bool> ret = insert(make_pair(key, mapped_type()));
        iterator it = ret.first;
        return it->second;
}

mapped_type 表示键值对中的值value的类型

insert 不管插入成功还是失败，都会返回一个 pair<iterator, bool>，其中 iterator 是指向key所在节点的迭代器，bool 表示插入成功或失败。

• key不存在，插入成功，返回 pair<新插入key所在节点的迭代器，true>
• key存在，插入失败，返回 pair<存在的key所在节点的迭代器，false>

通过 pair 中的迭代器，可以访问到节点的值value

再来看下面这条语句的作用

insert(make_pair(key, mapped_type()))

如果使用 operator[key]，key 不存在，进行插入，只不过插入的是默认构造出的值。例如：value类型为string，则插入空串""；类型为 int，则插入0等

那么这有什么用呢？——可以用来统计键值的出现次数

例如，有一组单词，我们可以用 set 来统计每个单词的频次，代码可以这样写：

vector<string> v = { "string",{"left"},{"right"},{"string"},{"left"},{"right"},{"string"},{"string"} };
map<string, int> s;
// 统计
for (auto& e : v)
{
        auto it = s.find(e);
        if (it != s.end()) // 单词存在
                it->second++;
        else
                s.insert({ e,1 }); // 单词不存在
}
// 打印
for (auto e : s)
{
        cout << e.first << ":" << e.second << endl;
}

如果使用 operator[]，代码就会简单很多：

• 存在就++
• 不存在，先插入0，再++

vector<string> v = { "string",{"left"},{"right"},{"string"},{"left"},{"right"},{"string"},{"string"} };
map<string, int> s;
// 统计
for (auto& e : v)
{
        //auto it = s.find(e);
        //if (it != s.end()) // 单词存在
        //        it->second++;
        //else
        //        s.insert({ e,1 }); // 单词不存在

        s[e]++;
}
// 打印
for (auto e : s)
{
        cout << e.first << ":" << e.second << endl;
}

测试：

其他操作

函数声明	功能介绍
iterator find (const key_type& key) const;	查找键值为 key 的元素，找到就返回它的迭代器，找不到则返回 end() 迭代器
size_type count (const key_type& key) const;	统计指定键值 key 在容器中出现的次数
iterator lower_bound (const key_type& key) const;	返回一个迭代器，指向第一个大于等于给定键值 key 的元素；如果没有，则返回 end()
iterator upper_bound(const key_type& key);	返回一个迭代器，指向第一个大于给定键值 key 的元素；如果没有，则返回 end()
pair<iterator,iterator> equal_range (const key_type& key) const;	返回一个包含两个迭代器的 pair，这两个迭代器分别指向范围等于给定键值的第一个元素和最后一个元素之后的位置

multiset 和 multimap

multiset 与 set 的区别就是：multiset 的元素可以重复，而 set 中的元素是唯一的；它们的接口使用起来类似，这里不再一一列举

multimap 和 map 的区别也是一样的：multimap 键值可以重复，map 键值不可重复，但是需要注意：multimap 并没有重载 operator[]

因为 multimap 中的不同元素的键值可能相同，使用键值访问元素时不知道该访问哪个，会引发歧义

底层数据结构

在 STL 中，map 和 set 通常采用红黑树作为底层实现，说到红黑树，就不得不说 AVL树，它俩都是二叉搜索树，下面我们就来看一下这三棵树

二叉搜索树

概念

二叉搜索树也叫二叉排序树，它是一棵特殊的二叉树，有如下性质

• 二叉搜索树可以是一棵空树，如果不为空，则：
• 若左子树不为空，左子树的所有节点的键值均小于根节点的键值
• 若右子树不为空，右子树的所有节点的键值均大于根节点的键值
• 左右子树也都是二叉搜索树
• 对二叉搜索树进行中序遍历，遍历出的数据都是有序的，如下图进行中序遍历：[1, 3, 4, 6, 7, 8, 10, 13, 14]

操作

查找

1. 从根节点开始寻找指定值
   1. 若指定值比当前节点大，则向右边寻找
   2. 若指定值比当前节点小，则向左边寻找
2. 最多查找树的高度次，就可以找到指定数据；走到空还没有找到，说明值不存在

在二叉搜索树中寻找7

在二叉搜索树中寻找不存在的11

插入

1. 树为空，直接插入值即可
2. 树不为空，根据二叉搜索树的性质，寻找合适的位置插入
   1. 从根节点开始寻找
   2. 插入值比当前节点大，向右走；插入值比当前节点小，向左走
   3. 直到找到空位置

依次插入0，9

删除

删除值比较麻烦，分为下面三种情况：

1. 删除的节点左右子树为空，也就是叶子节点
2. 删除的节点左为空或者右为空
3. 删除的节点左右都不为空

其实前两种情况可以合并为一种情况，假设要删除的节点是cur，以下是删除方法：

1. cur的左为空或者右为空
   a. 左子树为空，由 cur 的父节点 parent 接管 cur 的右子树，不管右子树为不为空
   

   b. 右子树为空，由 cur 的父节点 parent 接管 cur 的左子树，不管左子树为不为空
   

2. cur的左右都不为空，例如删除3

这种情况下，不可以先删除cur，再由 parent 接管 cur 的子树了，需要用到替换删除法：找到一个节点与cur交换，然后删除替代节点。详细操作可以看实现部分

实现

在实现之前，我们使用命名空间隔离一下

namespace key
{
};

结构

树节点中包含指向左右子树的指针，还有键值

template <class K>
struct BSTreeNode
{
        BSTreeNode(const K& key = K())
                :_left(nullptr)
                , _right(nullptr)
                , _key(key)
        {}

        BSTreeNode<K>* _left;
        BSTreeNode<K>* _right;
        K _key;
};

二叉搜索树的成员变量只有一个节点指针，代表树的根节点

template <class K>
class BSTree
{
        typedef BSTreeNode<K> Node;
private:
        Node* _root = nullptr;
};

插入

1. 树为空，直接插入值即可
2. 树不为空，根据二叉搜索树的性质，寻找合适的位置插入
   1. 从根节点开始寻找
   2. 插入值比当前节点大，向右走；插入值比当前节点小，向左走
   3. 直到找到空位置
3. 插入成功返回 true，失败返回 false
4. 一般二叉搜索树不允许插入重复的数据，因为二叉搜索树的作用就是查看某个值在不在结构中，重复值没有意义

注意：

1. 定义 cur 来寻找合适的插入位置，定义 parent 作为 cur 的父节点
2. 找到合适位置后，判断 cur 是 parent 的左子树还是右子树，然后进行 parent 与 cur 的链接

bool insert(const K& key)
{
        // 树为空
        if (_root == nullptr)
        {
                _root = new Node(key);
                return true;
        }

        // 树不为空
        // 寻找合适插入位置
        Node* cur = _root, * parent = nullptr;
        while (cur)
        {
                if (key > cur->_key)
                {
                        // 插入值 > 当前节点
                        parent = cur;
                        cur = cur->_right;
                }
                else if (key < cur->_key)
                {
                        // 插入值 < 当前节点
                        parent = cur;
                        cur = cur->_left;
                }
                else
                        return false; // 不允许插入重复值
        }
        // 找到插入位置
        cur = new Node(key);
        // 判断 cur 是 parent 的左子树还是右子树，链接
        if (cur->_key > parent->_key)
                parent->_right = cur;
        else
                parent->_left = cur;
        return true;
}

测试：

void test1()
{
        int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };
        key::BSTree<int> t1;

        for (auto e : a)
                t1.insert(e);
}

暂时没发现错误

中序遍历

我们可以写一个中序遍历，把结果打印出来看看

• 中序遍历需要从根节点开始
• 写一个公有函数 inOrder()，一个私有函数 _inOrder()
• 公有函数 inOrder() 负责将根节点 _root 传递给私有函数 _inOrder()
• 私有函数 _inOrder() 负责递归地实现中序遍历的逻辑

为什么要这样写呢？如果只实现一个公有函数 inOrder() 可不可以呢？

void inOrder(Node* root)
{
        inOrder(root->_left);
        inOrder(root->_right);
        cout << root->_key << " ";
}

中序遍历是从根节点开始遍历的，我们在外部调用时拿不到根节点 _root

BSTree<int> t1;
t1.inOrder(_root); // 拿不到 _root

那如果我们给 inOrder 的参数设置一个缺省值 _root 呢？

void inOrder(Node* root = _root)
{
    //...
}

这样也是不行的，我们想拿到 _root 要通过隐含的 this 指针，但是 this 指针不可以在函数的参数列表直接使用，只能在函数体中使用

当然也可以写一个 GetRoot 来允许外部拿到 _root，Java就很喜欢这样做，C++不太常用这种方式

所以还是写一个公有函数 inOrder()，再写一个私有函数 _inOrder()

public:
        void inOrder()
        {
                _inOrder(_root);
                cout << endl;
        }
private:
        void _inOrder(Node* root)
        {
            if (root == nullptr) return;
            _inOrder(root->_left);
            cout << root->_key << " ";
            _inOrder(root->_right);
        }

测试：

查找

找到指定值就返回 true，找不到返回 false

1. 树为空，直接返回 false
2. 树不为空，根据二叉搜索树的性质，寻找指定值
   1. 插入值比当前节点大，向右走；插入值比当前节点小，向左走
   2. 直到找到指定值，返回 tr