Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

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 < typename _Key, typename _Ty, typename _Cmp = std::less<_Key>, typename _Alloc = std::allocator< std::pair<const _Key, _Ty> > > class map
{
public:
    typedef map<_Key, _Ty, _Cmp, _Alloc> _Myt;
    typedef _Key key_type;
    typedef _Ty mapped_type;
    typedef _Cmp compare_type;
    typedef _Alloc allocator_type;
    typedef std::pair<const key_type, mapped_type> 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 &_Rhs)
        : size_(_Rhs.size_), capacity_(_Rhs.size_ + 20), data_(_Alloc().allocate(_Rhs.size_))
    {
        int count = 0;
        for (iterator i = &_Rhs.data_[0]; i != &_Rhs.data_[_Rhs.size_]; ++i, ++count)
        {
            _Alloc().construct(&data_[count], *i);
        }
    }

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

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

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

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

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

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

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

    iterator end()
    {
        return &data_[size_];
    }
private:
    pointer data_;
    size_type size_, capacity_;
};
share|improve this question
    
I am downvoting this for your use of reserved identifiers. You have been advised not to do this in all of your previous STL exercise that you put up here for review. Please STOP AND READ. –  TemplateRex Mar 12 at 19:58
add comment

3 Answers 3

Readability

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

template </*...*/>
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 &data_[0];
    }
    
    const_iterator cend() const
    {
        return &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 &_Key) const
    {
        for (const_iterator i = cbegin(); i != cend(); ++i)
        {
            if (i->first == _Key)
            {
                return true;
            }
        }
        return false;
    }
    
share|improve this answer
    
Having const_iterator begin() const; is probably a higher priority than cbegin(), 'twas introduced first because it's the more useful, propagating const correctness in certain template situations. The lack of const correctness obviously led to for (iterator i = &_Rhs.data_[0]; i != &_Rhs.data_[_Rhs.size_]; ++i, ++count) - that can be cleaned up as ...i = rhs.begin(); i != rhs.end();.... –  Tony D Mar 14 at 23:31
add comment

[...] I am not sure if the operator[] is done correctly: should I be using the has_key function?

It is done correctly (i.e. it does what the contract of it's API should), but not efficiently. The operator iterates twice (once in has_key and once in the operator). You can replace both calls with a call to std::find_if, and remove the has_key function completely.

share|improve this answer
add comment

You are searching two times the entire arrays to find your key,pair value. This is highly inefficient. Instead you could extend your has type to take two arguments and in the second argument it could store the value. This way you only iterate once.

Otherwise yes, reusing your code is a yes yes, just don't iterate two times when you could easily done it once.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.