Why is the code in most STL implementations so convoluted?

Question

The STL is a critical piece of the C++ world, most implementations derive from the initial efforts by Stepanov and Musser.

My question is given the criticality of the code, and it being one of the primary sources for people to view examples of well written C++ for both awe and learning purposes: Why are the various implementations of the STL so disgusting to look at - convoluted and generally good examples of how not to write C++ code from an aesthetics point of view.

The code examples below would not pass code-review at the places I've worked at for reasons varying from variable naming, layout, macros and uses of operators that require more than a simple glance to figure out what is actually occurring.

template<class _BidIt> inline
bool _Next_permutation(_BidIt _First, _BidIt _Last)
{  // permute and test for pure ascending, using operator<
_BidIt _Next = _Last;
if (_First == _Last || _First == --_Next)
   return (false);

for (; ; )
   {  // find rightmost element smaller than successor
   _BidIt _Next1 = _Next;
   if (_DEBUG_LT(*--_Next, *_Next1))
      {  // swap with rightmost element that's smaller, flip suffix
      _BidIt _Mid = _Last;
      for (; !_DEBUG_LT(*_Next, *--_Mid); )
         ;
      _STD iter_swap(_Next, _Mid);
      _STD reverse(_Next1, _Last);
      return (true);
      }

   if (_Next == _First)
      {  // pure descending, flip all
      _STD reverse(_First, _Last);
      return (false);
      }
   }
}


_Ty operator()()
   {  // return next value
   static _Ty _Zero = 0;   // to quiet diagnostics
   _Ty _Divisor = (_Ty)_Mx;

   _Prev = _Mx ? ((_Ity)_Ax * _Prev + (_Ty)_Cx) % _Divisor
      : ((_Ity)_Ax * _Prev + (_Ty)_Cx);
   if (_Prev < _Zero)
      _Prev += (_Ty)_Mx;
   return (_Prev);
   }

Please note I'm not critiquing the interface, as it is very well designed and applicable. What I'm concerned about is the readability of the implementation details.

A similar questions have been previously posed:

Is there a readable implementation of the STL

Why STL implementation is so unreadable? How C++ could have been improved here?

Note: The code presented above is taken from MSVC 2010 algorithm and queue headers.

Answer 1

About the variables names, library implementors must use "crazy" naming conventions, such as names starting with an underscore followed by an uppercase letter, because such names are reserved for them. They cannot use "normal" names, because those may have been redefined by a user macro.

Section 17.6.3.3.2 "Global names" §1 states:

Certain sets of names and function signatures are always reserved to the implementation:

• Each name that contains a double underscore or begins with an underscore followed by an uppercase letter is reserved to the implementation for any use.

• Each name that begins with an underscore is reserved to the implementation for use as a name in the global namespace.

(Note that these rules forbid header guards like __MY_FILE_H which I have seen quite often.)