C++ 查找包含类型

Question

动机

在某种程度上，其动机是模仿 C++ 中的数学概念，主要是为了允许编写极其通用的算法。稍后会详细介绍动机。

首先，一些定义。

定义

1. A 型 A包含另一种类型 B如果B可转换为 A至少几乎没有信息丢失*。这类似于超集的数学概念 B ⊆ A .
2. A 型 C在 operatorX 下关闭如果C包括 C X C .
3. 闭包C类型 A在 operatorX 下是包含 A 的类型并在 operatorX 下关闭本身。 C可能不是唯一的。 C可能不存在。
4. 闭包C类型 A和 B在 operatorX 下和 operatorY是同时包含 A 的类型和 B并在 operatorX 下关闭和 operatorY本身。这需要 A X B , B Y A等等。

*注意:这是一个相当不精确的陈述，但如果没有很多繁琐的限制，很难给出一个严格的定义。正如示例:int包括 char , double包括 float , double包括 int32_t因为它有 52 位精度，但是 float不包含 int32_t因为它只有 23 位精度。

问题

给定两种类型 T和 U , 都有 operator+和 operator*定义。找到闭包或在找不到闭包时发出错误的有效方法是什么？

请注意，他们的运营商应该被认为是绝对疯狂的，即T甚至可能不会在 operator+ 下关闭, Σ(k ∈ [0, n)) T可能是依赖于 n 的类型.

例如，如果我们只想要operator+下的闭包

closure<unsigned, unsigned char>::type  //unsigned

可以很容易地实现为

template<typename T, typename U> struct closure {
    using type = decltype(std::declval<T>() + std::declval<U>());
};

但这并不适用于所有类型，因为如前所述，decltype(std::declval<T>() + std::declval<U>())可能不会关闭。

更多关于动机

假设某种通用算法需要操纵多种不同类型。如果我们想创建一个变量来存储中间值，它的类型应该是它们的闭包。

最简单的例子是添加 int至 float , 使用 double作为中间存储。但是在这种情况下，语言实际上指定了 float是int的关闭和 float这在某些情况下是次优的。

现在，由于该算法是通用的，我们需要某种方法来找到闭包，而无需事先知道这些类型及其运算符是什么。

我可能有点忘乎所以，实际上创造了一些愚蠢的设计。

标题说明

我不能称它为“查找类型的闭包”，闭包在编程中通常意味着其他东西 :P 。如果有人建议更好的名称，我会很乐意更改。

Answer 1

要准确估计闭包所需的表示大小，您必须至少跟踪您的操作可能需要的有效数字。下面仅给出整数类型的示例，并且仅涵盖加法。减法和乘法应该很容易做；在那之后，它会变得比现在更困惑。 :)

#include <iostream>
#include <limits>
#include <typeinfo>

namespace closure {

// A subset of numeric_limits provides, just to shorten stuff.  Tells us all we
// want to know about the properties of a particular integer representation.
template <typename T>
struct repr
{
  static constexpr bool is_signed = std::numeric_limits<T>::is_signed;
  static constexpr int digits = std::numeric_limits<T>::digits;
};

// An estimate of the range of the sum of two integers
template <typename R1, typename R2>
struct add
{
  static constexpr bool is_signed = R1::is_signed | R2::is_signed;
  // Can use std::max() when on C++14 or newer
  static constexpr int digits = ((R1::digits > R2::digits) ? R1::digits : R2::digits) + 1;
};

// Now the mess: map the required number of significant digits back to existing
// types.  Note that the edge case for two's complement is overestimated to
// preserve my personal sanity: e.g., a char covers -128..+127, but we will
// place -128 into an int16_t.
template <int digits, bool is_signed>
struct result_impl;

// Define unsigned types in terms of signed ones
template <int digits> struct result_impl<digits, false>
{
  using type = typename std::make_unsigned<typename result_impl<digits-1, true>::type>::type;
};
template <> struct result_impl<0, false> { using type = uint8_t; };

// Construct the correct type based on the number of needed significant bits.
// binary log
constexpr int log2(int x)
{
  return (x > 1) ? (log2(x>>1)+1) : 0;
}

// The required type based on the binary logarithm of the number of significant bits
template <int logdigits>
struct logtype;

template <> struct logtype<0> { using type = int8_t;  };
template <> struct logtype<1> { using type = int8_t;  };
template <> struct logtype<2> { using type = int8_t;  };
template <> struct logtype<3> { using type = int16_t; };
template <> struct logtype<4> { using type = int32_t; };
template <> struct logtype<5> { using type = int64_t; };

// And this is the actual type for signed integers with a certain minimum number of bits
template <int digits> struct result_impl<digits, true>
{
  using type = typename logtype<log2(digits)>::type;
};

// Finally, our result type using the representation types from above.
template <typename R>
struct result { using type = typename result_impl<R::digits, R::is_signed>::type; };

}

int main()
{
  using namespace closure;

  // Adding two 16-bit values should require a 32-bit type
  std::cout << typeid(result<add<repr<uint16_t>,
                                 repr<uint16_t>>>::type).name() << std::endl;

  // Adding three 16-bit values should still require a 32-bit type
  std::cout << typeid(result<add<add<repr<uint16_t>,
                                     repr<uint16_t>>,
                                 repr<uint16_t>>>::type).name() << std::endl;

  // Adding two 16-bit values, one signed, should require a signed 32-bit type
  std::cout << typeid(result<add<repr<uint16_t>,
                                 repr<int16_t>>>::type).name() << std::endl;

  // Adding a signed 16-bit and an unsigned 32-bit value, should require a signed 64-bit type
  std::cout << typeid(result<add<repr<uint32_t>,
                                 repr<int16_t>>>::type).name() << std::endl;
}

(编辑:感谢@PasserBy，简化了有效二进制数字的数量和所选整数大小之间的关系。)

通过 c++filt -t 编译和运行结果应该给你类似的东西

unsigned int
unsigned int
int
long

作为输出。它并不多，但也许它是您正在寻找的东西的起点。当谈到浮点表示时，我担心它会变得更加可怕。