std::map Alternatives

Hi,

In my application I currently use std::map. However, I have found no way to solve the following problems: when an invalid key is passed to operator[] it inserts a new element into the map.

This is undesirable as my map is rather large to say the least (2-3GiB) in some instances, with 99% of the values being 0 (my map is std::map<std::pair<int, int>, int>). Therefore big savings are to be had by assuming a default value of 0.

But, STL containers do not like being sub-classed and so implementing such functionality is not really possible.

Therefore, I am interested in alternatives which would support 'default values' for a key. Does anyone have any suggestions? (My application is currently just STL + Boost.)

Regards, Freddie.

Quote:

---

Originally Posted by EvilGuru

Hi,

In my application I currently use std::map. However, I have found no way to solve the following problems: when an invalid key is passed to operator[] it inserts a new element into the map.

---

Don't use operator[] -- use find(). If the key does not exist, it will return end(). We had another discussion on this topic just this morning.

Example:

Code:

---

map_type::const_iterator i = my_map.find(some_key);
if(i == my_map.end())
{
    // Key not found
}
else
{
    // Key found -- the corresponding item is in:
    i->second;
}

---

You might encapsulate this in a lookup function which returns the default value (0) if the key isn't found.

I actually don't use operator[] for maps very often. Using find works fine.

Here's a generic function that looks up a key in a map and returns the corresponding value, or a default value if the key is not found. You can specify the default to use, otherwise it will use the "default default" which is to default construct the data type. It never inserts anything:

Code:

---

template <typename C>
typename C::data_type find_or_default(const C &container_p, typename C::key_type key_p,
    typename C::data_type default_p = typename C::data_type ())
{
    typename C::const_iterator i = container_p.find(key_p);
    if(i == container_p.end()) return default_p;
    return i->second;
}

---

It should work on any mapping type. Have not compiled or tested it. If you data_type does not have a default constructor, you will have to remove the default-default argument (too many occurrences of the word "default!")

I think data_type should be value_type

Quote:

---

Originally Posted by laserlight

I think data_type should be value_type

---

Hmm, I think value_type is actually std:: pair<key_type, data_type>, in other words, the type of object you get when you dereference the iterator..

Quote:

---

Hmm, I think value_type is actually std:: pair<key_type, data_type>, in other words, the type of object you get when you dereference the iterator..

---

hmm... that's right. The standard gives mapped_type as the correct typedef.

Quote:

---

Originally Posted by laserlight

hmm... that's right. The standard gives mapped_type as the correct typedef.

---

Yeah, I just realized I'm going off the old SGI "standard" instead of the real one. Most STL implementations will provide "data_type" for backward compatibility, but yes -- mapped_type is preferable.

Thanks!

That did the trick.

Regards, Freddie.