C++set与map的用法以及用AVL树封装
·
set与map的常见用法
set
set是有序容器，容器里的元素默认按从小到大的顺序，且容器里不会存在重复元素（自动去重），其底层一般用红黑树实现，插入、删除、查找的效率都是O(logN)
1.构造
void test_set01()
{
set<int> s1; // 默认构造
set<int> s2 = {4,4,4,4,2,2,2,1,8,6,5,9}; // 列表构造
int a[] = {6,3,5,7,9,2};
set<int> s3(a, a + 5); // 迭代器区间构造
for(auto& e : s1) cout << e << ' ';
cout << endl;
for(auto& e : s2) cout << e << ' ';
cout << endl;
for(auto& e : s3) cout << e << ' ';
cout << endl;
}
运行结果
也可以自定义set里面元素的顺序
struct my_cmp
{
// 判断a是否在b之前。
bool operator() (int a, int b) const
{
return abs(a) < abs(b); // 若|a| < |b|，则a在b前面
}
};
void test_set01()
{
int a[6] = {6,-3,5,7,-9,2};
set<int> s(a, a + 6); // 默认升序
set<int, greater<int>> s1(a, a + 6); // 降序
set<int, my_cmp> s2(a, a + 6); // 按绝对值升序
for(auto& e : s) cout << e << ' ';
cout << endl;
for(auto& e : s1) cout << e << ' ';
cout << endl;
for(auto& e : s2) cout << e << ' ';
cout << endl;
}
运行结果
2.查找元素
void test_set02()
{
set<int> s = { 2,3,5,6,7,9 };
auto it = s.find(3); // 查找元素3。找到了返回指向元素的迭代器，否则返回s.end()
cout << *it << endl;
it = s.lower_bound(5); // 查找第一个 >= 5 的元素，找到了返回其迭代器，否则返回s.end();
cout << *it << endl;
it = s.upper_bound(5); // 查找第一个 > 5 的元素，找到了返回其迭代器，否则返回s.end();
cout << *it << endl;
int cnt = s.count(4); // 查询容器中元素4的个数。对于set而言，找到了返回1，否则返回0
cout << cnt << endl;
cnt = s.count(5);
cout << cnt << endl;
}
运行结果
3.插入元素
void test_set03()
{
set<int> s;
int a[] = { 2,3,5,6,7,9 };
for(auto e : a)
s.insert(e); // 把a数组的所有元素插入到s中
auto p = s.insert(2); // 由于容器中已经有2了，这里会插入失败
// insert的返回值：
// 成功插入返回 pair<插入元素的迭代器, true>，否则返回 pair<插入元素的迭代器, false>
cout << *(p.first) << " " << p.second << endl;
p = s.insert(999);
cout << *(p.first) << " " << p.second << endl;
}
运行结果
4.删除元素
void test_set04()
{
set<int> s = { 2,3,5,6,7,9 };
int cnt = s.erase(2); // 删除2。
// erase的返回值是成功删除的元素个数。对于set而言成功删除返回1，否则返回0
cout << cnt << endl;
for(auto& e : s) cout << e << ' ';
cout << endl;
cnt = s.erase(100);
cout << cnt << endl;
for(auto& e : s) cout << e << ' ';
cout << endl;
}
运行结果
5.其他
void test_set05()
{
set<int> s = { 2,3,5,6,7,9 };
// 1.迭代器。begin()返回第一个元素的迭代器；end()返回最后一个元素的下一个元素的迭代器
auto it = s.begin();
while(it != s.end())
{
cout << *it << ' ';
// *it = 999; // err 注意不可修改set内部的元素。因为set容器的元素之间相互关联
++it;
}
// 2.容量相关
cout << s.size() << endl; // 返回容器里的元素个数
cout << s.empty() << endl; // 判断容器里是否为空。为空返回true，否则返回false
s.clear(); // 清空容器
}
set不支持插入重复元素，而multiset支持，其用法与set类似。 参考官方文档
map
set存储是单一元素key，set中的元素是按key的先后顺序排列的。
map在set之上又对key绑定了数据，map存储的的元素是pair<key, value>，map中的元素按key先后顺序排列【注意不是按pair<key, value>先后顺序排列】。
1.构造
void test_map01()
{
map<string, int> m; // 默认构造
pair<string, int> p[3] = { {"aaa", 5}, {"bbb", 2}, {"ccc", 1} };
map<string, int> m1(p, p + 3); // 迭代器区间构造
map<string, int> m2 = { {"c", 2}, {"b", 1}, {"a", 7} }; // 列表构造
for(auto& p : m)
cout << p.first << ' ' << p.second << endl;
cout << endl;
for(auto& p : m1)
cout << p.first << ' ' << p.second << endl;
cout << endl;
for(auto& p : m2)
cout << p.first << ' ' << p.second << endl;
cout << endl;
}
运行结果
与set类似，map也可以自定义元素的顺序
void test_map01()
{
map<int, int, greater<int>> m = { {1,0}, {2,0}, {3,0} }; // 按key从大到小
for(auto& p : m)
cout << p.first << ' ' << p.second << endl;
cout << endl;
// 错误写法：
// map<int, int, greater<pair<int,int>>> m = { {1,0}, {2,0}, {3,0} };
// 注意是按key比较，而非pair<key, value>
}
运行结果
2.查找元素
void test_map02()
{
map<string, string> m = { {"left", "左"}, {"right", "右"}, {"sort", "排序"} };
for(auto& p : m)
cout << p.first << ' ' << p.second << endl;
cout << endl;
auto it = m.find("sort"); // 查找key为sort的元素。找到了返回该元素的迭代器，否则返回m.end()
cout << it->first << " " << it->second << endl;
it = m.find("xxx");
}
map的lower_bound与upper_bound与set类似，这里不过多讲解
3.插入元素
void test_map03()
{
map<string, string> m = { {"left", "左"}, {"right", "右"}, {"sort", "排序"} };
auto it = m.insert({"age", "年龄"}); // m内部元素类型为pair<string,string>，插入的元素类型应当也是pair<string,string>
// insert的返回值：
// 成功插入返回 pair<指向该元素的迭代器, true>，否则返回pair<指向该元素的迭代器, false>
cout << it.first->first << ' ' << it.first->second << ' ' << it.second << endl;
it = m.insert({"left", "剩余"}); // m中已经有key值为"left"的元素了，这里会插入失败
cout << it.first->first << ' ' << it.first->second << ' ' << it.second << endl;
}
运行结果
4.[]重载
map还重载了[]，函数原型及用法如下：
value& operator[](const key& k);
查找key值为k的元素，并返回该元素对应的value。
若k不存在，则会先插入 {k, value()} （第二个是value的默认值），再返回其对应的value。
void test_map03()
{
map<string, string> m = { {"left", "左"}, {"right", "右"}, {"sort", "排序"} };
// 1.通过key查找value
cout << m["left"] << endl;
cout << m["right"] << endl;
cout << m["sort"] << endl << endl;
m["left"] = "剩余"; // 修改value
cout << m["left"] << endl << endl;
// 2.充当插入
m["word"] = "单词"; // 插入{"word", "单词"}。
// 【其实底层是先插入{"word", string()}, 然后再将value修改为"单词”】 插入{"word", string()}时，由于已经存在key为"word"的元素了，会插入失败
m["who"]; // 没有给value，会用其默认构造，相当于插入{"who", string()}
for(auto& p : m)
cout << p.first << ' ' << p.second << endl;
cout << endl;
}
运行结果
5.删除元素
void test_map04()
{
map<string, string> m = { {"left", "左"}, {"right", "右"}, {"sort", "排序"} };
int cnt = m.erase("left"); // 删除key为left的元素。返回成功删除的元素个数，对map而言：成功删除返回1，否则返回0
cout << cnt << endl;
for(auto& p : m)
cout << p.first << ' ' << p.second << endl;
cout << endl;
}
运行结果
6.其他
void test_map05()
{
map<int, int> m = { {2,3}, {5,6}, {7,9} }; // m存储的元素类型为 pair<int,int>
// 1.迭代器。begin()返回第一个元素的迭代器；end()返回最后一个元素的下一个元素的迭代器
auto it = m.begin();
while(it != m.end())
{
cout << it->first << ' ' << it->second << endl;
// cout << (*it).first << ' ' << (*it).second << endl; // 也可以这样写。it是指向 pair<int,int> 的迭代器
// it->first = 999; // err 注意：key不可修改
++it;
}
// 2.容量相关
cout << m.size() << endl; // 返回容器里的元素个数
cout << m.empty() << endl; // 判断容器里是否为空。为空返回true，否则返回false
m.clear(); // 清空容器
}
map不支持插入key值重复的元素，multimap支持，其用法与map类似。参考官方文档
set与map可以当哈希表使用，其用法需多刷题加以巩固。
AVL树封装set与map
此部分内容建立在上篇 C++平衡树之AVL树 之上
开始此部分前，请确保会AVL树的查找、插入、求前驱、求后继操作（删除操作为拓展内容）
AVL树回顾
相较于上篇，我简化了一下AVL树
#include<iostream>
using namespace std;
template<class T>
struct AVLtree_node
{
T _val; // 权值
int _h = 1; // 以该节点为根的子树的高度（为了保持平衡）
int _size = 1; // 以该节点为根的子树的大小（为了可以查询树中排名第k的节点）
// 相较于上篇，这里删除了_cnt，不支持插入重复元素
AVLtree_node* _left = nullptr; // 左儿子
AVLtree_node* _right = nullptr; // 右儿子
AVLtree_node* _parent = nullptr; // 父节点
AVLtree_node(const T& x = T())
:_val(x)
{}
};
template<class T>
class AVLtree
{
typedef AVLtree_node<T> node;
typedef AVLtree_node<T>* node_ptr;
protected:
node* _root = nullptr;
public:
构造、析构、拷贝构造、赋值重载等与上篇的一致
// 找到了返回该节点的指针，否则返回其应当插入位置的父节点的指针
node* find(const T& val)
{
node* cur = _root;
node* p = nullptr; // 记录cur的父节点
while (cur)
{
p = cur;
if (val < cur->_val)
cur = cur->_left;
else if (val > cur->_val)
cur = cur->_right;
else
return cur;
}
return p;
}
// 成功插入返回true，否则返回false
bool insert(const T& val)
{
if (!_root)
{
_root = get_node(val);
return true;
}
node* cur = find(val);
if (cur->_val == val)
return false;
else
{
// 到这里说明未找到，cur是val应插入的位置的父节点
node* p = cur;
cur = get_node(val);
cur->_parent = p;
if (val < p->_val) p->_left = cur;
else p->_right = cur;
update(cur);
return true;
}
}
int size() { return size(_root); }
bool empty() { return !_root; }
void clear()
{
_clear(_root);
_root = nullptr;
}
protected:
void _clear(node* x)
{
if(!x) return;
_clear(x->_left);
_clear(x->_right);
del_node(x);
}
node* get_node(const T& val) { return new node(val); }
void del_node(node* x) { delete x; }
int height(node* x) { return x ? x->_h : 0; }
int size(node* x) { return x ? x->_size : 0; }
// 更新x的_h与_size
void push_up(node* x)
{
if (x)
{
x->_h = max(height(x->_left), height(x->_right)) + 1;
x->_size = size(x->_left) + size(x->_right) + 1;
}
}
void update(node* p)
{
while(p)
{
node* g = p->_parent;
int l = height(p->_left), r =height(p->_right);
if(abs(l - r) <= 1)
push_up(p);
else // 平衡破坏，需旋转调整
balance(p);
p = g;
}
}
void balance(node* p)
{
int l = height(p->_left), r = height(p->_right);
if (l > r)
{
int ll = height(p->_left->_left), lr = height(p->_left->_right);
// LL型
if (ll >= lr)
rotateR(p);
// LR型
else {
rotateL(p->_left);
rotateR(p);
}
}
else {
int rr = height(p->_right->_right), rl = height(p->_right->_left);
// RR型
if (rr >= rl)
rotateL(p);
// RL型
else {
rotateR(p->_right);
rotateL(p);
}
}
}
// g g
// | |
// p x
// / \ / \
// x C ====> A p
// / \ / \
// A B B C
void rotateR(node* p) // 右旋
{
node* g = p->_parent;
node* x = p->_left;
p->_left = x->_right;
if(x->_right) x->_right->_parent = p;
x->_right = p;
p->_parent = x;
x->_parent = g;
if(g){
if(p == g->_left) g->_left = x;
else g->_right = x;
}
// 注意需先更新p，再更新x
push_up(p);
push_up(x);
if(_root == p) // 注意可能需要更新根节点
_root = x;
}
// g g
// | |
// p x
// / \ / \
// x C <==== A p
// / \ / \
// A B B C
void rotateL(node* x) // 左旋，与右旋类似
{
node* g = x->_parent;
node* p = x->_right;
x->_right = p->_left;
if(p->_left) p->_left->_parent = x;
p->_left = x;
x->_parent = p;
p->_parent = g;
if(g){
if(x == g->_left) g->_left = p;
else g->_right = p;
}
push_up(x);
push_up(p);
if(_root == x) _root = p;
}
AVL树迭代器
与之前讲的list迭代器类似，这里也需要把AVL树节点的指针封装一下，然后用运算符重载修改其行为。迭代器按中序遍历的顺序。operator++就相当于求后继，operator--就相当于求前驱
// 普通迭代器 ==> 封装node*
template<class T>
struct AVLtree_iterator
{
typedef AVLtree_node<T> node;
typedef node* node_ptr;
typedef AVLtree_iterator Self;
node_ptr _ptr; // 封装节点的指针
node_ptr _root; // 为了处理--end(), 还需额外封装一个_root指向树的根节点
AVLtree_iterator(node_ptr p = nullptr, node_ptr r = nullptr)
:_ptr(p)
,_root(r)
{}
// 前置++，找后继
Self& operator++()
{
// 特判迭代器为end()的情况
if (!_ptr)
assert(false);
// 右子树存在，则右子树的最左侧节点即为后继
if(_ptr->_right)
{
_ptr = _ptr->_right;
while(_ptr->_left)
_ptr = _ptr->_left;
}
// 右子树不存在，向上找第一个右拐的节点
else{
node_ptr p = _ptr->_parent;
while(p && _ptr == p->_right)
{
_ptr = p;
p = p->_parent;
}
_ptr = p;
}
return *this;
}
// 后置++
Self operator++(int)
{
Self tmp(*this);
++(*this);
return tmp;
}
// 前置--，找前驱
Self& operator--()
{
// 特判迭代器为end()的情况
if(!_ptr){
if (!_root) // 空树应当直接报错
assert(false);
// 找最后一个节点
_ptr = _root;
while(_ptr->_right)
_ptr = _ptr->_right;
return *this;
}
// 左子树存在，则左子树的最右侧节点即为前驱
if(_ptr->_left)
{
_ptr = _ptr->_left;
while(_ptr->_right)
_ptr = _ptr->_right;
}
// 左子树不存在，向上找第一个左拐的节点
else{
node_ptr p = _ptr->_parent;
while(p && _ptr == p->_left)
{
_ptr = p;
p = p->_parent;
}
_ptr = p;
}
return *this;
}
// 后置--
Self operator--(int)
{
Self tmp(*this);
--(*this);
return tmp;
}
bool operator==(const Self& it) const
{ return _ptr == it._ptr; }
bool operator!=(const Self& it) const
{ return _ptr != it._ptr; }
// 下面两个函数已经在list那篇介绍过了
T& operator* () { return _ptr->_val; }
T* operator-> () { return &_ptr->_val; }
};
// const迭代器 ==> 封装 const node*
template<class T>
struct AVLtree_const_iterator
{
typedef AVLtree_node<T> node;
typedef const node* node_ptr;
typedef AVLtree_const_iterator Self;
node_ptr _ptr; // 封装节点的指针
node_ptr _root; // 为了处理--end(), 还需额外封装一个_root指向树的根节点
AVLtree_const_iterator(node_ptr p = nullptr, node_ptr r = nullptr)
:_ptr(p)
,_root(r)
{}
// 有时候可能需要用普通迭代器构造const迭代器
AVLtree_const_iterator(const AVLtree_iterator<T>& it)
:_ptr(it._ptr)
,_root(it._root)
{}
// ++/--/==/!= 的代码与普通迭代器的一样
const T& operator* () { return _ptr->_val; }
const T* operator-> () { return &_ptr->_val; }
};
再添加begin与end函数
template<class T>
class AVLtree
{
// ...省略其他代码
public:
typedef AVLtree_iterator<T> iterator;
iterator begin() // 返回中序遍历第一个，即最左侧元素
{
if (!_root) return { _root, _root };
node* cur = _root;
while (cur->_left) cur = cur->_left;
return { cur, _root };
}
iterator end() { return { nullptr, _root }; }
typedef AVLtree_const_iterator<T> const_iterator;
const_iterator begin() const
{
if (!_root) return { _root, _root };
node* cur = _root;
while (cur->_left) cur = cur->_left;
return { cur, _root };
}
const_iterator end() const { return { nullptr, _root }; }
// ...省略其他代码
};
注：若树中执行插入/删除，根节点可能会改变，迭代器就会失效。
（拓展：如果AVL树额外设置了哨兵节点，例如哨兵节点的有个指针指向_root，然后end()返回的并不是nullptr而是哨兵，这样的话–end()也能找到最右侧节点，迭代器就无需添加根节点指针了。）
测试
void test01()
{
int a[] = { -16, 3, 7, -11, -9, 26, 18, -14, -15 };
AVLtree<int> t;
for (auto e : a) t.insert(e);
for (auto it = t.begin(); it != t.end(); ++it)
cout << *it << ' ';
cout << endl;
auto it = t.begin();
*it = 999; // 普通迭代器，可修改内容
for (auto it = t.begin(); it != t.end(); ++it)
cout << *it << ' ';
cout << endl;
const AVLtree<int> t1;
for (auto e : a) t1.insert(e);
for (auto it = t1.begin(); it != t1.end(); ++it)
{
cout << *it << ' ';
//*it = 10; // err 不可修改
}
}
运行结果
但是有个问题，二叉搜索树每个节点都是有关联性的（根据节点权值排列），如果通过迭代器修改了树中节点的权值，可能会破坏二叉搜索树的性质，为此需要将AVL树进一步封装成set、map
AVL树自定义比较顺序
上篇写的AVL树中序遍历只能按从小到大的顺序，但有时候可能会按其他顺序（例如按绝对值从小到大等），为此需要额外提供比较函数。
template<class T, class Compare = less<T>>
class AVLtree
{
typedef AVLtree_node<T> node;
protected:
node* _root = nullptr;
Compare _cmp;
// _cmp(t1, t2): 若t1在t2的前面，返回true，否则返回false
public:
// ...省略迭代器等代码
// 顺便把find与insert的返回值改为迭代器
// find返回值：找到了返回 值为val的迭代器，否则返回val应当插入位置的父节点的迭代器
iterator find(const T& val)
{
node* cur = _root;
node* p = nullptr; // 记录cur的父节点
while (cur)
{
p = cur;
if (_cmp(val, cur->_val)) // val < cur->_val
cur = cur->_left;
else if (_cmp(cur->_val, val)) // val > cur->_val
cur = cur->_right;
else
return { cur, _root }; // 迭代器提供了相关的构造
}
return { p, _root };
}
// insert返回值：值为val的迭代器
iterator insert(const T& val)
{
if (!_root)
{
_root = get_node(val);
return {_root, _root};
}
node* cur = find(val)._ptr;
if(_cmp(cur->_val, val) || _cmp(val, cur->_val)) // cur->_val != val
{
node* p = cur;
cur = get_node(val);
cur->_parent = p;
if (_cmp(val, p->_val)) // val < p->_val
p->_left = cur;
else
p->_right = cur;
update(cur);
}
return {cur, _root};;
}
// ...省略其他代码
};
测试
struct my_cmp
{
// 按绝对值大小比较
bool operator()(int a, int b) const
{
return abs(a) < abs(b);
}
};
void test02()
{
int a[] = {-16, 3, 7, -11, -9, 26, 18, -14, -15};
AVLtree<int> t;
AVLtree<int, my_cmp> t1;
for (auto e : a)
{
t.insert(e);
t1.insert(e);
}
for (auto e : t)
cout << e << ' ';
cout << endl;
for (auto e : t1)
cout << e << ' ';
}
运行结果
兼容set与map
我们上述实现的AVL只能封装set，因为AVL内部元素key的排列方式就按key的先后顺序。
由于map存储的元素是pair<key, value>，排列顺序是按key而非pair<key, value>。为了兼容map，需再额外修改一下AVL树
template<class K, class T, class K_of_T, class Compare = less<K>>
class AVLtree
{
typedef AVLtree_node<T> node;
typedef AVLtree_node<T>* node_ptr;
protected:
node* _root = nullptr;
Compare _cmp;
K_of_T _get_key;
}
新增了两个模板参数：K与K_of_T
K：代表key的类型。容器中的元素需按key的先后顺序排列
T：容器中的元素类型。例如set存储的是key，而map存储的是pair<key,value>
K_of_T：仿函数，用于根据容器中的元素求得对应的key。例如set的key就是其存储的元素，而map的key是存储的元素.first
Compare：仿函数，用于确定key的先后顺序
然后再修该一下find与insert函数
// 根据key查找
iterator find(const K& key)
{
node* cur = _root;
node* p = nullptr;
while (cur)
{
p = cur;
// 需要对_val再套一层_get_key求其key值
if (_cmp(key, _get_key(cur->_val))) // val < cur->_val
cur = cur->_left;
else if (_cmp(_get_key(cur->_val), key)) // val > cur->_val
cur = cur->_right;
else
return { cur, _root };
}
return { p, _root };
}
// 插入的元素应该是T
iterator insert(const T& val)
{
if (!_root)
{
_root = get_node(val);
return {_root, _root};
}
// 下面也是类似，对_val再套一层_get_key
node* cur = find(_get_key(val))._ptr;
if(_cmp(_get_key(cur->_val), _get_key(val)) || _cmp(_get_key(val), _get_key(cur->_val))) // cur->_val != val
{
node* p = cur;
cur = get_node(val);
cur->_parent = p;
if (_cmp(_get_key(val), _get_key(p->_val))) // val < p->_val
p->_left = cur;
else
p->_right = cur;
update(cur);
}
return {cur, _root};;
}
封装set
成员变量
由于不可以修改set内部元素（修改会破坏二叉搜索树性质），所以我们对其数据类型加上const
template<class T, class Compare = less<T>>
class set
{
protected:
typedef T K; // set就是根据存储的元素排序的
struct set_key_of_T
{
const K& operator()(const T& t) const
{
return t;
}
};
// 存储的元素类型加上const，防止修改
typedef AVLtree<K, const T, set_key_of_T, Compare> tree_type;
tree_type _t;
};
迭代器
直接用AVL的即可
typedef tree_type::iterator iterator;
typedef tree_type::const_iterator const_iterator;
iterator begin() { return _t.begin(); }
iterator end() { return _t.end(); }
const_iterator begin() const { return _t.begin(); }
const_iterator end() const { return _t.end(); }
由于树的节点_val是const T类型，AVL树的普通迭代器解引用会返回const T&，AVL树的const迭代器解引用会返回const const K&。
补充知识：const const K&是什么类型呢？
答：const重复修饰同一个类型时，编译器会将其视为冗余，最终类型不变。const const K&等价于const K&。
例如：
这样的话无论用普通迭代器还是const迭代器，都不能修改内部数据
封装find与insert
// 注意set的find与AVL的find不同
// AVL的find：找到了返回对应权值的迭代器，否则返回其父节点的迭代器
// set的find：找到了返回对应权值的迭代器，否则返回end()
iterator find(const K& key)
{
if(_t.empty()) return _t.end();
Compare cmp;
auto it = _t.find(key);
if(!cmp(*it, key) && !cmp(key, *it)) // *it == key
return it;
return _t.end();
}
// 基于find，我们顺便封装一下count
// 返回set中值为key的元素个数。找到了返回1，否则返回0
int count(const K& key) {
return find(key) != end();
}
// 注意set的insert与AVL的insert不同
// AVL的insert：返回值为val的迭代器
// set的insert：返回值是pair类型，<值为val的迭代器, bool>
pair<iterator, bool> insert(const T& val)
{
int old_size = _t.size();
auto it = _t.insert(val);
if(_t.size() == old_size) // 插入后容器大小不变，说明插入失败；否则插入成功
return {it, false};
else
return {it, true};
}
封装lower_bound与upper_bound
// 查询set中 >= key的最小的元素
iterator lower_bound(const K& key)
{
if(_t.empty()) return _t.end();
Compare cmp;
auto it = _t.find(key);
// 存在key，返回的就是key；
// 否则返回的是key应该插入位置的父节点的迭代器，其父节点只能是key的前驱或后继！！！
if(cmp(*it, key)) // *it < key
++it;
return it;
}
// 查询set中 > key的最小的元素
iterator upper_bound(const K& key)
{
if(_t.empty()) return _t.end();
Compare cmp;
auto it = _t.find(key);
if(cmp(key, *it)) // *it > key
return it;
return ++it;
}
// 顺便提供size与empty函数
int size() { return _t.size(); }
bool empty() { return _t.empty(); }
封装erase（选看）
AVL树中的erase如下：（加上迭代器、比较函数、以及K_of_T）
bool erase(const K& key)
{
if(!_root) return false;
node* cur = find(key)._ptr;
if(!_cmp(_get_key(cur->_val), key) && !_cmp(key, _get_key(cur->_val))) // key == cur->_val
{
node* p = cur->_parent;
// 1.叶子节点：直接删除
if(!cur->_left && !cur->_right)
{
if(!p) _root = nullptr; // 特判只有一个节点
else if(cur == p->_left)
p->_left = nullptr;
else
p->_right = nullptr;
del_node(cur);
update(p); // 删除后从父节点往上更新
}
// 2.只有一个儿子：用儿子替代
else if(!cur->_left || !cur->_right)
{
node* child = cur->_left ? cur->_left : cur->_right;
if(!p) _root = child; // 特判只有一个节点
else if(p->_left == cur)
p->_left = child;
else
p->_right = child;
child->_parent = p; // 别忘记连接父节点
del_node(cur);
update(p); // 删除后从父节点往上更新
}
// 3.有两个儿子: 用前驱替代，然后删除前驱
else{
// 找前驱
node* pre = cur->_left;
node* pre_parent = cur;
while(pre->_right)
{
pre_parent = pre;
pre = pre->_right;
}
// 交换，然后删除前驱节点
std::swap(cur->_val, pre->_val);
// 到这里pre必定没有右儿子
if(pre_parent->_left == pre)
pre_parent->_left = pre->_left;
else
pre_parent->_right = pre->_left;
if(pre->_left)
pre->_left->_parent = pre_parent;
del_node(pre);
update(pre_parent); // 删除pre后，需从其父节点往上更新
}
return true;
}
return false;
}
由于我set为了防止修改存储的元素，给其加上了const。
但erase的第三种情况（被删除节点有两个儿子），我是把两个节点的值进行交换std::swap(cur->_val, pre->_val);这就会报错。
为此需要修改指针，将pre直接移动到cur的位置
情况三修改后的代码：
// 3.有两个儿子: 用前驱替代，然后删除前驱
else{
// 找前驱
node* pre = cur->_left;
node* pre_parent = cur;
while(pre->_right)
{
pre_parent = pre;
pre = pre->_right;
}
// 移动指针需特判pre就是cur的左儿子的情况
node* x = cur, *y = pre;
node* xp = x->_parent, *xl = x->_left, *xr = x->_right;
node* yp = y->_parent, *yl = y->_left;
if(yp->_left == y){
// 该情况说明y的父节点就是x
y->_parent = xp;
if(xp){
if(xp->_left == x) xp->_left = y;
else xp->_right = y;
}
else _root = y;
y->_right = xr;
xr->_parent = y;
update(y);
}
else{
// 该情况说明y的父节点不是x
yp->_right = yl;
if(yl) yl->_parent = yp;
y->_parent = x->_parent;
if(x->_parent){
if(x->_parent->_left == x)
x->_parent->_left = y;
else
x->_parent->_right = y;
}
else _root = y;
y->_left = xl;
xl->_parent = y;
y->_right = xr;
xr->_parent = y;
update(yp);
}
del_node(x);
}
然后set封装的erase就可以这样写了：
int erase(const key_type& key) { return _t.erase(key); }
封装map
此部分与封装set类似，只不过需要按K比较
成员变量
template<class K, class V, class Compare = less<K>>
class map
{
protected:
// map存储的元素类型实际是pair<K, V>
typedef pair<const K, V> T; // 防止key被修改，这里加上const
struct map_key_of_T
{
const K& operator()(const T& t) const
{
return t.first;
}
};
typedef AVLtree<K, T, map_key_of_T, Compare> tree_type;
tree_type _t;
};
迭代器
直接用AVL的即可
typedef tree_type::iterator iterator;
typedef tree_type::const_iterator const_iterator;
iterator begin() { return _t.begin(); }
iterator end() { return _t.end(); }
const_iterator begin() const { return _t.begin(); }
const_iterator end() const { return _t.end(); }
封装find与insert
// 按K类型查找
iterator find(const K& key)
{
if(_t.empty()) return _t.end();
Compare cmp;
auto it = _t.find(key);
// 注意是按K比较，而非T
if(!cmp(it->first, key) && !cmp(key, it->first)) // *it == key
return it;
return _t.end();
}
// 插入T类型元素
pair<iterator, bool> insert(const T& val)
{
int old_size = _t.size();
auto it = _t.insert(val);
if(_t.size() == old_size) // 插入后容器大小不变，说明插入失败；否则插入成功
return {it, false};
else
return {it, true};
}
封装operator[]
V& operator[](const K& key)
{
return insert({key, V()}).first->second;
}
封装lower_bound与upper_bound
iterator lower_bound(const K& key)
{
if(_t.empty()) return _t.end();
Compare cmp;
auto it = _t.find(key);
if(cmp(it->first, key)) // *it < key
++it;
return it;
}
iterator upper_bound(const K& key)
{
if(_t.empty()) return _t.end();
Compare cmp;
auto it = _t.find(key);
if(cmp(key, it->first)) // *it > key
return it;
return ++it;
}
封装erase与set那部分类似（需要对AVL的erase额外修改一下）
int erase(const K& key) { return _t.erase(key); }
完整代码
额外补充了const类型的函数封装
AVLtree.h
#pragma once
#include<iostream>
#include<assert.h>
using namespace std;
template<class T>
struct AVLtree_node
{
T _val; // 权值
int _h; // 以该节点为根的子树的高度（为了保持平衡）
int _size; // 以该节点为根的子树的大小（为了可以查询树中排名第k的节点）
AVLtree_node* _left; // 左儿子
AVLtree_node* _right; // 右儿子
AVLtree_node* _parent; // 父节点
AVLtree_node(const T& x = T())
:_val(x)
,_h(1)
,_size(1)
,_left(nullptr)
,_right(nullptr)
,_parent(nullptr)
{}
};
template<class T>
struct AVLtree_iterator
{
typedef AVLtree_node<T> node;
typedef node* node_ptr;
typedef AVLtree_iterator Self;
node_ptr _ptr; // 封装节点的指针
node_ptr _root; // 为了处理--end(), 还需额外封装一个_root指向树的根节点
AVLtree_iterator(node_ptr p = nullptr, node_ptr r = nullptr)
:_ptr(p)
,_root(r)
{}
// 前置++，找后继
Self& operator++()
{
// 特判迭代器为end()的情况
if (!_ptr)
assert(false);
// 右子树存在，则右子树的最左侧节点即为后继
if(_ptr->_right)
{
_ptr = _ptr->_right;
while(_ptr->_left)
_ptr = _ptr->_left;
}
// 右子树不存在，向上找第一个右拐的节点
else{
node_ptr p = _ptr->_parent;
while(p && _ptr == p->_right)
{
_ptr = p;
p = p->_parent;
}
_ptr = p;
}
return *this;
}
// 后置++
Self operator++(int)
{
Self tmp(*this);
++(*this);
return tmp;
}
// 前置--，找前驱
Self& operator--()
{
// 特判迭代器为end()的情况
if(!_ptr){
if (!_root) // 空树应当直接报错
assert(false);
// 找最后一个节点
_ptr = _root;
while(_ptr->_right)
_ptr = _ptr->_right;
return *this;
}
// 左子树存在，则左子树的最右侧节点即为前驱
if(_ptr->_left)
{
_ptr = _ptr->_left;
while(_ptr->_right)
_ptr = _ptr->_right;
}
// 左子树不存在，向上找第一个左拐的节点
else{
node_ptr p = _ptr->_parent;
while(p && _ptr == p->_left)
{
_ptr = p;
p = p->_parent;
}
_ptr = p;
}
return *this;
}
// 后置--
Self operator--(int)
{
Self tmp(*this);
--(*this);
return tmp;
}
bool operator==(const Self& it) const
{ return _ptr == it._ptr; }
bool operator!=(const Self& it) const
{ return _ptr != it._ptr; }
// 下面两个函数已经在list那篇介绍过了
T& operator* () { return _ptr->_val; }
T* operator-> () { return &_ptr->_val; }
};
template<class T>
struct AVLtree_const_iterator
{
typedef AVLtree_node<T> node;
typedef const node* node_ptr;
typedef AVLtree_const_iterator Self;
node_ptr _ptr; // 封装节点的指针
node_ptr _root; // 为了处理--end(), 还需额外封装一个_root指向树的根节点
AVLtree_const_iterator(node_ptr p = nullptr, node_ptr r = nullptr)
:_ptr(p)
,_root(r)
{}
// 有时候可能需要用普通迭代器构造const迭代器
AVLtree_const_iterator(const AVLtree_iterator<T>& it)
:_ptr(it._ptr)
,_root(it._root)
{}
// 前置++，找后继
Self& operator++()
{
// 特判迭代器为end()的情况
if (!_ptr)
assert(false);
// 右子树存在，则右子树的最左侧节点即为后继
if(_ptr->_right)
{
_ptr = _ptr->_right;
while(_ptr->_left)
_ptr = _ptr->_left;
}
// 右子树不存在，向上找第一个右拐的节点
else{
node_ptr p = _ptr->_parent;
while(p && _ptr == p->_right)
{
_ptr = p;
p = p->_parent;
}
_ptr = p;
}
return *this;
}
// 后置++
Self operator++(int)
{
Self tmp(*this);
++(*this);
return tmp;
}
// 前置--，找前驱
Self& operator--()
{
// 特判迭代器为end()的情况
if(!_ptr){
if (!_root) // 空树应当直接报错
assert(false);
// 找最后一个节点
_ptr = _root;
while(_ptr->_right)
_ptr = _ptr->_right;
return *this;
}
// 左子树存在，则左子树的最右侧节点即为前驱
if(_ptr->_left)
{
_ptr = _ptr->_left;
while(_ptr->_right)
_ptr = _ptr->_right;
}
// 左子树不存在，向上找第一个左拐的节点
else{
node_ptr p = _ptr->_parent;
while(p && _ptr == p->_left)
{
_ptr = p;
p = p->_parent;
}
_ptr = p;
}
return *this;
}
// 后置--
Self operator--(int)
{
Self tmp(*this);
--(*this);
return tmp;
}
bool operator==(const Self& it) const
{ return _ptr == it._ptr; }
bool operator!=(const Self& it) const
{ return _ptr != it._ptr; }
const T& operator* () { return _ptr->_val; }
const T* operator-> () { return &_ptr->_val; }
};
template<class K, class T, class K_of_T, class Compare = less<K>>
class AVLtree
{
typedef AVLtree_node<T> node;
typedef AVLtree_node<T>* node_ptr;
protected:
node* _root = nullptr;
Compare _cmp;
K_of_T _get_key;
public:
void print() { _print(_root); }
void _print(node* x)
{
if(!x) return;
_print(x->_left);
cout << x->_val << ' ';
_print(x->_right);
}
typedef AVLtree_iterator<T> iterator;
iterator begin() // 返回中序遍历第一个，即最左侧元素
{
if (!_root) return { _root, _root };
node* cur = _root;
while (cur->_left) cur = cur->_left;
return { cur, _root };
}
iterator end() { return { nullptr, _root }; }
typedef AVLtree_const_iterator<T> const_iterator;
const_iterator begin() const
{
if (!_root) return { _root, _root };
node* cur = _root;
while (cur->_left) cur = cur->_left;
return { cur, _root };
}
const_iterator end() const { return { nullptr, _root }; }
// 根据key查找
iterator find(const K& key)
{
node* cur = _root;
node* p = nullptr;
while (cur)
{
p = cur;
// 需要对_val再套一层_get_key求的其key值
if (_cmp(key, _get_key(cur->_val))) // val < cur->_val
cur = cur->_left;
else if (_cmp(_get_key(cur->_val), key)) // val > cur->_val
cur = cur->_right;
else
return { cur, _root };
}
return { p, _root };
}
// 新增const类型的find
const_iterator find(const K& key) const
{
const node* cur = _root;
const node* p = nullptr;
while (cur)
{
p = cur;
// 需要对_val再套一层_get_key求的其key值
if (_cmp(key, _get_key(cur->_val))) // val < cur->_val
cur = cur->_left;
else if (_cmp(_get_key(cur->_val), key)) // val > cur->_val
cur = cur->_right;
else
return { cur, _root };
}
return { p, _root };
}
// 插入的元素应该是T
iterator insert(const T& val)
{
if (!_root)
{
_root = get_node(val);
return {_root, _root};
}
node* cur = find(_get_key(val))._ptr;
// 这里也是类似，对_val再套一层_get_key
if(_cmp(_get_key(cur->_val), _get_key(val)) || _cmp(_get_key(val), _get_key(cur->_val))) // cur->_val != val
{
node* p = cur;
cur = get_node(val);
cur->_parent = p;
if (_cmp(_get_key(val), _get_key(p->_val))) // val < p->_val
p->_left = cur;
else
p->_right = cur;
update(cur);
}
return {cur, _root};;
}
bool erase(const K& key)
{
if(!_root) return false;
node* cur = find(key)._ptr;
if(!_cmp(_get_key(cur->_val), key) && !_cmp(key, _get_key(cur->_val)))
{
node* p = cur->_parent;
// 1.叶子节点：直接删除
if(!cur->_left && !cur->_right)
{
if(!p) _root = nullptr; // 特判只有一个节点
else if(cur == p->_left)
p->_left = nullptr;
else
p->_right = nullptr;
del_node(cur);
update(p); // 删除后从父节点往上更新
}
// 2.只有一个儿子：用儿子替代
else if(!cur->_left || !cur->_right)
{
node* child = cur->_left ? cur->_left : cur->_right;
if(!p) _root = child; // 特判只有一个节点
else if(p->_left == cur)
p->_left = child;
else
p->_right = child;
child->_parent = p; // 别忘记连接父节点
del_node(cur);
update(p); // 删除后从父节点往上更新
}
// 3.有两个儿子: 用前驱替代，然后删除前驱
else{
// 找前驱
node* pre = cur->_left;
node* pre_parent = cur;
while(pre->_right)
{
pre_parent = pre;
pre = pre->_right;
}
// // 交换，然后删除前驱节点
// std::swap(cur->_val, pre->_val);
// // 到这里pre必定没有右儿子
// if(pre_parent->_left == pre)
// pre_parent->_left = pre->_left;
// else
// pre_parent->_right = pre->_left;
// if(pre->_left)
// pre->_left->_parent = pre_parent;
// del_node(pre);
// update(pre_parent); // 删除pre后，需从其父节点往上更新
node* x = cur, *y = pre;
node* xp = x->_parent, *xl = x->_left, *xr = x->_right;
node* yp = y->_parent, *yl = y->_left;
if(yp->_left == y){
// 该情况说明y的父节点就是x
y->_parent = xp;
if(xp){
if(xp->_left == x) xp->_left = y;
else xp->_right = y;
}
else _root = y;
y->_right = xr;
xr->_parent = y;
update(y);
}
else{
// 该情况说明y的父节点不是x
yp->_right = yl;
if(yl) yl->_parent = yp;
y->_parent = x->_parent;
if(x->_parent){
if(x->_parent->_left == x)
x->_parent->_left = y;
else
x->_parent->_right = y;
}
else _root = y;
y->_left = xl;
xl->_parent = y;
y->_right = xr;
xr->_parent = y;
update(yp);
}
del_node(x);
}
return true;
}
return false;
}
int size() const { return size(_root); }
bool empty() const { return !_root; }
void clear()
{
_clear(_root);
_root = nullptr;
}
protected:
void _clear(node* x)
{
if(!x) return;
_clear(x->_left);
_clear(x->_right);
del_node(x);
}
node* get_node(const T& val) { return new node(val); }
void del_node(node* x) { delete x; }
// 计算以x为根的子树的高度
int height(node* x) { return x ? x->_h : 0; }
// 计算以x为根的子树的大小
int size(node* x) const { return x ? x->_size : 0; }
// 更新x的_h与_size
void push_up(node* x)
{
if (x)
{
x->_h = max(height(x->_left), height(x->_right)) + 1;
x->_size = size(x->_left) + size(x->_right) + 1;
}
}
void update(node* p)
{
while(p)
{
node* g = p->_parent;
int l = height(p->_left), r =height(p->_right);
if(abs(l - r) <= 1)
push_up(p);
else // 平衡破坏，需旋转调整
balance(p);
p = g;
}
}
void balance(node* p)
{
int l = height(p->_left), r = height(p->_right);
if (l > r)
{
int ll = height(p->_left->_left), lr = height(p->_left->_right);
// LL型
if (ll >= lr)
rotateR(p);
// LR型
else {
rotateL(p->_left);
rotateR(p);
}
}
else {
int rr = height(p->_right->_right), rl = height(p->_right->_left);
// RR型
if (rr >= rl)
rotateL(p);
// RL型
else {
rotateR(p->_right);
rotateL(p);
}
}
}
// g g
// | |
// p x
// / \ / \
// x C ====> A p
// / \ / \
// A B B C
void rotateR(node* p) // 右旋
{
node* g = p->_parent;
node* x = p->_left;
p->_left = x->_right;
if(x->_right) x->_right->_parent = p;
x->_right = p;
p->_parent = x;
x->_parent = g;
if(g){
if(p == g->_left) g->_left = x;
else g->_right = x;
}
// 注意需先更新p，再更新x
push_up(p);
push_up(x);
if(_root == p) // 注意可能需要更新根节点
_root = x;
}
// g g
// | |
// p x
// / \ / \
// x C <==== A p
// / \ / \
// A B B C
void rotateL(node* x) // 左旋，与右旋类似
{
node* g = x->_parent;
node* p = x->_right;
x->_right = p->_left;
if(p->_left) p->_left->_parent = x;
p->_left = x;
x->_parent = p;
p->_parent = g;
if(g){
if(x == g->_left) g->_left = p;
else g->_right = p;
}
push_up(x);
push_up(p);
if(_root == x) _root = p;
}
};
set_map.h
#include"AVLtree.h"
template<class T, class Compare = less<T>>
class set
{
public:
typedef T K;
protected:
struct set_key_of_T
{
const K& operator()(const T& t) const
{
return t;
}
};
// 存储的元素类型加上const，防止修改
typedef AVLtree<K, const T, set_key_of_T, Compare> tree_type;
tree_type _t;
public:
set(){}
set(initializer_list<T> il)
{
for(auto& e : il)
_t.insert(e);
}
template<class InputIterator>
set(InputIterator first, InputIterator last)
{
while(first != last)
{
_t.insert(*first);
++first;
}
}
typedef tree_type::iterator iterator;
typedef tree_type::const_iterator const_iterator;
iterator begin() { return _t.begin(); }
iterator end() { return _t.end(); }
const_iterator begin() const { return _t.begin(); }
const_iterator end() const { return _t.end(); }
// 注意set的find与AVL的find不同
// AVL的find：找到了返回对应权值的迭代器，否则返回其父节点的迭代器
// set的find：找到了返回对应权值的迭代器，否则返回end()
iterator find(const K& key)
{
if(_t.empty()) return _t.end();
Compare cmp;
auto it = _t.find(key);
if(!cmp(*it, key) && !cmp(key, *it)) // *it == key
return it;
return _t.end();
}
// 新增const类型的find
const_iterator find(const K& key) const
{
if(_t.empty()) return _t.end();
Compare cmp;
auto it = _t.find(key);
if(!cmp(*it, key) && !cmp(key, *it)) // *it == key
return it;
return _t.end();
}
int count(const K& key) const
{
return find(key) != end();
}
// 查询set中 >= key的最小的元素
iterator lower_bound(const K& key)
{
if(_t.empty()) return _t.end();
Compare cmp;
auto it = _t.find(key); // 存在key，返回的就是key；否则只能是key的前驱/后继
if(cmp(*it, key)) // *it < key
++it;
return it;
}
// 新增const类型的lower_bound
const_iterator lower_bound(const K& key) const
{
if(_t.empty()) return _t.end();
Compare cmp;
auto it = _t.find(key); // 存在key，返回的就是key；否则只能是key的前驱/后继
if(cmp(*it, key)) // *it < key
++it;
return it;
}
// 查询set中 > key的最小的元素
iterator upper_bound(const K& key)
{
if(_t.empty()) return _t.end();
Compare cmp;
auto it = _t.find(key);
if(cmp(key, *it)) // *it > key
return it;
return ++it;
}
// 新增const类型的upper_bound
const_iterator upper_bound(const K& key) const
{
if(_t.empty()) return _t.end();
Compare cmp;
auto it = _t.find(key);
if(cmp(key, *it)) // *it > key
return it;
return ++it;
}
pair<iterator, bool> insert(const T& val)
{
int old_size = _t.size();
auto it = _t.insert(val);
if(_t.size() == old_size) // 插入后容器大小不变，说明插入失败；否则插入成功
return {it, false};
else
return {it, true};
}
int erase(const K& key) { return _t.erase(key); }
int size() const { return _t.size(); }
bool empty() const { return _t.empty(); }
void clear() { return _t.clear(); }
};
template<class K, class V, class Compare = less<K>>
class map
{
protected:
typedef pair<const K, V> T; // 防止key被修改，这里加上const
struct map_key_of_T
{
const K& operator()(const T& t) const
{
return t.first;
}
};
typedef AVLtree<K, T, map_key_of_T, Compare> tree_type;
tree_type _t;
public:
map(){}
map(initializer_list<T> il)
{
for(auto& e : il)
_t.insert(e);
}
template<class InputIterator>
map(InputIterator first, InputIterator last)
{
while(first != last)
{
_t.insert(*first);
++first;
}
}
typedef tree_type::iterator iterator;
typedef tree_type::const_iterator const_iterator;
iterator begin() { return _t.begin(); }
iterator end() { return _t.end(); }
const_iterator begin() const { return _t.begin(); }
const_iterator end() const { return _t.end(); }
// 注意set的find与AVL的find不同
// AVL的find：找到了返回对应权值的迭代器，否则返回其父节点的迭代器
// set的find：找到了返回对应权值的迭代器，否则返回end()
iterator find(const K& key)
{
if(_t.empty()) return _t.end();
Compare cmp;
auto it = _t.find(key);
if(!cmp(it->first, key) && !cmp(key, it->first)) // *it == key
return it;
return _t.end();
}
// 新增const类型的find
const_iterator find(const K& key) const
{
if(_t.empty()) return _t.end();
Compare cmp;
auto it = _t.find(key);
if(!cmp(it->first, key) && !cmp(key, it->first)) // *it == key
return it;
return _t.end();
}
int count(const K& key) const
{
return find(key) != end();
}
iterator lower_bound(const K& key)
{
if(_t.empty()) return _t.end();
Compare cmp;
auto it = _t.find(key); // 存在key，返回的就是key；否则只能是key的前驱/后继
if(cmp(it->first, key)) // *it < key
++it;
return it;
}
// 新增const类型的lower_bound
const_iterator lower_bound(const K& key) const
{
if(_t.empty()) return _t.end();
Compare cmp;
auto it = _t.find(key); // 存在key，返回的就是key；否则只能是key的前驱/后继
if(cmp(it->first, key)) // *it < key
++it;
return it;
}
iterator upper_bound(const K& key)
{
if(_t.empty()) return _t.end();
Compare cmp;
auto it = _t.find(key);
if(cmp(key, it->first)) // *it > key
return it;
return ++it;
}
// 新增const类型的upper_bound
const_iterator upper_bound(const K& key) const
{
if(_t.empty()) return _t.end();
Compare cmp;
auto it = _t.find(key);
if(cmp(key, it->first)) // *it > key
return it;
return ++it;
}
pair<iterator, bool> insert(const T& val)
{
int old_size = _t.size();
auto it = _t.insert(val);
if(_t.size() == old_size) // 插入后容器大小不变，说明插入失败；否则插入成功
return {it, false};
else
return {it, true};
}
V& operator[](const K& key)
{
return insert({key, V()}).first->second;
}
int erase(const K& key) { return _t.erase(key); }
int size() const { return _t.size(); }
bool empty() const { return _t.empty(); }
void clear() { return _t.clear(); }
};
感谢观看
Agent 垂直技术社区，欢迎活跃、内容共建。
更多推荐
31
0- 0
已为社区贡献10条内容
所有评论(0)