Is There a Readable Implementation of the Stl

Is there a readable implementation of the STL?

There is a book The C++ Standard Template Library, co-authored by the original STL designers Stepanov & Lee (together with P.J. Plauger and David Musser), which describes a possible implementation, complete with code - see http://www.amazon.co.uk/C-Standard-Template-Library/dp/0134376331.

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

Implementations use names starting with an underscore followed by an uppercase letter or two underscores to avoid conflicts with user-defined macros. Such names are reserved in C++.
For example, one could define a macro called Type and then #include <vector>. If vector implementations used Type as a template parameter name, it would break.
However, one is not allowed to define macros called _Type (or __type, type__ etc.). Therefore, vector can safely use such names.

How can I find implementations of the C++ Standard Library?

The two most popular open source implementations of standard C++ library are:

libstdc++, part of gcc project
libc++, part of LLVM project

Both websites contain links to git/svn repositories with source code.

Was the Visual C++ STL human-generated or code-generated?

Two things:

The indentation is actually fine, although nowadays unusual (and I personally hate it): they use an indentation of four, which is achieved via spaces, but use tabs for all multiples of eight. This used to be the standard almost everywhere (notably it’s still the default setting in several editors such as Vim). But as a consequence, the code is only indented correctly if you set your tab width to 8. So the code actually looks like this:
```
else if (_Where == end())
    {   // insert at end if after last element
        if (_DEBUG_LT_PRED(this->comp,
            _Key(_Rmost()), this->_Kfn(_Val)))
            return (_Insert(false, _Rmost(), _Val));
    }
```
Which, though still unusual, is perfectly logical and legible.
It’s good style (or even mandated?) that the standard library uses only reserved identifiers to avoid name clashes with customers’ C++ code. These reserved names are either names starting with an underscore followed by a capital letter (_DEBUG_LT_PRED, _Key), or two underscores (not in this code, but the GCC libstdc++ is littered with __x etc.).

Hence the alphabet soup.

But yes, this code is indeed manually written – at least it is in the case of the GCC. The active source branch of the libstdc++ looks exactly like the code above, and isn’t auto-generated.

Readable alternative to std::set::find

If your concern is primarily terseness, then I'd suggest:

if (s.count(val)) {
  // count == 1 == true, element exists
} else {
  // count == 0 == false, element does not exist
}

But personally I still prefer checking find against end since the intent is more explicit. It's worth a bit of extra typing to me.

How to implement an STL-style iterator and avoid common pitfalls?

https://cplusplus.com/reference/iterator/ has a handy chart that details the specs of § 24.2.2 of the C++11 standard. Basically, the iterators have tags that describe the valid operations, and the tags have a hierarchy. Below is purely symbolic, these classes don't actually exist as such.

iterator {
    iterator(const iterator&);
    ~iterator();
    iterator& operator=(const iterator&);
    iterator& operator++(); //prefix increment
    reference operator*() const;
    friend void swap(iterator& lhs, iterator& rhs); //C++11 I think
};

input_iterator : public virtual iterator {
    iterator operator++(int); //postfix increment
    value_type operator*() const;
    pointer operator->() const;
    friend bool operator==(const iterator&, const iterator&);
    friend bool operator!=(const iterator&, const iterator&); 
};
//once an input iterator has been dereferenced, it is 
//undefined to dereference one before that.

output_iterator : public virtual iterator {
    reference operator*() const;
    iterator operator++(int); //postfix increment
};
//dereferences may only be on the left side of an assignment
//once an output iterator has been dereferenced, it is 
//undefined to dereference one before that.

forward_iterator : input_iterator, output_iterator {
    forward_iterator();
};
//multiple passes allowed

bidirectional_iterator : forward_iterator {
    iterator& operator--(); //prefix decrement
    iterator operator--(int); //postfix decrement
};

random_access_iterator : bidirectional_iterator {
    friend bool operator<(const iterator&, const iterator&);
    friend bool operator>(const iterator&, const iterator&);
    friend bool operator<=(const iterator&, const iterator&);
    friend bool operator>=(const iterator&, const iterator&);

    iterator& operator+=(size_type);
    friend iterator operator+(const iterator&, size_type);
    friend iterator operator+(size_type, const iterator&);
    iterator& operator-=(size_type);  
    friend iterator operator-(const iterator&, size_type);
    friend difference_type operator-(iterator, iterator);

    reference operator[](size_type) const;
};

contiguous_iterator : random_access_iterator { //C++17
}; //elements are stored contiguously in memory.

You can either specialize std::iterator_traits<youriterator>, or put the same typedefs in the iterator itself, or inherit from std::iterator (which has these typedefs). I prefer the second option, to avoid changing things in the std namespace, and for readability, but most people inherit from std::iterator.

struct std::iterator_traits<youriterator> {        
    typedef ???? difference_type; //almost always ptrdiff_t
    typedef ???? value_type; //almost always T
    typedef ???? reference; //almost always T& or const T&
    typedef ???? pointer; //almost always T* or const T*
    typedef ???? iterator_category;  //usually std::forward_iterator_tag or similar
};

Note the iterator_category should be one of std::input_iterator_tag, std::output_iterator_tag, std::forward_iterator_tag, std::bidirectional_iterator_tag, or std::random_access_iterator_tag, depending on which requirements your iterator satisfies. Depending on your iterator, you may choose to specialize std::next, std::prev, std::advance, and std::distance as well, but this is rarely needed. In extremely rare cases you may wish to specialize std::begin and std::end.

Your container should probably also have a const_iterator, which is a (possibly mutable) iterator to constant data that is similar to your iterator except it should be implicitly constructable from a iterator and users should be unable to modify the data. It is common for its internal pointer to be a pointer to non-constant data, and have iterator inherit from const_iterator so as to minimize code duplication.

My post at Writing your own STL Container has a more complete container/iterator prototype.

Is There a Readable Implementation of the Stl