CODEWITHSUNDEEP
c++dictionary
wannabe programmer
wannabe programmer

Reputation: 683

Implement Map in C++ with a predefined size

I want to implement my own version of a map data structure in C++. I need its size to be predefined so I decided that when the user creates the map he will have to specify not only the size, but also a default value for the keys and for the values. before you ask - I need this in order to be able to use that data structore in an embedded system.

I have written this constructor:

template <typename T, typename K>
myMap<T, K>::myMap(int size, const T& keyInit, const K& valueInit) :
size(nSize), defaultKey(keyInit), defaultValue(valueInit)
{
    for (int i = 0; i < nSize; i++)
    {
        container.insert(std::make_pair(keyInit,valueInit));
    }
}

where container is a member of type: std::map<T, K> (and basically the class is just a wrapper for the stl map)

now I'm not sure how to implement the insert function. aside from that I have figured out how to delete (reassgin default values) and how to search (use stl's maps find). So my only problem right now is the insert method.

I thought about iterating through the map and looking for the first free cell but it got me confused and I' stuck. Any other ideas would be great.

Upvotes: 1

Views: 697

Answers (3)

Zan Lynx
Zan Lynx

Reputation: 54393

For an embedded system what I think you actually want is custom memory allocators. You can define an allocation pool for each data structure you want to use. Then you pass it to the constructor for the map and it will allocate data from the pool. When the pool is empty it will send out bad_alloc exceptions.

Upvotes: 0

Tom
Tom

Reputation: 986

Key in std::map is unique, so what you do at construction does not make sense.

If you seek great performance (as this may be the case in embedded world), then I would advise to find some other hash table implementation. You can also implement your own hash table to meet your needs.

Upvotes: 0

Christophe
Christophe

Reputation: 73627

If I've understood well, you make a wrapper for a standard container, i.e. a map.

At construction, you intend to insert several the same default key. This is not allowed in a std::map, where the key MUST be unique.

If you want to use several time the same key in a map, you have to use a multimap: you can use it almost as a map, but it allows to have duplicate keys.

I'm not sure why you create items with a default key, but you have to be aware that maps and multimaps work with ordered keys. So if you intend later to replace the default key with another one, you can't just replace the values: you have to delete the entry and insert a new one.

Upvotes: 1

Related Questions