目录
1、set的简述
在STL中，容器分为序列式容器和关联式容器，前面学习的vector、list、deque就是序列式容器，在序列式容器中，数据之间的关联性不强，顺序是可以任意的。现在学的set和下一节的map是关联式容器，数据之间有很强的关联，顺序不能任意。
set有点类似于上一节二叉搜索树中的K模型，底层是使用红黑树实现的，仿函数默认是less，即比根小的往左走，比根大的往右走
void test_set1()
{
set<int> s;
s.insert(5);
s.insert(2);
s.insert(7);
s.insert(4);
s.insert(9);
s.insert(1);
s.insert(5);
s.insert(2);
s.insert(0);
s.insert(7);
s.insert(7);
set<int>::iterator it = s.begin();
while (it != s.end())
{
cout << *it << " ";
it++;
}
}结果是
会发现变成有序了，所以迭代器默认走的是中序遍历，并且set中若是重复了，则不会再插入，是去重 + 排序
2、set的使用
2.1 构造函数和拷贝构造
set支持3中形式的构造，普通构造、迭代器区间构造、拷贝构造
2.2 析构函数
我们会发现，在我们上一节的二叉搜索树模拟实现中，并没有实现析构函数，那么树形结构需要如何写析构函数呢？析构函数是没有参数的，但是树形结构想要完成析构，就需要使用到递归，也就是需要传参数，所以可以写一个子函数
拷贝构造也是同理，在这里对上一节的K模型的二叉搜索树进行完善，加入拷贝构造函数和析构函数
template<class K>
struct BSTNode // 二叉搜索树的结点
{
K _key;
BSTNode<K>* _left;
BSTNode<K>* _right;
BSTNode(const K& key)
:_key(key)
, _left(nullptr)
, _right(nullptr)
{}
};
template<class K>
class BSTree
{
typedef BSTNode<K> Node;
public:
BSTree() = default;
~BSTree()
{
Destroy(_root);
_root = nullptr;
}
BSTree(const BSTree<K>& t)
{
_root = Copy(t._root);
}
bool Find(const K& key)
{
Node* cur = _root;
while (cur) // 不为空时就继续找
{
if (cur->_key < key) cur = cur->_right;
else if (cur->_key > key) cur = cur->_left;
else return true; // 找到了返回true
}
return false; // 没找到返回false
}
bool Insert(const K& key)
{
// 判断根节点是否为空
if (_root == nullptr)
{
_root = new Node(key);
return true;
}
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
if (cur->_key < key)
{
parent = cur;
cur = cur->_right;
}
else if (cur->_key > key)
{
parent = cur;
cur = cur->_left;
}
else return false;
}
Node* newNode = new Node(key);
if (parent->_key < key) parent->_right = newNode;
else parent->_left = newNode;
return true;
}
void InOrder()
{
_InOrder(_root);
}
bool Erase(const K& key)
{
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
if (cur->_key < key)
{
parent = cur;
cur = cur->_right;
}
else if (cur->_key > key)
{
parent = cur;
cur = cur->_left;
}
else // 此时已经找到了要删除的结点
{
// 要删除的结点只有一个孩子或者没有孩子,此时只需要把它的孩子给他的父亲结点
if (cur->_left == nullptr)
{
// 判断cur是父亲的左孩子还是右孩子
if (parent->_left == cur) parent->_left = cur->_right;
else parent->_right = cur->_right;
delete cur;
return true;
}
else if (cur->_right == nullptr)
{
if (parent->_left == cur) parent->_left = cur->_left;
else parent->_right = cur->_left;
delete cur;
return true;
}
// 要删除的结点有两个孩子
else
{
// 先去右子树中寻找值最小的结点，也就是右子树最左边的那个结点
Node* rightMin = cur->_right;
Node* rightMinP = cur;
while (rightMin->_left)
{
rightMinP = rightMin;
rightMin = rightMin->_left;
}
cur->_key = rightMin->_key;
if (rightMinP->_left == rightMin)
rightMinP->_left = rightMin->_right;
else
rightMinP->_right = rightMin->_right;
delete rightMin;
return true;
}
}
}
return false;
}
private:
void _InOrder(Node* _root)
{
if (_root == nullptr) return;
_InOrder(_root->_left);
cout << _root->_key << " ";
_InOrder(_root->_right);
}
void Destroy(Node* root)
{
if (root == nullptr) return;
Destroy(root->_left);
Destroy(root->_right);
delete root;
}
Node* Copy(Node* root)
{
// 用前序，递归拷贝左右子树
if (root == nullptr) return nullptr;
Node* newRoot = new Node(root->_key);
newRoot->_left = Copy(root->_left);
newRoot->_right = Copy(root->_right);
return newRoot;
}
Node* _root = nullptr;
};注意：只写了拷贝构造没写其他构造函数是不行的，因为没有默认的构造函数，此时可以使用default强制生成一个默认的
3.2 insert、erase、find
void test_set2()
{
set<int> s;
s.insert(5);
s.insert(2);
s.insert(7);
s.insert(4);
s.insert(9);
s.insert(1);
// 删除最小值
s.erase(s.begin());
Print(s);
// 删除一个存在的元素
s.erase(2);
Print(s);
// 删除一个不存在的元素
s.erase(10);
Print(s);
}结果是
会发现erase是有就删，没有就不删的。若要删除最小值，即删除树最左边的那个结点，也就是begin的结果
如何知道是否删除成功了呢？
法一：利用erase的返回值
void test_set2()
{
set<int> s;
s.insert(5);
s.insert(2);
s.insert(7);
s.insert(4);
s.insert(9);
s.insert(1);
// 删除最小值
s.erase(s.begin());
Print(s);
// 删除一个存在的元素
int num1 = s.erase(2);
if (num1 == 0) cout << "删除失败" << endl;
else cout << "删除成功" << endl;
// 删除一个不存在的元素
int num2 = s.erase(10);
if (num2 == 0) cout << "删除失败" << endl;
else cout << "删除成功" << endl;
}结果是
法二：结合find
find若找到了，则会返回对应结点的迭代器，若没找到，则返回end
可以先调用find。判断set中是否有该元素再erase
void test_set3()
{
set<int> s;
s.insert(5);
s.insert(2);
s.insert(7);
s.insert(4);
s.insert(9);
s.insert(1);
set<int>::iterator it = s.find(9);
if (it != s.end())
{
s.erase(it);
}
Print(s);
}也可以直接一步完成
void test_set3()
{
set<int> s;
s.insert(5);
s.insert(2);
s.insert(7);
s.insert(4);
s.insert(9);
s.insert(1);
s.erase(s.find(9));
Print(s);
}但是，此时若是查找一个不存在的值，返回end后，会直接报错，因为erase里面传end会直接报错
头文件algorithm中有一个find，那么这个find和set自己的find有什么区别呢？
algorithm中的find是从begin，一直到end顺序查找的，而set中的find是按二叉搜索树的查找规则找的，所以若要在set中查找元素，一定要使用set自带的find
3.3 count
count是给一个值，返回当前容器中这个值的个数，在set中可以用来判断这个值在不在
3.4 lower_bound、upper_bound
lower_bound是给一个值，返回第一个大于等于这个值的迭代器
upper_bound是给一个值，返回第一个大于这个值的迭代器
可以配合erase来删除一个区间内所有的元素
void test_bound()
{
std::set<int> myset;
std::set<int>::iterator itlow, itup;
for (int i = 1; i < 10; i++) myset.insert(i * 10); // 10 20 30 40 50 60 70 80 90
itlow = myset.lower_bound(30); // >= 30 ^
itup = myset.upper_bound(60); // > 60 ^
myset.erase(itlow, itup); // 10 20 70 80 90
std::cout << "myset contains:";
for (std::set<int>::iterator it = myset.begin(); it != myset.end(); ++it)
std::cout << ' ' << *it;
std::cout << '\n';
}erase删除区间时是左闭右开的，所以这里右区间使用的是upper_bound
3.5 equal_range
传入一个值，返回这个值在set中的范围，不过因为在set中，值都是唯一的，所以范围中也只有一个元素。如果没有找到匹配项，则返回的长度为0，返回对象的两个迭代器都指向寻找对象之后的第一个元素
注意，equal_range返回的区间是左闭右开的，所以就算这个区间中只有一个值，那么返回的pair对象中的first和second也是不同的
3、multiset
multiset是允许键值冗余的set
所以multiset就不像set一样拥有去重 + 排序的功能了，只拥有排序了
void test_multiset()
{
multiset<int> ms;
ms.insert(5);
ms.insert(2);
ms.insert(7);
ms.insert(4);
ms.insert(9);
ms.insert(1);
ms.insert(7);
for (multiset<int>::iterator it = ms.begin(); it != ms.end(); it++)
{
cout << *it << " ";
}
}结果是
使用默认的仿函数时，比根小的往左，比根大的往右，与根相等的往左往右都可以，因为插入到右边，也可能因为反转而到左边，下面以相等插入到右边为例
multiset与set大部分情况是相同的，下面来讲讲与set的几个不同
1. 有多个相同值时，find(x)，返回的时第一个x的迭代器，即遇到相等了还要先去左子树找
这样子的好处就是拿到第一个，++就可以拿到全部
2. count的作用就不像set中只能判断一个值是否在容器中了，还可以用来判断容器中有几个这个值
3. erase给值进行删除，是删除全部
4. equal_range会返回某个值的左闭右开的区间
