title: c++ Binary search of a function template specialization
body: <p>I am trying to write a factory with a compile-time class registration. 
  The idea is simple: we get an object by id using a template specialization.
  Here the code:</p>
  
  <pre><code>#include &lt;iostream&gt;
  
  typedef unsigned short IdType;
  #define MAX_ID_TOO_COMPLEX 10000
  #define MAX_ID 100
  #define MIN_ID 1
  
  static_assert(MAX_ID &gt;= MIN_ID, 
      "error: max message id is lesser than min");
  static_assert(std::is_signed&lt;IdType&gt;::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&lt;IdType _Left = MIN_ID, IdType _Right = MAX_ID&gt;
  Base * create(IdType id)
  {
      const IdType _Mid = (_Left + _Right) / 2;
      if (_Mid == id)
          return create&lt;_Mid&gt;();
      if (_Mid &lt; id)
          return create&lt;_Mid + 1, _Right&gt;(id);
      return create&lt;_Left, _Mid - 1&gt;(id);
  }
  template&lt;&gt;
  Base * create&lt;MAX_ID + 1, MAX_ID&gt;(IdType id)
  {
      std::cout &lt;&lt; " too much " &lt;&lt; std::endl;
      return nullptr;
  }
  
  template&lt;&gt;
  Base * create&lt;MIN_ID, MIN_ID - 1&gt;(IdType id)
  {
      std::cout &lt;&lt; " too less " &lt;&lt; std::endl;
      return nullptr;
  }
  
  
  template&lt;IdType _Id&gt;
  Base * create()
  {
      std::cout &lt;&lt;  "no registered class for " &lt;&lt; _Id &lt;&lt; std::endl;
      return nullptr;
  }
  
  
  //registering the Derv class
  template&lt;&gt;
  Base * create&lt;Derv::id&gt;()
  {
      std::cout &lt;&lt; "creating Derv..." &lt;&lt; std::endl;
      return new Derv;
  }
  
  int main()
  {
      for (IdType i = 0; i &lt; MAX_ID + 2;  i++) {
          Base * x = create(i);
          if (x != nullptr) delete x;
      }
      system("pause");
  }
  </code></pre>
  
  <p>I use the binary search instead of iterations to avoid the problem described here:
  <a href="https://stackoverflow.com/questions/21139528/what-does-it-mean-if-visual-studio-2012-throws-a-compile-error-that-shouldnt-ex">What does it mean if Visual studio 2012 throws a compile error that shouldn&#39;t exist for VS2012?</a></p>
  
  <p>This code works as it should, but when the max id is over 10000 I got the next error:</p>
  
  <pre><code>fatal error C1128: number of sections exceeded object file format limit : compile with /bigobj
  </code></pre>
  
  <p>So, it creates a template instantiation for each possible _Left/_Right combination.</p>
  
  <p>I am wondering if there is a way to search without enlarging of the object file?
  Or is there any more elegant way to do the same?</p>
  
  <p><strong>UPD:</strong></p>
  
  <p>Slightly modificated code from @Yakk answer below:</p>
  
  <pre><code>#include &lt;iostream&gt;
  
  typedef unsigned short IdType;
  #define MAX_ID_TOO_COMPLEX 500
  #define MAX_ID 100
  #define MIN_ID 0
  
  static_assert(MAX_ID &gt;= 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&lt;IdType id&gt;
  Base* create() {
      std::cout &lt;&lt; "no registered class for " &lt;&lt; id &lt;&lt; std::endl;
      return nullptr;
  }
  
  //registering the Derv class
  template&lt;&gt;
  Base * create&lt;Derv::id&gt;()
  {
      std::cout &lt;&lt; "creating Derv..." &lt;&lt; std::endl;
      return new Derv;
  }
  
  
  namespace details {
      template&lt;IdType min_id, IdType...ids&gt;
      Base* createById(IdType x, std::integer_sequence&lt;IdType, ids...&gt;) {
          using base_maker = Base*(*)();
          static const base_maker makers[] {
              create&lt;min_id + ids&gt;...
          };
          return makers[x - min_id]();
      }
  }
  
  template&lt;IdType min_id = MIN_ID, IdType max_id=MAX_ID&gt;
  Base* createById(IdType x) {
      if (x &lt; min_id) return nullptr;
      if (x &gt;= max_id) return nullptr;
      return details::createById&lt;min_id&gt;(x, std::make_integer_sequence&lt;IdType, max_id - min_id&gt;{});
  }
  
  
  int main()
  {
      for (IdType i = 0; i &lt; MAX_ID + 2; i++) {
          Base * x = createById(i);
          if (x != nullptr) delete x;
      }
  
      system("pause");
  }
  </code></pre>
  
  <p>Seems much better.</p>