Pointer to template parameter type

Question

I am trying to make my own container, which is just a wrapper around a std::unordered_map that keeps track of the insert order with a std::vector.

Here is my (simplified) class :

template <class tKey, class tValue>
class OrderedMap
{
public:
    typedef size_t tSize;
    inline bool contains(const tKey& key) const { return map_.count(key) > 0; }
    inline tValue& at(const tSize& index) { return vector_[index]; }
    inline tValue& operator [](const tKey& key)
    {
        if(!contains(key)) { throw std::out_of_range("Unknown key"); }
        return *map_[key];
    }
    inline void push_back(const tKey& key, const tValue& value)
    {
        vector_.push_back(value);
        map_[key] = &vector_[size()-1];
    }
    inline void set(const tKey& key, const tValue& value)
    {
        if(!contains(key)) push_back(key, value);
        else *map_[key] = value;
    }

private:
    std::vector<tValue> vector_;
    std::unordered_map<tKey, tValue*> map_;
};

The thing is when I try to execute this code sample :

OrderedMap<std::string, std::vector<std::string> > myContainer;
myContainer.set("1", {"11", "12"});
myContainer.set("2", {"21", "22"});
auto myValues = myContainer["1"];

Something wrong is happening when I try to access the data. In this example it triggers an exception telling me the vector is too long when the program tries to copy the data into myValues, but somewhere else in my code it ends in a read access violation error when dereferencing the pointrer inside operator [].

Clearly I made a mistake somewhere, but I can't find, so what's wrong with my code ? Am I missing something about template paramters and referencing them ?

edit: I am on Windows compiling with MSVC 12.0.

NathanOliver · Accepted Answer · 2016-08-11T12:58:43.910

3

It is normally a very bad idea to store pointers/references/iterators to elements in a growing vector. In

inline void push_back(const tKey& key, const tValue& value)
{
    vector_.push_back(value);
    map_[key] = &vector_[size()-1];
}

You add the element into the vector and then you store a pointer to that element in the map. The problem with this is if you keep adding items to the vector, the vector is going to need to grow which means allocating new memory. This means that the elements in the vector are no longer where they used to be which means all of the pointers in the map are now dangling(point to garbage).

The simple fix would be to store the element in both places. You could also create a std::shared_ptr and store the shared_ptr in both containers.

edited Aug 11 '16 at 12:58

answered Aug 11 '16 at 12:52

NathanOliver

171,901
28
288
402

I think instead of using a vector, a list would fix this problem. – Kokozaurus Aug 11 '16 at 12:55
1

@Dr.Nefario It could be. It really depends on the use cases. `list` is bad for traversal so if there is a lot of that then it could hamper performance. Good suggestion though. – NathanOliver Aug 11 '16 at 12:56
"The simple fix would be to store the element in both places." unless you plan on using a pointer (raw or managed) this would cause there to be two distinct copies of `value` in each data structure, just an fyi for @Wexiwa. @DrNefario is correct in that `list` provides a stricter guarantee for preventing element [pointer invalidation](http://stackoverflow.com/a/23872017/591495) – obataku Aug 11 '16 at 13:01

Pointer to template parameter type

1 Answers1