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?

此代碼的工作，因爲它應該，但當最大編號爲10000我下一個錯誤：

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

因此，它爲每個可能的_Left/_Right組合創建一個模板實例化。

我想知道是否有一種方法來搜索沒有擴大的對象文件？ 或者有沒有更好的方法來做同樣的事情？

UPD：

略改性殼聚糖從@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纔可用，但寫起來很簡單。堆棧溢出有許多實現。