Need help understanding operator overloading in C++

Question

I'm trying to implement a structure which is basically a custom made hash table containing either nothing (NULL) or a pointer to a binary search tree object.

Anyway, I'm having trouble figuring out how to do some things, such as setting the hash table, which is an array to NULL, and also memcpy'ing BST objects from one table to another.

BST *prevData;
BST *currData;

As I understand it, I think I have to overload the = and == operators to allow setting array elements to NULL, is this correct? I'm really unclear about how to implement all this, but going on examples from Google, I've got:

BST& BST :: operator= (int null);
bool BST :: operator== (int null);

The == operator overload is to check whether a specific array index is equal to NULL. I'm assuming I need some additional code, rather than just the prototypes, and this is where I come unstuck.

The second point is memcpy, which I'm not being allowed to do by the compiler.

memcpy(prevData[x], currData[x], sizeof(BST) * height);

Complains about

error C2664: 'memcpy' : cannot convert parameter 1 from 'BST' to 'void *' No user-defined-conversion operator available that can perform this conversion, or the operator cannot be called

If you need more information, I'd be happy to fill you in.

Any clues? Thanks.

Answer 1

As I understand it, I think I have to overload the = and == operators to allow setting array elements to NULL, is this correct?

No, not at all. You have described an array of BST * pointers, not of BST objects. NULL is already a valid value for a pointer to take, you don't need to change any C++ behaviour:

BST *array[LENGTH]; // LENGTH > 1
array[0] == NULL;
array[0] == new BST; // but watch for memory leaks!
array[1] == array[0];
array[0] == NULL; // now moved the array[0] pointer to array[1]

Any time you have an array of pointers, memory management becomes tricky, and it becomes important to consider smart pointers such as shared_ptr.

EDIT: as discussed in the comments, a better solution is to have some sort of null BST value:

class BST {
    bool isNull_;
    BST() : isNull_(true) {}
    bool isNull() { return isNull_; }
    // rest of class definition...
};

now, you have an "empty" BST value for which bst.isNull_ is true. The default value is a null value. So if you create an empty vector:

std::vector<BST> vec = std::vector<BST>(10);

this will initialise to 10 null BSTs. The same is true for the new[] array allocation operator.

The second point is memcpy, which I'm not being allowed to do by the compiler.

memcpy(prevData[x], currData[x], sizeof(BST) * height);

Don't do that! It's wrong for a number of reasons, but mainly because it's a legacy C function, not suitable for C++ classes; and because you're copying one item, not a block of them.

To copy one item, use operator=:

currData[x] = prevData[x];

The C++ function for copying block data is std::copy. One reason to use it is that it can recognise overloaded operator= assignment operators, while memcpy can't. Example:

std::copy(prevData, prevData + LENGTH, currData);

(I assume you want to copy from prevData to currData like I've done here, rather than the other way around like you did for memcpy?)

Answer 2

If it wasn't homework (that was your tag?) I'd recommend a single unordered_map or map. You're conception of this isn't coming together yet - best to simplify it and tackle one thing at a time rather than biting off more than you can chew. If you want a hash map of trees, I suggest you start building that from the C++ STL containers that you can rely on to work, then - if you're not supposed to use them for this task - replace them one by one making sure you keep the high-level usage/tests working as you do it. That means:

typedef vector<map<T> > Container;
Container container;

You can use container.resize(n) to fill the container with n empty maps, or to grow the container from some previous size to a new one with the extra maps being empty.

Really, start with that. Then if you have to as an exercise, implement each of the vector and map independently, and test their usage with simple indepedent test cases before slotting them back into your hybrid hash map.

It may sound like I'm being a bit harsh, so lets work through a bit of your question to see some of the mis-conceptions of which I spoke:

Anyway, I'm having trouble figuring out how to do some things, such as setting the hash table, which is an array to NULL, and also memcpy'ing BST objects from one table to another.

My advice is keep things simple and do what's obvious and clean. If you must use an array and not a vector, then if it's on the stack:

X* buckets[N];
for (int i = 0; i < sizeof buckets / sizeof buckets[0]; ++i)
    array[i] = NULL;

If it's on the heap:

X** p_buckets = new X*[N];
for (int i = 0; i < N; ++i)
    array[i] = NULL;

This is slower than memset(), but it's simple and understandable, and gets you in the habit of thinking about looping over your container, doing the operations you want. There are more C++ ways to this, but it's harder to use those same styles of iteration for other arbitrary tasks, so stick to this until you're totally comfortable with it.

BST *prevData; BST *currData;

As I understand it, I think I have to overload the = and == operators to allow setting array elements to NULL, is this correct? I'm really unclear about how to implement all this, but going on examples from Google, I've got:

BST& BST :: operator= (int null); bool BST :: operator== (int null); The == operator overload is to check whether a specific array index is equal to NULL. I'm assuming I need some additional code, rather than just the prototypes, and this is where I come unstuck.

You've got two pointers to BSTs. Your hash tables are an array of such objects, but it's only one of your comment that suggests you conceive of these as pointers to two such hash tables (rather than say being temporary variables recording non-NULL elements during iteration through the hash table). They should be BST*, as they point to the first BST in the hash table. But, this is a very dangerous way to implement your hash tables, as the client is using a pointer to the hash table rather than a pointer to some class that provides a safe implementation of the hash table concept. With such a pointer, all they can do is index to a specific BST, but there's no association with the functions that you intend to maintain the hash table, nor the variables that track how many buckets it currently has space for, how many elements it contains, etc.. You should put your arrays into a class that provides all this; there are lots of design decisions, but it should look something like this:

template <typename Key, typename Value>
class Hash
{
  public:
    Hash() : p_(NULL), size_(0), num_buckets_(0) { }

    // find/make entry for Key, giving read/write access to the current/a-default value
    Value& operator[](const Key&);        
    const Value& operator[](const Key&) const;

    // try to find an entry, throw an exception if not found...
    Value& at(const Key&);
    const Value& at(const Key&) const;

    // report whether a key is already in the hash table...
    bool has_key(const Key&) const;

    int size() const;

  private:
    BST* p_;
    int num_buckets_;
    int size_;
};

(yet again, I can only recommend that you first try this with p_ replaced with that vector of maps).

The second point is memcpy, which I'm not being allowed to do by the compiler.

memcpy(prevData[x], currData[x], sizeof(BST) * height);

Complains about

error C2664: 'memcpy' : cannot convert parameter 1 from 'BST' to 'void *' No user-defined-conversion operator available that can perform this conversion, or the operator cannot be called

It's a very bizarre request to copy everything from one bucket in one hash table into the same bucket in another hash table. If, for example, the number of buckets differs or the hash function differs then you'll probably corrupt the destination bucket. Anyway, I suggest you implement a BST class with value semantics (i.e. a copy constructor and operator= that replicates an existing tree). Then you can simply use:

prevData.buckets[x] = currData.buckets[x];

(note: operator should look up in the hash table, and given the key type ought to be able to be int, you don't want to use the same notation for copying entire buckets - you can't overload a function if both have the same signature. That's why here I show buckets being the exposed container of BSTs - exposing this breaks encapsulation; in real classes you just don't want users even aware of the buckets (or BSTs for that matter)).