1
\$\begingroup\$

I often find myself in the following position: I have created a class in some file, and would like to add a new data member to that class without changing the original class definition. Now, you cannot actually add a new data member to a class without changing the class definition. So instead, I'd like to "simulate" (in some sense) a new data member.

What do I mean by this? In an implementation of the disjoint sets data structure, objects in the disjoint sets have two properties - they have a "rank" (which is an integer) and they have a "parent" (which is another object of the same class). In Kruskal's algorithm, such a disjoint union data structure is used to represent disjoint sets of vertices. It makes no sense to break abstraction barriers, jump into the implementation of "vertex", and place a vertex pointer called "Vertex *parent" and an integer "rank" in each the class definition of Vertex. Instead, I need some other way to access the rank/parent of a Vertex in O(1) time. How should I do this? Is there a canonical way? Do I use a hash table? How does one hash a vertex?

I suspect I can be more helpful in asking my question if I include my attempt at an implementation to get over this problem. I implemented a "hash map" that uses the address of the object as a key.

This is the implementation of "HashMap", which will key objects by their address and store a pointer to something of class val. This file is what my question focuses on.

File hashMap.h:

#include <unordered_map>

template <class keyed, class val>
class HashMap
{
public:
    HashMap(){}
    ~HashMap(){}

    long keyOf(keyed &item){ return (long) &item; }

    val* &operator[](keyed &item)
    {
        long key = keyOf(item);
        return _uomap[key];
    }

private:
    std::unordered_map<long, val*> _uomap;
};

This is a file that includes an implementation of the DisjointSets data structure. It isn't very important - I've included it just for concreteness. Notice that "_rankOf" and "_parentOf" will, in a certain sense, "simulate" data members T.rank and T.parent which may not already appear in the implementation of whatever is used for T.

File disjoint.h:

#include "hashMap.h"

template <class T>
class DisjointSets
{
public:
    DisjointSets(){}
    ~DisjointSets(){}

    void makeSet(T &elem)
    {
        int elemRank = 0;
        _parentOf[elem] = &elem;
        _rankOf[elem] = &elemRank; 
        ++_numSets;
    }

    T &findSet(T &elem)
    {
        if (_parentOf[elem] != &elem)
            _parentOf[elem] = &findSet(*_parentOf[elem]);
        return (*_parentOf[elem]);
    }

    void unify(T &elemA, T &elemB)
    {
        link(findSet(elemA), findSet(elemB));
        --_numSets;
    }

    void link(T &setA, T &setB)
    {
        if (*_rankOf[setA] < *_rankOf[setB])
            _parentOf[setA] = &setB;
        else
        {
            _parentOf[setB] = &setA;
            if (*_rankOf[setB] == *_rankOf[setA])
                ++(*_rankOf[setB]);
        }
    } 

private:
    HashMap<T, T> _parentOf;
    HashMap<T, int> _rankOf;
    int _numSets = 0;
};

In a separate file, you might want to actually use the disjoint data structure to do something. Here is an example of such a file. Note that Vertex doesn't have a rank data member or a parent data member.

File vertex.cc:

#include "disjoint.h"
#include <iostream>

using namespace std;

class Vertex
{
public:
    Vertex(int val): _val (val){}
    ~Vertex(){}

    int valOf(){ return _val; }

private:
    int _val = 0;
};

int main()
{
    //Have fun with Kruskal's algorithm or whatever
    DisjointSets<Vertex> sets;
    Vertex a(1);
    Vertex b(2);

    sets.makeSet(a);
    sets.makeSet(b);
    //etc.
    return 1;
}

This gets the job done, but I really don't like it. It seems very hacky. I have to use the address as a hash, which doesn't seem safe. I have to use pointers as the stored value of the HashMap, which isn't quite like a real data member.

Any advice is appreciated. Alternatively, if this whole approach is bad, please let me know what the better alternative is. I've been told that I shouldn't find myself in a position where I want to add a new data member without changing the original class definition - I feel I've given a good example here of where this is necessary.

\$\endgroup\$
  • 2
    \$\begingroup\$ Adding new features to existing classes in C++ is typically done by aggregation or inheritance. It's not clear to me why neither of these mechanisms is used, and not clear to me what actual problem you're trying to solve. \$\endgroup\$ – Edward Oct 7 '18 at 16:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.