我不熟悉的 set

同样的我着重介绍那些我不怎么用到的系列, 同时, 常用的我就点一下.

我们都知道 set 底层是用红黑树实现的, 红黑树是一种已排序的树, 所以我们通过迭代器来访问节点元素的时候, 并不可以改变它, 如果随意改变, 那排序规则就乱套了.

讲 API 之前, 现介绍一个 对组(pair) 的概念.

对组 (pair) 将一对值组合成一个值, 这一对值可以具有不同的数据类型, 两个值可以分别用 pair 的两个公有属性 first 和 second 访问.

创建对组的方法

一, 使用拷贝构造

pair<string, int> pair1(string("name"), 20);
cout <<pair1.first << endl; // 访问 pair 第一个值
cout << pair1.second << endl;// 访问 pair 第二个值

二, 使用 make_pair

pair<string, int> pair2 = make_pair("name", 30);
cout <<pair2.first << endl;
cout << pair2.second << endl;

对组可以方便的将不同数据类型作为返回值, 一次返回两个数值.

构造, 赋值和大小操作

set<T> st;          //set 默认构造函数.
set(const set &st); // 拷贝构造函数
swap(set st);       // 交换两个集合容器
size();             // 返回容器中元素的数目
empty();            // 判断容器是否为空

与前几篇说的一致.

插入与删除

pair<iterator,bool> insert(elem);  // 在容器中插入元素.
void insert(beg,end)     // 插入 [beg,end) 范围元素
iterator erase(pos);     // 删除 pos 迭代器所指的元素, 返回下一个元素的迭代器.
iterator erase(beg, end);// 删除区间 [beg,end) 的所有元素 , 返回下一个元素的迭代器.
size_type erase(elem);   // 删除容器中值为 elem 的元素.
void clear();            // 清除所有元素

这边强调一下 erase 和 insert:

关于 erase:

既可以删除迭代器指向的元素, 也可以删除指定的元素值. 与 list 一致.

删除迭代器的时候返回指向的下一个迭代器.

删除指定元素的时候, 返回的是这个元素在容器中的个数.(set 为 0 或 1,multiset 可以大于 1)

关于 insert:

唯一的一个插入元素的动作.

插入元素时, 返回一个对组. 第一个成员是指向新插入值或已存在的这个值的迭代器, 第二个成员表示插入成功与否(不存在的, 新插入的为真, 已存在的不需新插入为假).

范围插入的时候, 没有返回值.

查找函数

这才是今天的重点.

iterator find(key);  // 查找键 key 是否存在, 若存在, 返回该键的元素的迭代器; 若不存在, 返回 set.end();
size_type count(key); // 查找键 key 的元素个数
iterator lower_bound(keyElem);// 返回第一个 key>=keyElem 元素的迭代器.
iterator upper_bound(keyElem);// 返回第一个 key>keyElem 元素的迭代器.
pair<iterator,iterator> equal_range(keyElem);// 返回容器中 key 与 keyElem 相等的上下限的两个迭代器.

find 函数

find 函数, 实际上是在红黑树中进行二叉搜索, 如果找到了就返回相应位置迭代器, 找不到就返回尾后迭代器 end().

count 函数

根据 set 不能重复的性质, count 非零即一.

lower_bound,upper_bound 和 equal_range 函数

很直接的, lower 就是返回第一个大于等于指定元素的迭代器, 而 upper 就是返回第一个大于指定元素的迭代器. 如下所示:

int main()
{
    set<int> s;
    s.insert(2);
    s.insert(4);
    s.insert(9);
    s.insert(10);
    s.insert(20);
    auto it1 = s.lower_bound(9);
    auto it2 = s.upper_bound(9);
    cout <<"*it1=" << *it1 << "*it2=" << *it2 << endl;
    return 0;
}

我们输出结果为:

*it1=9 *it2=10

由此可以清楚看出这两个函数的作用.

接下来我们介绍 equal_range 函数. equal_range 的作用就是返回查找到的元素的上下限迭代器, 同样遵守左闭右开的原则. 而这正好是我们 lower_bound 和 upper_bound 的返回值. 所以, 我们可以将 equal_range 的返回值看做是返回一个存着 lower_bound 和 upper_bound 的返回值的对组.

我们可以验证:

int main()
{
    //multiset<int> s;
    set<int> s;
    s.insert(2);
    s.insert(4);
    s.insert(9);
    s.insert(9);
    s.insert(9);
    s.insert(10);
    s.insert(20);
    auto it1 = s.lower_bound(9);
    auto it2 = s.upper_bound(9);
    auto pair = s.equal_range(9);
    if (pair.first == it1 && pair.second == it2)
        cout <<"equal_range pair == lower_bound & upper_bound" << endl;
    return 0;
}

最后我们成功输出了

"equal_range pair == lower_bound & upper_bound"

set 的排序规则

set 默认是从小到大排序的, 当我们要从大到小排序或者用自定义数据排序的时候, 我们就要指定排序规则, 同样也是使用仿函数实现:

//functor 为仿函数
set<int,functor> s;
...

自己写一个仿函数即可. 可参照 我不熟悉的 list .

不支持回调函数.

速记: 因为 set 用红黑树实现, 插入即排序, 排序一旦建立不能更改, 所以要在创建 set 的时候就指定排序规则, 而不是插入完了之后再指定.

由于 set 的特殊性, 插入即排序建立. 故有此要求.

来源: https://www.cnblogs.com/love-jelly-pig/p/9995667.html