Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Overloading [] in C++ to return lvalue

I'm writing a simple hash map class:

template <class K, class V> class HashMap;

The implementation is very orthodox: I have a heap array which doubles in size when it grows large. The array holds small vectors of key/value pairs.

Vector<Pair<K, V> > *buckets;

I would like to overload the subscript operator in such a way that code like this will work:

HashMap<int, int> m;
m[0] = 10; m[0] = 20;
m[2] = m[1] = m[0];

In particular,

  • For m[k] = v where m does not contain k, I'd like a new entry to be added.
  • For m[k] = v where m does contain k, I'd like the old value to be replaced.
  • In both of these cases, I'd like the assignment to return v.

Presumably the code will look something like

V& operator[](K &key)
{
    if (contains(key))
    {
        // the easy case
        // return a reference to the associated value
    }
    else
    {
        Vector<Pair<K, V> > *buck = buckets + hash(k) % num_buckets;
        // unfinished
    }
}

How should I handle the case where the key is not found? I would prefer to avoid copying values to the heap if I can.

I suppose I could make a helper class which overloads both the assignment operator and a cast to V, but surely there is a simpler solution?

Edit: I didn't realize that std::map required that the value type have a zero argument constructor. I guess I will just default-construct a value as well.

like image 261
Daniel Lubarov Avatar asked Jun 08 '11 04:06

Daniel Lubarov


People also ask

Can [] operator be overloaded?

An overloaded operator (except for the function call operator) cannot have default arguments or an ellipsis in the argument list. You must declare the overloaded = , [] , () , and -> operators as nonstatic member functions to ensure that they receive lvalues as their first operands.

Can you overload based on return type?

No, you cannot overload a method based on different return type but same argument type and number in java.

What should an overloaded operator return?

Operator Overloading is the method by which we can change the function of some specific operators to do some different task. In the above syntax Return_Type is value type to be returned to another object, operator op is the function where the operator is a keyword and op is the operator to be overloaded.

Can we overload method by changing return type in C++?

Function overloading and return type in C++ The definition of the function must differ from each other by the types and/or the number of arguments in the argument list. You cannot overload function declarations that differ only by return type. The function overloading is basically the compile time polymorphism.


2 Answers

How should I handle the case where the key is not found?

Insert a new element with that key and return a reference to the value of that new element. Effectively, your pseudocode becomes something equivalent to:

if (!contains(key))
    insert(Pair<K, V>(key, V()));
return reference_to_the_element_with_that_key;

This is exactly what your requirement is, too. You said "For m[k] = v where m does not contain k, I'd like a new entry to be added."

like image 119
James McNellis Avatar answered Oct 08 '22 04:10

James McNellis


How should I handle the case where the key is not found?

std::map creates a new object, and inserts it into the map, and returns its reference. You can also do the same.

Alternatively, you can throw an exception KeyNotFoundException like the way .NET map throws. Of course, you've to define KeyNotFoundException yourself, possibly deriving from std::runtime_exception.

By the way, as a general rule, always implement operator[] in pair as:

V &operator[](const K &key);
const V &operator[](const K &key) const;

Just for the sake for const-correctness. However, if you decide to create a new object and insert it into the map, when the key is not found, then this rule is not applicable here, as const version wouldn't make sense in this situation.

See this FAQ:

  • What's the deal with "const-overloading"?
like image 40
Nawaz Avatar answered Oct 08 '22 02:10

Nawaz