4
\$\begingroup\$

I am quite new to C++ and would like some feedback on my implementation of a dictionary data structure. The code is below.

#ifndef DICTIONARY_H_INCLUDED
#define DICTIONARY_H_INCLUDED

#include <initializer_list>
#include <algorithm>
#include <vector>

template <typename T, typename U>
class Dictionary{
    private:
        std::vector<T> keys;
        std::vector<U> values;
    public:
        Dictionary();
        Dictionary(std::initializer_list<std::pair<T,U>>);
        bool has(T) const;
        void add(T,U);
        T* begin();
        T* end();
        U operator[](T);
};

template <typename T, typename U>
T* Dictionary<T,U>::begin(){
    return &(keys[0]);
}

template <typename T, typename U>
T* Dictionary<T,U>::end(){
    return &(keys[keys.size()-1])+1;
}

template <typename T, typename U>
Dictionary<T,U>::Dictionary (std::initializer_list<std::pair<T,U>> store){
    for (std::pair<T,U> object : store){
        keys.push_back(object.first);
        values.push_back(object.second);
    }
}

template <typename T, typename U>
bool Dictionary<T,U>::has(T targetKey) const{
    for (T currentKey : keys){
        if (currentKey == targetKey){
            return true;
        }
    }
    return false;
}

template <typename T, typename U>
void Dictionary<T,U>::add (T key, U value){
    keys.push_back(key);
    values.push_back(value);
}

template <typename T, typename U>
U Dictionary<T,U>::operator[] (T key){
    unsigned int pos = std::find(keys.begin(), keys.end(), key) - keys.begin();
    return values[pos];
}

#endif // DICTIONARY_H_INCLUDED
\$\endgroup\$
  • 3
    \$\begingroup\$ Do you have any tests, or sample code that shows how it's used? That would help people to review this. \$\endgroup\$ – Toby Speight Nov 21 '18 at 21:32
7
\$\begingroup\$

The representation (as a parallel pair of vectors) isn't as good as the alternative (a single vector of pairs), because:

  1. any time the vectors have to grow, there's two separate allocations rather than just one, and
  2. whenever they are used, the data may be in different regions of memory (the code has poorer spatial locality).

Consider instead writing

using value_type = std::pair<T, U>;
std::vector<value_type> entries;

This will change the interface a little - in particular, begin() and end() will now give iterators that access these pairs. That's more consistent with std::map interface, so I recommend that.


We can reduce duplication a little: in the initializer-list constructor, we can simply call add() for each element rather than re-writing its body:

template <typename T, typename U>
Dictionary<T,U>::Dictionary (std::initializer_list<std::pair<T,U>> store)
{
    for (std::pair<T,U> object : store) {
        add(object.first, object.second);
    }
}

On the other hand, if we've changed our representation as above, we simply have

template <typename T, typename U>
Dictionary<T,U>::Dictionary (std::initializer_list<std::pair<T,U>> store)
{
    for (std::pair<T,U> object : store) {
        entries.push_back(object);
    }
}

The indexing operator is surprising. If key doesn't exist in the dictionary, then we have undefined behaviour (accessing values out of range). That's a valid choice, but worthy of a comment (particularly as it diverges from the Standard Library interface). Since it doesn't create as necessary, and only ever returns a copy of the value (rather than a reference) it probably ought to be declared const.


We should probably check whether key already exists in add(). We can then either ignore it, or update the existing value. What we have at the moment is the worst possible choice - we add data that can never be used, which only serves to slow future operations.


Some other useful accessors are missing - constant and/or reverse iterators spring to mind as an obvious example, as do methods of removing values. A swap() member would also be very useful.


The has function can be simplified a bit with the use of a standard algorithm: std::any_of() can replace the loop.


Algorithmic complexity

Our operator[] uses linear search with std::find(). Whilst this works, it will get slower in proportion to the number of elements contained - in "big O" notation, we say that it scales as O(n). Once we have the interface as we we want, we'll then want to look at changing the data structure to improve look-up times (and we might need to trade against insertion speed). The good news is that storing items as pairs will work well with whatever storage we choose, and it will be much easier to change the implementation than with separate storage of keys and values.

It may well be worth moving to pair-based storage, and implementing the other review items, and then returning for a performance review of the new code.

\$\endgroup\$
  • \$\begingroup\$ Shouldn't you have tackled performance issues also? O(n) look-up isn't acceptable in a map-like container, because it wouldn't add anything to a simple std::vector + std::find. \$\endgroup\$ – papagaga Nov 22 '18 at 9:49
  • \$\begingroup\$ Yes, you're right - I wrote this in a rush and didn't get to that part. I believe it's important to get the interface right first, and there were sufficient changes there that changing the algorithm was going to be too much in one go. \$\endgroup\$ – Toby Speight Nov 22 '18 at 10:13
  • \$\begingroup\$ @papagaga - I've edited to recommend returning for a performance review after first round of fixes. \$\endgroup\$ – Toby Speight Nov 22 '18 at 10:21
5
\$\begingroup\$

Definition for default constructor is missing.


Begin() and end() cause UB when dictionary is empty because you performed out of bound access on the keys vector. Begin and end should return iterator that allow access of both key and value.

\$\endgroup\$
  • \$\begingroup\$ Good observations - I missed both of these in my review. \$\endgroup\$ – Toby Speight Nov 22 '18 at 8:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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