basic_string implementation

First stop using underscores like that.

1. Double underscore is always reserved for the implementation.
2. A leading underscore followed by a capital letter is always reserved for the implementation.

There are a couple of more rules. But basically unless you want to memorize stop using identifiers with double or a leading underscore. The problem is most beginners seem to want to learn from the standard library and pick that habit up there. The standard library is part of the implementation and thus they can do it. But you as an application level programmer can not.

Bind the & and * to the type not the variable. They are part of type declaration not part of the variable.

 int*     x; // x is the variable  `int*` is the type.

Tidy up your declarations; they are hard to read.

typedef basic_string<_Elem, _Traits, _Alloc> _Myt;
typedef _Elem value_type;
typedef _Traits traits_type;
typedef _Alloc allocator_type;
typedef value_type *pointer;
typedef const value_type *const_pointer;
typedef value_type *iterator;
typedef const value_type *const_iterator;
typedef value_type &reference;
typedef const value_type &const_reference;
typedef std::size_t size_type;
typedef std::ptrdiff_t difference_type;

Much easier to read:

typedef basic_string<_Elem, _Traits, _Alloc> _Myt;
typedef Elem               value_type;
typedef Traits             traits_type;
typedef Alloc              allocator_type;
typedef value_type*        pointer;
typedef const value_type*  const_pointer;
typedef value_type*        iterator;
typedef const value_type*  const_iterator;
typedef value_type&        reference;
typedef const value_type&  const_reference;
typedef std::size_t        size_type;
typedef std::ptrdiff_t     difference_type;

Your use if allocator is making the code harder to read than necessary. You should have written the code without allocators. Got it reviewed and corrected then added the allocator where necessary.

    _Alloc().construct() // Used to call the constructor
                         // when doing an inplace new.
    _Alloc(). destroy()  // Used to call the destructor on
                         // an object that was created by
                         // inplace new

We are dealing with characters and thus construction and destruction are completely irelavant to a string.

Fundamental flaw in your design is that you don't keep track of the string size as a member of the class. You re-calculate it every time by searching along the string looking for the \0 marker. This is a real problem with your design fix it otherwise your class is little better than a C-String.

Are you really only going to allocate 1 byte in the constructor?

basic_string()
{
    __data = _Alloc().allocate(1);
    _Alloc().construct(&__data[0], '\0');
}

Its likely that string will be expanded real soon. usually you see to size variables in this type of container. The amount currently being used (size). The amount we have allocated for use (reserved).

This is a dasterdly and very dangerious thing to do:

basic_string(void *_Init)
{
    *this = basic_string(reinterpret_cast<const_pointer>(_Init));
}

Most pointers auto convert to void* so your string here will initialize with any pointer and pretend it is a string. NOT a good idea. Make people be specific.

Don't need to check for copy construction against yourself.

basic_string(const _Myt &_Init)
{
    if (this != &_Init) {
        ...
    }
}

You are not constructed yet. So you can not be passed as an argument to another constructor so there can never be copy construction from self.

This is a very expensive copy operation.

        *this = basic_string(_Init.c_str());

