C++14的异构比较

03 Oct 2021 | C/CPP, STL | | ˚C

在”IRResolver(STL set重叠区间以及异构查询)“里面,提到过std::set在c++14后可以进行异构查询。这部分其实可以展开讲讲,不仅限于上述文章的用法,也不仅限于std::set。不过我们还是以std::set为例,毕竟这个最典型也最常用。

数据库表中,有所谓的主键概念,任意两个记录的主键值不重复,因此我们通过查询主键就能找到唯一的一条记录。

在一些编程场景中,我们也有类似的需求。比如,一个小组有若干成员:

struct Member {
    uint32_t id;
    std::string name;
    uint32_t mutable age; //为了在后面的集合中能够修改age字段,所以加mutable
    //...
};

由于名字等其他字段都有可能重复,所以用工号id来惟一标识一个员工。我们用一个set来表示一个小组:

struct MemberCmp {
    bool operator() (const Member& l, const Member& r) const
    {
        return l.id < r.id;
    }
};

using Team = std::set<Member, MemberCmp>;

今天是8月17号, 工号1926的童鞋生日了,年龄要增加一岁,我们自然希望这么写:


void age_inc(Team& t, uint32_t id)
{
    auto it = t.find(id);
    if (it != t.end()) {
        it->age++;
    }
}

在c++14以前, 这么写是编译不过的。因为c++14之前, std::set::find是个普通的成员函数。它只接收当前模板类的Key类型作为参数。如果要实现这个功能,必须写成如下形式:

void age_inc(Team& t, uint32_t id)
{
    Member dummy;
    dummy.id = id;
    auto it = t.find(dummy);
    //...
}

且不说, 现实中Member可能是个比较复杂的结构,这样会导致一些性能问题,单纯从观感上来说,这么写绝对谈不上优雅。

好在C++14之后,std::set::find增加了两个成员函数模板:

template< class K > iterator find( const K& x );
template< class K > const_iterator find( const K& x ) const;

这样,find可以接收任意参数,只要该参数能与存储的Key类型通过比较器比较大小。容易想到,可以把MemberCmp改写成如下:

struct MemberCmp {
    bool operator() (const Member& l, const Member& r) const
    {
        return l.id < r.id;
    }
    bool operator() (uintt32_t id, const Member& r) const
    {
        return id < r.id;
    }
    bool operator() (const Member& l, uint32_t id) const
    {
        return l.id < id;
    }
};

然而这样还是存在编译错误。因为C++14在这两个新函数里多了一条规定:只有当比较器中存在Compare::is_transparent类型定义时,这俩重载的模板函数才成立。至于为什么搞这么个规定,可以以看下这里: https://stackoverflow.com/questions/20317413/what-are-transparent-comparators

MemberCmp中添加该类型定义,最终达成了我们期望的效果,见: https://godbolt.org/z/dzo43Yhqa

在”IRResolver(STL set重叠区间以及异构查询)” 中的用法,是std::less<>void特化版本:https://zh.cppreference.com/w/cpp/utility/functional/less_void 原理是一样的。


Older · View Archive (20)

字典树的几种实现方式以及应用