C++中的比较技巧

Question

一类:

class foo{
public:
    int data;
};

现在我想在这个类中添加一个方法,进行一些比较,看看它的数据是否等于给定数字之一.

当然,我可以写if(data==num1|| data == num2|| data ==num3.....),但老实说,data ==每当我把它与数字进行比较时,我都会感到恶心.

所以,我希望我能写出这样的东西:

if(data is equal to one of these(num1,num2,num3,num4,num5...))
    return true;
else
    return false;

我想实现这个声明, data is equal to one of these(num1, num2, num3, num4, num5...)

这是我的方法:

#include <stdarg.h>
bool is_equal_to_one_of_these(int count,...){
    int i;
    bool equal = false;
    va_list arg_ptr;
    va_start(arg_prt,count);
    for(int x=0;x<count;x++){
        i = va_arg(arg_ptr,int);
        if( i == data ){
            equal = true;
            break;
        }
    }
    va_end(arg_ptr);
    return equal;
}

这段代码将为我完成这项工作.但每次我使用这种方法时,我都要计算参数并将其传入.

有没有人有更好的主意？

Answer 1

简单的方法

最简单的方法是编写一个成员函数封装称为in()周围std::find有一对迭代寻找有问题的数据.我为此写了一个简单的template<class It> in(It first, It last)成员函数

template<class It>
bool in(It first, It last) const
{
    return std::find(first, last, data) != last;
}

如果您无法访问源代码foo,您可以编写签名template<class T> bool in(foo const&, std::initializer_list<T>)等非成员函数,并将其称为

in(f, {1, 2, 3 });

艰难的方式

但是,让我们完全放弃:只需添加两个public重载:

• 一个std::initializer_list参数使用相应的初始化列表参数的begin()和end()迭代器调用前一个参数.
• 一个用于任意容器作为输入,它将执行一个小标签调度到辅助程序的另外两个private重载detail_in():
  • 一个过载做SFINAE特技尾随返回类型decltype(c.find(data), bool())将从过载集中删除,如果容器c中的问题并没有一个成员函数find(),并返回bool,否则(这是由滥用实现逗号操作里面decltype)
  • 一个后备重载只是简单地采用begin()和end()迭代器和代表原来的in()以两个迭代器

因为对于标签detail_in()帮助形成一个继承层次结构(类似于标准的迭代器标签),第一过载将匹配的关联容器std::set,并std::unordered_set和他们多表兄弟.所有其他容器(包括C阵列std::array)std::vector和std::list将匹配第二个重载.

#include <algorithm>
#include <array>
#include <initializer_list>
#include <type_traits>
#include <iostream>
#include <set>
#include <unordered_set>
#include <vector>

class foo
{
public:
    int data;

    template<class It>
    bool in(It first, It last) const
    {
        std::cout << "iterator overload: ";
        return std::find(first, last, data) != last;
    }

    template<class T>
    bool in(std::initializer_list<T> il) const
    {
        std::cout << "initializer_list overload: ";
        return in(begin(il), end(il));
    }

    template<class Container>
    bool in(Container const& c) const 
    {
        std::cout << "container overload: ";
        return detail_in(c, associative_container_tag{});    
    }

private:
    struct sequence_container_tag {};
    struct associative_container_tag: sequence_container_tag {};

    template<class AssociativeContainer>
    auto detail_in(AssociativeContainer const& c, associative_container_tag) const 
    -> decltype(c.find(data), bool())
    {
        std::cout << "associative overload: ";
        return c.find(data) != end(c);    
    }

    template<class SequenceContainer> 
    bool detail_in(SequenceContainer const& c, sequence_container_tag) const
    {
        std::cout << "sequence overload: ";
        using std::begin; using std::end;
        return in(begin(c), end(c));    
    }
};

