c++函数模板特化的二进制搜索

Question

我正在尝试编写一个带有编译时类注册的工厂。这个想法很简单:我们使用模板特化通过 id 获取一个对象。这里的代码:

#include <iostream>

typedef unsigned short IdType;
#define MAX_ID_TOO_COMPLEX 10000
#define MAX_ID 100
#define MIN_ID 1

static_assert(MAX_ID >= MIN_ID, 
    "error: max message id is lesser than min");
static_assert(std::is_signed<IdType>::value || MIN_ID != 0, 
    "error: for unsigned types min must be positive");

class Base
{
public:
    virtual ~Base(){};
};

class Derv : public Base
{
public:
    static const IdType id;
};
const IdType Derv::id = 4;


template<IdType _Left = MIN_ID, IdType _Right = MAX_ID>
Base * create(IdType id)
{
    const IdType _Mid = (_Left + _Right) / 2;
    if (_Mid == id)
        return create<_Mid>();
    if (_Mid < id)
        return create<_Mid + 1, _Right>(id);
    return create<_Left, _Mid - 1>(id);
}
template<>
Base * create<MAX_ID + 1, MAX_ID>(IdType id)
{
    std::cout << " too much " << std::endl;
    return nullptr;
}

template<>
Base * create<MIN_ID, MIN_ID - 1>(IdType id)
{
    std::cout << " too less " << std::endl;
    return nullptr;
}


template<IdType _Id>
Base * create()
{
    std::cout <<  "no registered class for " << _Id << std::endl;
    return nullptr;
}


//registering the Derv class
template<>
Base * create<Derv::id>()
{
    std::cout << "creating Derv..." << std::endl;
    return new Derv;
}

int main()
{
    for (IdType i = 0; i < MAX_ID + 2;  i++) {
        Base * x = create(i);
        if (x != nullptr) delete x;
    }
    system("pause");
}

我使用二进制搜索而不是迭代来避免此处描述的问题: What does it mean if Visual studio 2012 throws a compile error that shouldn't exist for VS2012?

这段代码可以正常工作，但是当最大 id 超过 10000 时，我得到了下一个错误:

fatal error C1128: number of sections exceeded object file format limit : compile with /bigobj

因此，它会为每个可能的 _Left/_Right 组合创建一个模板实例化。

我想知道是否有一种方法可以在不放大目标文件的情况下进行搜索？或者有没有更优雅的方法来做同样的事情？

更新:

下面@Yakk 回答的代码略有修改:

#include <iostream>

typedef unsigned short IdType;
#define MAX_ID_TOO_COMPLEX 500
#define MAX_ID 100
#define MIN_ID 0

static_assert(MAX_ID >= MIN_ID,
    "error: max id is lesser than min");

class Base
{
public:
    virtual ~Base() {};
};

class Derv : public Base
{
public:
    static const IdType id;
};
const IdType Derv::id = 4;

template<IdType id>
Base* create() {
    std::cout << "no registered class for " << id << std::endl;
    return nullptr;
}

//registering the Derv class
template<>
Base * create<Derv::id>()
{
    std::cout << "creating Derv..." << std::endl;
    return new Derv;
}


namespace details {
    template<IdType min_id, IdType...ids>
    Base* createById(IdType x, std::integer_sequence<IdType, ids...>) {
        using base_maker = Base*(*)();
        static const base_maker makers[] {
            create<min_id + ids>...
        };
        return makers[x - min_id]();
    }
}

template<IdType min_id = MIN_ID, IdType max_id=MAX_ID>
Base* createById(IdType x) {
    if (x < min_id) return nullptr;
    if (x >= max_id) return nullptr;
    return details::createById<min_id>(x, std::make_integer_sequence<IdType, max_id - min_id>{});
}


int main()
{
    for (IdType i = 0; i < MAX_ID + 2; i++) {
        Base * x = createById(i);
        if (x != nullptr) delete x;
    }

    system("pause");
}

看起来好多了。

Answer 1

使用跳转表代替二进制搜索。

template<IdType id>
Base* create() {
  return nullptr;
}
namespace details {
  template<IdType min_id, IdType...ids>
  Base* create(IdType x, std::integral_sequence<IdType, ids...>) {
    using base_maker = Base*(*)();
    static constexpr const base_maker makers[] = {
      create<min_id+ids>...
    };
    return makers[x-min_id]();
  }
}
template<IdType min_id, IdType max_id>
Base* create(IdType x) {
  if (x < min_id) return nullptr;
  if (x >= max_id) return nullptr;
  return details::create<min_id>(x, std::make_integral_sequence<IdType, max_id-min_id>{} );
}

这会创建 2 个函数和一个跳转表。然后它通过数学计算找到要调用的函数，然后调用它。

std::make_integral_sequence 等直到 C++14 才可用，但很容易编写一个。栈溢出的实现有很多。