title: C++11 using std::equal_range with custom comparison function
body: <p>Consider this example</p>
  
  <p>(<em>Note that this is just something I made up to illustrate the problem. I am well aware there are more efficient ways to parse an arithmetic expression and though the subject is fascinating, this has nothing to do with my actual question. It's just a semi-realistic example, if I might say so.</em><br>
  <em>I agree the parser thing might make the question seem more complicated, but I could not think of a more abstract example</em>).</p>
  
  <p>Assume you want to do a simple expression parser. You will get bits of strings from a tokenizer, some of them being possibly ambiguous.</p>
  
  <p>For instance, the string "-" could represent an unary minus or a binary minus.</p>
  
  <p>Assume you want to get all possible meanings for string "-".</p>
  
  <p>You could do as follows:</p>
  
  <p>1) define a sorted array describing all possible operators</p>
  
  <pre><code>// types of operators
  enum class opType: char { unary, lasso, rasso, none };
  
  // operator descriptors
  struct opDesc {
      string symbol;
      opType type;
      char   priority;
  
      // partial order comparison
      bool operator&lt; (const opDesc&amp; a) const
      {
          // unary operators first
          if (symbol == a.symbol) return type &lt; a.type;
          return symbol &lt; a.symbol;
      }
  
      // comparison with strings
      static bool comp_desc_str (const opDesc&amp; a, const string&amp; s)
      {
          return a.symbol &lt; s;
      }
      static bool comp_str_desc (const string&amp; s, const opDesc&amp; a)
      {
          return s &lt; a.symbol;
      }
  };
  
  static opDesc op_descriptors[] = {
      { "+" , opType::unary, 8 }, // unary +
      { "-" , opType::unary, 8 }, // unary -
      { "*" , opType::lasso, 6 }, // multiplication
      { "/" , opType::lasso, 6 }, // division
      { "+" , opType::lasso, 5 }, // addition
      { "-" , opType::lasso, 5 }, // substraction
  };
  </code></pre>
  
  <p>2) use <code>std::equal_range</code> to get all possible matches for a given string</p>
  
  <pre><code>// sort descriptors by value and type
  sort(begin(op_descriptors), end(op_descriptors));
  
  // do some searches
  string patterns[] = { "+", "-", "&gt;&gt;", "**" };
  
  for (string s : patterns)
  {
      pair&lt;opDesc*, opDesc*&gt; ops;
  
      ops = equal_range(
          std::begin(op_descriptors), 
          std::end  (op_descriptors), 
          s,
          opDesc::comp_desc_str);
  
      cout &lt;&lt; s &lt;&lt;": "&lt;&lt; ops.first[0] &lt;&lt; ops.second[-1] &lt;&lt; endl;
  }
  </code></pre>
  
  <p>This code won't compile, complaining about <code>opDesc::comp_desc_str</code> (it expects parameters the other way around, i.e. <code>string</code> first, <code>opDesc</code> next).</p>
  
  <p>If I try to replace the function with a version that takes its arguments in reverse order:</p>
  
  <pre><code>ops = equal_range(
      std::begin(op_descriptors), 
      std::end  (op_descriptors), 
      s,
      opDesc::comp_str_desc);
  </code></pre>
  
  <p>it won't compile either, complaining about parameters being yet again in the wrong order (at some other point of the algorithm).</p>
  
  <p>This code, however, will work (<a href="http://ideone.com/CPUAfW" rel="nofollow">see a live version here</a>)</p>
  
  <pre><code>#include &lt;regex&gt;
  #include &lt;iostream&gt;
  
  using namespace std;
  
  // types of operators
  enum class opType: char { unary, lasso, rasso, none };
  
  // operator descriptors
  struct opDesc {
      string symbol;
      opType type;
      char   priority;
  
      // partial order comparison
      bool operator&lt; (const opDesc&amp; a) const
      {
          // unary operators first
          if (symbol == a.symbol) return type &lt; a.type;
          return symbol &lt; a.symbol;
      }
  
      // comparison with strings
      static bool comp_desc_str (const opDesc&amp; a, const string&amp; s)
      {
          return a.symbol &lt; s;
      }
      static bool comp_str_desc (const string&amp; s, const opDesc&amp; a)
      {
          return s &lt; a.symbol;
      }
  
      // display
      friend ostream&amp; operator&lt;&lt;(ostream&amp; os, const opDesc&amp; op);
  };
  
  ostream&amp; operator&lt;&lt;(ostream&amp; os, const opDesc&amp; op)
  {
      os &lt;&lt; op.symbol &lt;&lt; "[" &lt;&lt; (int)op.type &lt;&lt; ":" &lt;&lt; (int)op.priority &lt;&lt; "]";
      return os;
  }
  
  static opDesc op_descriptors[] = {
      { "+" , opType::unary, 8 }, // unary +
      { "-" , opType::unary, 8 }, // unary -
      { "~" , opType::unary, 8 }, // bitwise not
      { "**", opType::rasso, 7 }, // power
      { "*" , opType::lasso, 6 }, // multiplication
      { "/" , opType::lasso, 6 }, // division
      { "%" , opType::lasso, 6 }, // remainder
      { "+" , opType::lasso, 5 }, // addition
      { "-" , opType::lasso, 5 }, // substraction
      { "&lt;&lt;", opType::lasso, 4 }, // left shift
      { "&gt;&gt;", opType::lasso, 4 }, // right shift
      { "&amp;" , opType::lasso, 3 }, // bitwise and
      { "^" , opType::lasso, 2 }, // bitwise xor
      { "|" , opType::lasso, 1 }, // bitwise or 
      { "(" , opType::none , 0 }, // braces
      { ")" , opType::none , 0 }
  };
  
  int main(void)
  {
      // sort descriptors by value and type
      sort(begin(op_descriptors), end(op_descriptors));
  
      // do some searches
      string patterns[] = { "+", "-", "&gt;&gt;", "**" };
  
      for (string s : patterns)
      {
          pair&lt;opDesc*, opDesc*&gt; ops;
          // this won't work
          /*
          ops = equal_range(
              std::begin(op_descriptors), 
              std::end  (op_descriptors), 
              s,
              opDesc::comp_desc_str or opDesc::comp_str_desc);
          */
          // this works
          ops.first = lower_bound(
              std::begin(op_descriptors), 
              std::end  (op_descriptors), 
              s, opDesc::comp_desc_str);
          ops.second = upper_bound(
              std::begin(op_descriptors), 
              std::end  (op_descriptors), 
              s, opDesc::comp_str_desc);
          cout &lt;&lt; s &lt;&lt;": "&lt;&lt; ops.first[0] &lt;&lt; ops.second[-1] &lt;&lt; endl;
      }
  }
  </code></pre>
  
  <p>output:</p>
  
  <pre><code>+: +[0:8]+[1:5]     // unary and binary "-" operators found
  -: -[0:8]-[1:5]     // same thing for "+"
  &gt;&gt;: &gt;&gt;[1:4]&gt;&gt;[1:4]  // first == second when there is only
  **: **[2:7]**[2:7]  // one version of the operator
  </code></pre>
  
  <p><strong>I tried this code on VisualC++ 2013 and g++ with the same results</strong><br>
  (only the obfuscation of the template error messages vary).</p>
  
  <h3>Questions</h3>
  
  <ul>
  <li>is there a particular reason why <code>lower_bound</code> and <code>upper_bound</code> should require two different custom comparison functions?</li>
  <li>is there a workaround for MSVC throwing a bogus error in debug build when using functors to work around the problem?</li>
  <li>is there a definite workaround for this problem (i.e. using <code>equal_range</code> as intended instead of doing the job twice <strong>and</strong> make it compile in debug mode on Visual C++ 2013)?</li>
  </ul>