c++ - Why use std::less as the default functor to compare keys in std::map and std::set? -

i wondering why std::map , std::set use std::less default functor compare keys. why not use functor works similar strcmp? like:

  template <typename t> struct compare   {      // return less 0 if lhs < rhs      // return 0 if lhs == rhs      // return greater 0 if lhs > rhs      int operator()(t const& lhs, t const& rhs)      {         return (lhs-rhs);      }   } 

say map has 2 object in it, keys key1 , key2. want insert object key key3.

when using std::less, insert function needs first call std::less::operator() key1 , key3. assume std::less::operator()(key1, key3) returns false. has call std::less::operator() again keys switched, std::less::operator()(key3, key1), decide whether key1 equal key3 or key3 greater key1. there 2 calls std::less::operator() make decision if first call returns false.

had std::map::insert used compare, there sufficient information make right decision using 1 call.

depending on type of key in map, std::less::operator()(key1, key2) expensive.

unless missing basic, shouldn't std::map , std::set use compare instead of std::less default functor compare keys?

i decided ask alexander stepanov (designer of stl) this. i'm allowed quote him follows:

originally, proposed 3-way comparisons. standard committee asked me change standard comparison operators. did told. have been advocating adding 3-way components standard on 20 years.

but note perhaps unintuitively, 2-way not huge overhead. you don't have make twice many comparisons. it's 1 comparison per node on way down (no equality check). cost not being able return (when key in non-leaf) , 1 comparison @ end (swapping arguments check equality). if i'm not mistaken, makes

1 + 1/2*1 + 1/4*2 + 1/8*3 + ... = 1 + 1/2+1/4+1/8+... + 1/4+1/8+... + ... -> 3  (depth -> infty) 

extra comparisons on average on balanced tree contains queried element.

on other hand, 3-way comparison doesn't have terrible overhead: branchless 3-way integer comparison. whether branch check comparison result against 0 (equality) @ each node less overhead paying ~3 comparisons @ end question. doesn't matter much. think comparison should have been 3-valued, decision whether use 3 outcomes changed.

update: see comments below why think 3-way comparison better in trees, not in flat arrays.