c++11 - 优于 O(n!) 无序元组比较算法

Question

我正在编写一个小型数学库(出于兴趣，没有特定的目标)，但遇到了一些困难。我有一个 Addition看起来像的类:

    template <class ... Functions>
    struct Addition
    {
        std::tuple<Functions...> functions;
        //...
    };

我想实现 operator==对于这个类。只需返回 functions == o.functions不好，因为，例如，实例化 Addition<Sine, Cosine>和 Addition<Cosine, Sine>不会比较平等，但我希望他们能。

当前对我创建的函数施加的限制是:

1. 函数对象必须与任何其他函数对象具有可比性。这是通过添加实现的

   template <class F> bool operator==(F && f) const { return false; }

   每个函数类的定义。

2. 只有属于同一类的两个类才相等。换句话说，两个类必须是同一类才能比较相等。

我现在的解决方案是对两个元组进行有序比较，然后置换其中一个并尝试另一个有序比较并继续置换和比较，直到一个返回 true。此方法的运行时间为 O(n!) 并且需要 O(n!) 次模板实例化。

我想做的是简单地找到比较相等的元素，然后删除它们并继续比较两个子元组。不幸的是，由于比较具有运行时代码(通常)，您无法知道在编译时要删除哪些元素。像这样的任何解决方案都将以 O(n!) 模板实例化结束，这也是不可取的。

那么，有没有一种方法可以实现小于 O(n!) 运行时间的两个元组的无序比较(具有以上两点，但如果不使用它们则可以加分)并且 少于 O(n!) 个模板实例化。

Answer 1

最简单的选择是使用 boost fusion set .

与 std::tuple 相比的另一个优势是您可以获得用于增强融合容器的算法，因此您可以使用 fold检查融合集中的每个函数对象是否包含在其他融合集中:

    template <class ... Functions>
    struct Addition
    {
        boost::fusion::set<Functions...> functions;
        //...


        struct Equal
        {

            typedef boost::fusion::set<Functions...> Functions;
            Functions& functions;

            template<typename T>
            std::enable_if<boost::fusion::has_key<Functions, T>::value, bool> 
            operator()(bool res, T& t) const
            {
                  return res && boost::fusion::at_key<T>(functions) == t;
            }

            template<typename T>
            std::enable_if<!boost::fusion::has_key<Functions, T>::value, bool> 
            operator()(bool res, T& t) const
            {
                return false;
            }

        };

        template <class ... Functions1>
        bool operator==(Addition<Functions1...> that)
        {
            return boost::fusion::fold(true, that.functions, Equal<Functions...>{this.functions});
        };

        ...
    };