You convert to a C-String. Build a separate object that does not use the intrinsic properties of the class but builds from a native C-String (this is a class I would expect it to know its own size (here you are re-calculating it). Then you perform an assignment (which usually involved creating another copy and destroying it).

It should be as simple as this (add your allocator as needed).

  basic_string(Myt const& copy)
     : data(Alloc().allocate(copy.size+1))
     , size(copy.size)
  {
      std::copy(&copy.data[0], &copy.data[copy.size+1], &data[0]);
  }

Everywhere else in your code you use Alloc().construct() but in the assign() you use std::copy().

    std::copy(&_Rhs[0], &_Rhs[_Traits::length(_Rhs)], &buf[0]);
    _Alloc().construct(&buf[_Traits::length(_Rhs)], '\0');

Be consistent.

You have defined an assignment operator for C-String but not for real assignment. So you have not fulfilled the rule of three. because you did not define one the compiler generated one for you and it will not work correctly with RAW owned pointers.

Its simple to implement use the copy and swap idum.

Myt &operator=(Myt rhs) // pass by value to get a copy.
{
    rhs.swap(*this);    // Swap the content with the copy.
    return *this;
}

std::size is unsigned it can never be negative.

reference at(size_type _Base)
{
    if (_Base >= 0 && _Base < size())
     // ^^^^^^^^^^  Never be false

Violating the DRY principle here

// These two functions are identical to the non const versions.
const_reference operator[](size_type _Base) const
const_reference at(size_type _Base) const

This is a complicated way

        for (iterator i = begin(); i != end(); ++i)
        {
            if (i == &__data[_Size])
            {
                while (i != end())
                {
                    _Alloc().destroy(i++);
                }
            }
        }

of saying

        for (iterator i = &data[_Size]; i != end(); ++i)
        {
            _Alloc().destroy(i);
        }

Also because you are using the \0 as a terminator to define the end of the string you forgot to move it.

The concept of reserve makes no sense for your class as you have no way of tracking the amount of space you reserved. You have an size marker but no reserve end of space marker.

void reserve(size_type _Size) // makes no sense

Reserved space is be definition unused. So you should not be constructing into it.

    for (int i = size(); i < _Size; ++i)
    {
        _Alloc().construct(&buf[i], '\0');
    }

You should construct into it when it becomes used. And destroy from it when it becomes unused.

Compiler can't assume the Traits::Length() has no side affects. So worst case you are calculating the length many times here.

    return _Traits::length(_Lhs) < _Traits().length(_Rhs) ? _Lhs
        : _Traits::length(_Rhs) < _Traits().length(_Lhs) ? _Rhs : _Lhs;

Here you run across the length of the string twice to do a comparison.

    return _Traits::compare(__data, _Rhs, _Traits::length(longest(*this, _Rhs))) == 0;

You run along the string to find the length. Then you run along the string again to do the comparison. Seems like a lot of wasted effort.

The starting pointer for a container class should look like this:

#include <cstddef>
#include <algorithm>
#include <functional>

template<typename C>
class mString
{
    // Keep track of three things
    private:
        C*   start;          // points first character
        C*   finish;         // points one past end of used space
        C*   reservedEnd;    // points one past end of allocated space

        // Note: string is also '\0' terminated.
        //       So finish points at '\0' and thus is never equal to reservedEnd
    public:

// Typedef needed for a container.
// Basic references to storage type.

        typedef     C                   value_type;
        typedef     value_type*         pointer;
        typedef     value_type const*   const_pointer;
        typedef     value_type&         reference;
        typedef     value_type const&   const_reference;

        // Iterator types. (not related to storage types)
        typedef     C*                  iterator;
        typedef     C const*            const_iterator;
        typedef     std::reverse_iterator<iterator>         reverse_iterator;
        typedef     std::reverse_iterator<const_iterator>   const_reverse_iterator;

        // Utility types.
        typedef     std::size_t         size_type;
        typedef     std::ptrdiff_t      difference_type;

// Four basic methods required
// To implement a non leaking class that
// owns a RAW pointer.

        mString()
            : start(new C[15])
            , finish(start)
            , reservedEnd(start + 15)
        {
            start[0] = '\0';
        }
        mString(mString const& copy)
            : start(new C[copy.size() + 1])
            , finish(start + copy.size())
            , reservedEnd(finish + 1)
        {
            std::copy(copy.start, copy.finish + 1, start);
        }
        mString& operator=(mString rhs)
        {
            rhs.swap(*this);
            return *this;
        }
        ~mString()
        {
            delete [] start;
        }

// Methods required to implement the Container concept.

        void swap(mString& other) noexcept
        {
            std::swap(start,       other.start);
            std::swap(finish,      other.finish);
            std::swap(reservedEnd, other.reservedEnd);
        }

        iterator        begin()                 { return start;}
        iterator        end()                   { return finish;}
        const_iterator  begin() const           { return start;}
        const_iterator  end()   const           { return finish;}
        const_iterator  cbegin()const           { return start;}
        const_iterator  cend()  const           { return finish;}

        bool        empty()     const           { return start == finish; }
        std::size_t max_size()  const           { return 10000;} // Arbitrary (look up numeric limits)
        std::size_t size()      const           { return finish-start; }

// Methods required to implement the Forward Container concept

        bool        operator==(mString const& rhs) const    {return size() == rhs.size() && std::equal(start, finish, rhs.start);}
        bool        operator!=(mString const& rhs) const    {return !operator==(rhs);}
        bool        operator<(mString const& rhs)  const    {std::less<value_type>          t; return size() < rhs.size() ? test(rhs, t) : rhs.test(*this, t);}
        bool        operator>(mString const& rhs)  const    {std::greater<value_type>       t; return size() < rhs.size() ? test(rhs, t) : rhs.test(*this, t);}
        bool        operator>=(mString const& rhs)  const   {std::greater_equal<value_type> t; return size() < rhs.size() ? test(rhs, t) : rhs.test(*this, t);}
        bool        operator<=(mString const& rhs)  const   {std::less_equal<value_type>    t; return size() < rhs.size() ? test(rhs, t) : rhs.test(*this, t);}

// Methods require to implement the Reversible Container concept

        reverse_iterator        rbegin()            { return reverse_iterator(finish); }
        reverse_iterator        rend()              { return reverse_iterator(start); }
        const_reverse_iterator  rbegin() const      { return const_reverse_iterator(finish); }
        const_reverse_iterator  rend()   const      { return const_reverse_iterator(start); }

// A SINGLE method to convert a C-String into a string

        mString(C* cString)
            : start(new C[(cString ? strlen(cString) : 0) + 15])
            , finish(start + (cString ? strlen(cString) : 0))
            , reservedEnd(finish + 15)
        {
            std::copy(cString, cString + size() + 1, start);
        }


        private:
            template<typename F>
            bool test(mString const& other, F f) const // makes assumptions about length (this must not be larger than other)
            {
                auto mis = std::mismatch(start, finish, other.start);
                return f(mis->first, mis->second);
            }

};