int main()
{
    foo f{1};
    int a1[] = { 1, 2, 3};
    int a2[] = { 2, 3, 4};

    std::cout << f.in({1, 2, 3}) << "\n";
    std::cout << f.in({2, 3, 4}) << "\n";

    std::cout << f.in(std::begin(a1), std::end(a1)) << "\n";
    std::cout << f.in(std::begin(a2), std::end(a2)) << "\n";

    std::cout << f.in(a1) << "\n";
    std::cout << f.in(a2) << "\n";

    std::cout << f.in(std::array<int, 3>{ 1, 2, 3 }) << "\n";
    std::cout << f.in(std::array<int, 3>{ 2, 3, 4 }) << "\n";

    std::cout << f.in(std::vector<int>{ 1, 2, 3 }) << "\n";
    std::cout << f.in(std::vector<int>{ 2, 3, 4 }) << "\n";

    std::cout << f.in(std::set<int>{ 1, 2, 3 }) << "\n";
    std::cout << f.in(std::set<int>{ 2, 3, 4 }) << "\n";

    std::cout << f.in(std::unordered_set<int>{ 1, 2, 3 }) << "\n";
    std::cout << f.in(std::unordered_set<int>{ 2, 3, 4 }) << "\n";    
}

实例 -对于所有可能的容器 - 为两个数字集打印1和0.

std::initializer_list重载的用例是针对您在调用代码中明确写出的小数字集的成员运行测试.它有复杂性但避免任何堆分配.O(N)

对于像大型集合的成员资格测试这样的任何重要任务,您可以将数字存储在关联容器中,例如std::set,或者它multi_set或unordered_set堂兄弟.这将在存储这些数字时进入堆,但具有O(log N)甚至O(1)查找复杂性.

但是如果你碰巧只有一个数字序列容器,你也可以把它扔到课堂上,它会很快为你计算会员资格O(N).

Answer 2

使用STL有很多方法可以做到这一点.

如果您有非常多的项目,并且您想测试您的给定项目是否是此集合的成员,请使用set或unordered_set.它们允许您分别检查成员资格log n和恒定时间.

如果将元素保存在已排序的数组中,那么binary_search还将log n及时测试成员资格.

对于小型阵列,线性search可能会明显更快地形成(因为没有分支).线性搜索甚至可以在二进制搜索"跳转"所花费的时间内进行3-8次比较.这篇博客文章建议在近64个项目上有一个收支平衡点,低于该点,线性搜索可能会更快,但这显然取决于STL实现,编译器优化和架构的分支预测.

Answer 3

如果data真的是一个整数或枚举类型,你可以使用switch:

switch (data) {
  case 1:
  case 2:
  case 2000:
  case 6000:
  case /* whatever other values you want */:
    act_on_the_group();
    break;
  default:
    act_on_not_the_group();
    break;
}

Answer 4

使用的答案std::initializer_list很好,但我想添加一个可能的解决方案,这正是您在类型安全和现代方式中尝试使用C变量的方法:使用C++ 11可变参数模板:

template<typename... NUMBERS>
bool any_equal( const foo& f , NUMBERS&&... numbers )
{
    auto unpacked = { numbers... };

    return std::find( std::begin( unpacked ) , std::end( unpacked ) , f.data ) 
           != std::end( unpacked );
};

当然,这只有在传递的所有值都属于同一类型时才有效.如果不是,unpacked则无法推断或初始化初始化列表.

然后:

bool equals = any_equal( f , 1,2,3,4,5 );

编辑:这是一个are_same元函数,以确保传递的所有数字是相同的类型:

template<typename HEAD , typename... TAIL>
struct are_same : public and_op<std::is_same<HEAD,TAIL>::value...>
{};

在哪里and_op执行n-ary逻辑和:

template<bool HEAD , bool... TAIL>
struct and_op : public std::integral_constant<bool,HEAD && and_op<TAIL...>::value>
{};

template<>
struct and_op<> : public std::true_type
{};

这样就可以以一种简单的方式强制使用相同类型的数字:

template<typename... NUMBERS>
bool any_equal( const foo& f , NUMBERS&&... numbers )
{
    static_assert( all_same<NUMBERS...>::value , 
                   "ERROR: You should use numbers of the same type" );


    auto unpacked = { numbers... };

    return std::find( std::begin( unpacked ) , std::end( unpacked ) , f.data ) 
           != std::end( unpacked );
};

Answer 5

任何优化都将取决于要比较的数字集的属性.

如果有一个明确的上限,你可以使用a std::bitset.测试成员资格(即索引到bitset,其行为类似于数组)是O(1),实际上是一些快速指令.这通常是达到数百个限制的最佳解决方案,尽管取决于应用,数百万可能是实用的.