关联容器使用非Key类型查找：is_transparent

使用is_transparent来实现用非Key类型对关联性容器进行查找。

C++ STL提供四种关联性容器(AssociativeContainer - cppreference)：set, multiset, map, multimap。在这些关联性容器中存放自定义类型，需要我们自己定义比较，常用的有以下几种方法

关联容器的默认比较器都是Compare = std::less<T>，而该函数对象类模版默认调用类上的operator<，除非重载。根据这个思路，我们有两种办法：

• 在namespace std中特化相应的std::less<T>类模板，在其中实现operator<(const T& lhs, const T& rhs)。该函数应该有const限定，否则编译器会警告：

  warning: the specified comparator type does not provide a const call operator

• 在该类中实现成员函数的operator<(const T& rhs)，但是一定要注意该成员函数必须有const限定符。因为关联容器的Key类型都带有const修饰，如果该成员函数没有const修饰，则无法被const T类型的对象调用。

特化struct less<T>类模版：

struct Timer;
using TimerPtr = std::unique_ptr<Timer>;

struct Timer
{
  uint64_t expiration_;
  uint64_t interval_;
};

namespace std
{
template<> struct less<TimerPtr>
{
  bool operator()(const TimerPtr& lhs, const TimerPtr& rhs) const
  {
    return lhs->expiration_ < rhs->expiration_;
  }
};
}

int main() {
  auto set = std::set<TimerPtr>{};
}

实现const修饰的成员函数operator<：

struct Timer
{
  uint64_t expiration_;
  uint64_t interval_;

  bool operator<(const Timer& rhs) const
  {
    return expiration_ < rhs.expiration_;
  }
};

int main() {
auto set = std::set<Timer>{};
}

第二种思路是我们自己传入模版参数Compare，因此我们需要创建函数对象，并重载他的operator()

• 定义一个Compare类，在该类中实现operator()(const T& lhs, const T& rhs)，如果operator()没有const限定符会收到编译器警告。
• 定义一个generic lambda表达式[](const auto& lhs, const auto& rhs){}。因为只有编译器才知道该lambda表达式的类型，因此我们使用decltype(cmp)将定义好的lambda表达式的类型传给容器。同时该lambda表达式也必须直接传给该容器的构造函数，因为该容器不能帮你构造出该匿名函数对象。默认情况下，由lambda表达式产生的闭包（closure）对象中的operator()是也是有const限定符的，除非该lambda被mutable修饰。

定义一个Compare类：

struct Timer
{
  uint64_t expiration_;
  uint64_t interval_;
};

struct TimerCompare
{
  bool operator()(const Timer& lhs, const Timer& rhs) const
  {
    return lhs.expiration_ < rhs.expiration_;
  }
};

int main() {
auto set = std::set<Timer, TimerCompare>{};
}

定义一个generic lambda

struct Timer
{
  uint64_t expiration_;
  uint64_t interval_;
};

int main() {
auto cmp = [](auto lhs, auto rhs){return lhs.expiration_ < rhs.expiration_;};
auto set = std::set<Timer, decltype(cmp)>{cmp};
}

---

使用is_transparent来实现用非Key类型对关联性容器进行查找。关联性容器都会提供下面这一组成员函数：lower_bound, equal_range, upper_bound。这一组函数接受一个const Key&类型的参数，用容器内的比较器进行查找。

struct Timer
{
  uint64_t expiration_;
  uint64_t interval_;
};

struct TimerCompare
{
  bool operator()(const Timer& lhs, const Timer& rhs) const
  {
    return lhs.expiration_ < rhs.expiration_;
  }
};

int main() {
auto set = std::set<Timer, TimerCompare>{};
set.insert(Timer{2, 0});
set.insert(Timer{1, 0});
set.insert(Timer{4, 0});
}

---

在C++14之前，如果我们想要查找这个set当中所有expiration_时间小于当前时间的Timer，我们就必须构造一个临时对象Timer，给他填上expiration_，然后传入lower_bound进行查找。如果临时对象构造的代价太大，或者构造临时对象有副作用，都对我们的查找造成很多不便。C++14当中，引入了一个标签is_tranparent。如果我们在我们的比较器中定义该标签，并保证该类型和Key之间的比较是畅通的，我们就可以用非Key类型进行比较：

struct Timer
{
  uint64_t expiration_;
  uint64_t interval_;
};

struct TimerCompare
{
  using is_transparent = void;

  bool operator()(const Timer& lhs, const Timer& rhs) const
  {
    return lhs.expiration_ < rhs.expiration_;
  }

  bool operator()(uint64_t  lhs, const Timer& rhs) const
  {
    return lhs < rhs.expiration_;
  }

  bool operator()(const Timer& lhs, uint64_t rhs) const
  {
    return lhs.expiration_ < rhs;
  }

  // bool operator(int lhs, int rhs) const 
};

int main() {
  auto set = std::set<Timer, TimerCompare>{};
  set.insert(Timer{2, 0});
  set.insert(Timer{1, 0});
  set.insert(Timer{4, 0});
  set.lower_bound(0);
}

---

C++14的标准库中还帮我们写了一个标准的，使用完美转发的is_transparent比较器std::less<void>。

template <class T = void> struct less {
    constexpr bool operator()(const T& x, const T& y) const;
    typedef T first_argument_type;
    typedef T second_argument_type;
    typedef bool result_type;
};

template <> struct less<void> {
    template <class T, class U> auto operator()(T&& t, U&& u) const
    -> decltype(std::forward<T>(t) < std::forward<U>(u));
    typedef *unspecified* is_transparent;
};

只要自己定义了operator<，并且两个类型之间定义过operator<，就可以直接使用这个std::less<void>，示例如下：

#include <iostream>
#include <set>
#include <iterator>

struct Timer
{
  uint64_t expiration_;
  uint64_t interval_;
};

inline bool operator<(const uint64_t& lhs, const Timer& rhs)
{
  return lhs < rhs.expiration_;
}

inline bool operator<(const Timer& lhs, const Timer& rhs)
{
  return lhs.expiration_ < rhs.expiration_;
}

inline bool operator<(const Timer& lhs, const uint64_t& rhs)
{
  return lhs.expiration_ < rhs;
}

int main() {
  auto set = std::set<Timer, std::less<>>{Timer{3, 0}, Timer{1,0}, Timer{2, 0}};
  for(const auto& x : set) std::cout<<x.expiration_<<' ';
}

---

参考

What are transparent comparators - stackoverflow
How do I use comparator with is_transparent type? - stackoverflow
一个Projection Less的实现
is_transparent: How to search a C++ set with another type than its key - fluentcpp.com
Transparent comparator code minimization - stackoverflow