5

I have often encountered a situation in which users of a program (not necessarily human, just an external agent) need to be able to reference objects of a class with a certain "external" identifier, in order to create, modify and delete them. This identifier could be an integer, for example, or a string. We'll suppose it's a string for the sake of the argument.

Where should these IDs be stored?

Let me clarify. In order for the program to "link" a certain identifier to the corresponding actual object, it needs to have some sort of associative container with IDs as keys and their corresponding objects as values, providing thus logarithmic access time.

Now, suppose some method of this class needs access to the identifier. In this case, should the identifier be a field of the class? This seems like the obvious solution. But the problem is that now the identifiers are duplicated: as keys in the associative container, and as fields in each instance. That would imply double the storage necessities and duplicate "management tasks" (i.e., when adding a new object to the associative container, one would need to specify the identifier as both key and field).

Is there a general way to overcome this problem? (Or am I fussing over nothing?) One alternative would be to have the associative container keep references to the ID field as keys. But I don't know how to do that.

For example, in C++, consider the class

class MyClass {
public:
    std::string ID;
    MyClass(string id) : ID(id) {}
}

Then the straightforward approach would be to store a std::map<std::string, MyClass>. I tried to make use of std::reference_wrapper to store references to the IDs, but then the order of the map doesn't work since operator< isn't defined on reference_wrappers:

int main() {
    std::map<reference_wrapper<std::string>, MyClass> myInstances; // error
    MyClass obj("Bob");
    myInstances.insert({obj.ID, obj});
}

Is there a way to do this? Or is it unnecessarily complicated?


In Python, I believe this

class MyClass:
    def __init__(self, ID: str):
        self.ID = ID


myInstances = {}
obj = MyClass("Bob")
myInstances[obj.ID] = obj

would work, since both the myInstances[obj.ID] identifier (as in Python object identifier) and the self.ID identifier would point to the same string (so no extra memory would be needed).

  • How is the body of your question related to human-readable identifiers? – Kasper van den Berg Mar 8 at 19:47
  • 1
    "(so no extra memory would be needed)" Just to be clear, you are adding an additional reference which, in CPython, appears to be the word size of the machine. So on a 64 bit machine, you are adding 8-bytes per reference. I'm pretty certain the overhead in C++ is similar. – JimmyJames Mar 8 at 21:09
  • @KaspervandenBerg Fair point; I've changed the title. – Anakhand Mar 10 at 11:23
4

Is there a general way to overcome this problem? (Or am I fussing over nothing?)

Yes, you are too concerned about this.

So you are duplicating data. As long as you have enough RAM available, this isn't a big deal. Keep a copy of the Ids as keys within the collection, and keep them as fields on the objects themselves.

Optimizations like this should only be entertained when you have measured a performance issue related to CPU usage, or the capacity of available disk or RAM storage — and the key here is a measured performance problem.

This sounds like premature optimization. Go for the solution that is easiest to implement and maintain.

  • 1
    +1 Just want to point out that the 'duplicate' data here is just a reference, at least in the Python example. There is surely lower-hanging fruit if you want to reduce your memory usage. – JimmyJames Mar 8 at 18:10

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.