Implementation of std::map I have decided to make a basic C++ implementation of the std::map class, and I was checking that it is fine, as I am not sure if the operator[] is done correctly: should I be using the has_key function? e.t.c

template &lt; typename _Key, typename _Ty, typename _Cmp = std::less&lt;_Key&gt;, typename _Alloc = std::allocator&lt; std::pair&lt;const _Key, _Ty&gt; &gt; &gt; class map
{
public:
    typedef map&lt;_Key, _Ty, _Cmp, _Alloc&gt; _Myt;
    typedef _Key key_type;
    typedef _Ty mapped_type;
    typedef _Cmp compare_type;
    typedef _Alloc allocator_type;
    typedef std::pair&lt;const key_type, mapped_type&gt; value_type;
    typedef value_type *pointer;
    typedef const value_type *const_pointer;
    typedef value_type *iterator;
    typedef const value_type *const_iterator;
    typedef std::size_t size_type;
    typedef std::ptrdiff_t difference_type;

    map()
        : size_(0), capacity_(20), data_(_Alloc().allocate(20))
    {
    }

    map(const _Myt &amp;_Rhs)
        : size_(_Rhs.size_), capacity_(_Rhs.size_ + 20), data_(_Alloc().allocate(_Rhs.size_))
    {
        int count = 0;
        for (iterator i = &amp;_Rhs.data_[0]; i != &amp;_Rhs.data_[_Rhs.size_]; ++i, ++count)
        {
            _Alloc().construct(&amp;data_[count], *i);
        }
    }

    ~map()
    {
        if (!empty())
        {
            for (iterator i = begin(); i != end(); ++i)
            {
                _Alloc().destroy(i);
            }
            _Alloc().deallocate(data_, capacity_);
        }
    }

    _Myt &amp;insert(const value_type &amp;_Value)
    {
        if (++size_ &gt;= capacity_)
        {
            reserve(capacity_ * 2);
        }
        _Alloc().construct(&amp;data_[size_ - 1], _Value);
        return *this;
    }

    bool has_key(const key_type &amp;_Key)
    {
        for (iterator i = begin(); i != end(); ++i)
        {
            if (i-&gt;first == _Key)
            {
                return true;
            }
        }
        return false;
    }

    mapped_type &amp;operator[](const key_type &amp;_Key)
    {
        if (has_key(_Key))
        {
            for (iterator i = begin(); i != end(); ++i)
            {
                if (i-&gt;first == _Key)
                {
                    return i-&gt;second;
                }
            }
        }
        size_type op = size_;
        insert(value_type(_Key, mapped_type()));
        return data_[op].second;
    }

    _Myt &amp;reserve(size_type _Capacity)
    {
        int count = 0;
        if (_Capacity &lt; capacity_)
        {
            return *this;
        }
        pointer buf = _Alloc().allocate(_Capacity);
        for (iterator i = begin(); i != end(); ++i, ++count)
        {
            _Alloc().construct(&amp;buf[count], *i);
        }
        std::swap(data_, buf);
        for (iterator i = &amp;buf[0]; i != &amp;buf[size_]; ++i)
        {
            _Alloc().destroy(i);
        }
        _Alloc().deallocate(buf, capacity_);
        capacity_ = _Capacity;
        return *this;
    }

    bool empty()
    {
        return size_ == 0;
    }

    iterator begin()
    {
        return &amp;data_[0];
    }

    iterator end()
    {
        return &amp;data_[size_];
    }
private:
    pointer data_;
    size_type size_, capacity_;
};
Readability

With your lengthy template statement, I'd put the class statement onto the next line:

template &lt;/*...*/&gt;
class map


Naming standards

According to this answer, identifiers in the form _Identifier are reserved:


  7.1.3 Reserved identifiers
  
  Each header declares or defines all identifiers listed in its
  associated subclause, and optionally declares or defines identifiers
  listed in its associated future library directions subclause and
  identifiers which are always reserved either for any use or for use as
  file scope identifiers.
  
  
  All identifiers that begin with an underscore and either an uppercase
  letter or another underscore are always reserved for any use.
  
  
  [...]


Const-correctness


You have iterators, but you should also have const iterators:

const_iterator cbegin() const
{
    return &amp;data_[0];
}

const_iterator cend() const
{
    return &amp;data_[size_];
}

empty() should be const:

bool empty() const
{
    return size_ == 0;
}

has_key() should be const and use the aforementioned const iterators:

bool has_key(const key_type &amp;_Key) const
{
    for (const_iterator i = cbegin(); i != cend(); ++i)
    {
        if (i-&gt;first == _Key)
        {
            return true;
        }
    }
    return false;
}