Template data types implementation

Question

I'm preparing for an exam on C++, as part of my preparation I want to implement a generic map without using anything from the STD for educational purposes.

Before jumping into implementation of everything, I want to know that the skeleton for my Map is solid and I use templates and template inheritance correctly.

Above is the skeleton of my Map. I would like to get an opinion about that skeleton.

#ifndef  MAP_H_
#define MAP_H_

template <class K, class V>
class Map {
public:
    /*
        Map c'tors and d'tors.
    */
    Map(); //C'tor
    Map(const Map& map); //Copy c'tor
    ~Map(); //D'tor


    /*
        Map methods
    */
    void insert(const K& key, const V& value);
    bool isIn(const K& key) const;
    void remove(const K& key);
    void clear();
    bool isEmpty();
    int size() const;

    template <class F>
    Map filter(F& filterFunction);


    /*
        Map methods using Iterators
    */
    class Iterator;
    class ConstIterator;
    Map::ConstIterator begin() const;
    Map::ConstIterator end() const;
    Map::Iiterator begin();
    Map::Iterator end();


    /*
        Map operators
    */
    const DataType& operator[](const KeyType key) const;
    DataType& operator[](const KeyType key);
};


/*
    Map::Pair class
*/
template <class K, class V>
class Map<K,V>::Pair {

};


/*
    Map::Iterator class
*/
template <class K, class V>
class Map<K,V>::Iterator {
    //to do
};


/*
    Map::ConstIterator class
*/
template <class K, class V>
class Map<K,V>::ConstIterator : public Map<K,V>::Iterator {
    //to do
};


/*
    Map c'tors, methods and operators implementation
*/

//to do


#endif /*  MAP_H_  */

---

Answer 1

Here are some small things you could di in order to improve your design:

• First of all, you have a typo: you wrote Map::Iiterator begin(); instead of Map::Iterator begin();.
• You use KeyType and DataType but do not even declare them.
• For client code that uses generic code, it would be great if the name of the functions and subtypes were consistent with the STL. That means that you should be using empty(), iterator, const_iterator, etc...
• The STL also defines subtypes like value_type, reference_type, size_type, etc... It would be better if you provided those too :)
• Since you are using C++11, you could also provide the member functions cbegin and cend, for the same reason (consistency with standard containers).
• You could have used std::size_t for the size() function (or even better, Map<K, V>::size_type), but using such an unsigned type can also lead to some unexpected problems. I wasn't able to find any relevant article, otherwise I would have linked one.
• operator[] should take its elements by const&. You probably don't want to copy entire std::string instances when using this function.
• Last but not least, I have no idea what your function filter is supposed to do. My guess is that it returns a filtered version of the Map, in which case the name filtered may be more suitable. Otherwise, if it filters the current map in place, it should probably return a Map& instead of a Map. Anyway, you better document it to remove the potential ambiguities. Moreover, we don't know whether the filter function filters the Map on its keys or on its values.

Well, otherwise, I don't think there are obvious errors in the design. There are probably some other things that can be improved, but generally speaking it's not bad :)

Answer 2

The one thing that immediately jumped at me: ConstIterator should not inherit from Iterator. If you want to reuse code, do it the other way around, but I would recommend even against that. Instead, try to make a common template.