Jump to content

  • Log In with Google      Sign In   
  • Create Account


Design recommendations for multiple map<> of objects


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
9 replies to this topic

#1 Cosmic314   Members   -  Reputation: 1168

Like
0Likes
Like

Posted 19 December 2012 - 02:28 PM

In my current C++ project I have a Device object. From this Device object I subclass a great number of devices. I store all of these devices in separate std::map objects with one map per subclass. The subclassed devices are produced by a factory. In the base class I have several routines to set various states of each device. Each device must have a unique ID upon creation. How would you implement this scenario?

Some ideas I had:

(1) Store all devices in one map<string,IDevice *>. Store type information and cast to the appropriate subclass. The main advantage here is that I maintain one master list of all devices. However, the devil on my shoulder says this practice is frowned upon because of the casting.

(2) Make a separate map for each subclass but have no centralized list. The main advantage here is that no casts are needed. A big disadvantage is that I have as many lists as I do device types. If I want to add a device I have to check against all lists to see if the device already exists.

(3) Like (2) but I have an additional map that does nothing but record existing ID names. When a device is added/removed two maps need updating. Updating two locations to maintain state could be problematic if code complexity increases. I could add an interface which wraps the action of adding/removing objects to both lists.

(4) Something like (1) and (2) combined. Have a master list of IDevice* and also maintain specific subclassed lists. If I need to perform a base class operation I just use the main device list. However, now I have two pointers and I worry about leaks and/or dangling pointers.

(5) Have some sort of nested map or multi_map structure.

I'm guessing there's a stronger solution than the above. What would you recommend?

Thanks!

Sponsor:

#2 Álvaro   Crossbones+   -  Reputation: 12473

Like
1Likes
Like

Posted 19 December 2012 - 02:47 PM

Why do you ever need to use casts? Ideally the IDevice class should provide an interface that allows all the code outside of the factory function to not have to know anything about the derived classes. You can then use (1), or some variant of it using a smart pointer (probably std::unique_ptr).

#3 Matias Goldberg   Crossbones+   -  Reputation: 3056

Like
1Likes
Like

Posted 19 December 2012 - 06:24 PM

What would you recommend?
Thanks!

For starters, try not to use a string as a key. Use a unique key or a hash (analyze whether you can predict a hash collision may happen or not under your control).


Second, what are you going to do most often? Iterate through them or find/query them? How often will you query/iterate per second (or per frame if applies).
I guess you're not going to be inserting/removing very often once you booted your application.


Third. How much is "great number devices". If that's 30 devices, a plain vector with linear search would work (and would work faster because of better cache coherence).
But if you don't iterate or look too often, it won't matter much whether you choose a vector or a map.

If you're going to handle around 1000 devices and 10 subclasses, then take in mind map's find complexity is logarithmic. Creating 10 maps of 100 devices each will result in poorer performance compared to a single map of a 1000 devices.
If you're going to have 30000 devices with 3 subclasses, it won't make much difference whether you choose 1 map, or 3 maps.


Fourth, if you're going to iterate very often through 1000s of devices per second, and will rarely insert/remove, then I'll suggest a sorted vector using std::lower_bound & std::vector::insert


Fifth, you may prefer OOP inheritance and virtual tables instead of casting to the correct derived type.

Cheers
Dark Sylinc

Edited by Matias Goldberg, 19 December 2012 - 06:24 PM.


#4 Cosmic314   Members   -  Reputation: 1168

Like
0Likes
Like

Posted 19 December 2012 - 07:46 PM

Thank you for the replies.

You gave me a lot of good ideas, Matias, for when considering performance. Eventually I plan to try different implementations to see what works best, but for now I am writing a prototype. I will definitely keep your suggestions in mind when I go to optimize.

Performance aside for a moment, let me narrow down the problem. Suppose I take suggestion (1) which is to create a vector or map of IDevice * objects. I have written the Device class such that you cannot instantiate it directly; you must subclass it to something specific. Suppose my subclasses are DeviceA, DeviceB, etc. Now I want to extract devices from the IDevice * list that are of type DeviceB. How would I do this?

My initial thought was to record type information in the subclass through a member function, something like:

const string&
DeviceB::get_device_type() { return string("B"); }

For all IDevice * objects that match it, then I'd simply do:

IDeviceB *device = static_cast<IDeviceB *>(matching_device);

I think this is a bad idea and I want to avoid it. After doing a little more research, I found the visitor pattern which seems to do what I want. A compile time check is done and there's no need to record additional information about the type of a particular object. I just need to see if I can get it to work. (Yes, I am learning C++.)

#5 Matias Goldberg   Crossbones+   -  Reputation: 3056

Like
1Likes
Like

Posted 19 December 2012 - 09:37 PM

IDeviceB *device = static_cast<IDeviceB *>(matching_device);

I think this is a bad idea and I want to avoid it. After doing a little more research, I found the visitor pattern which seems to do what I want. A compile time check is done and there's no need to record additional information about the type of a particular object. I just need to see if I can get it to work. (Yes, I am learning C++.)

The visitor pattern should do what you want.

However, again. Why would you downcast to IDeviceB?
The typical OOP approach is that you should do:
device->doYourThing();

//Declarations...
class IDevice
{
virtual void doYourThing() {} //You may want it to be pure virtual, like this:
//virtual void doYourThing() = 0; //->Pure virtual version, derived class *must* implement it.
}

class IDeviceB : IDevice
{
virtual void doYourThing() { /* Do that X something */}
}

Sure, if you are picky about performance, virtuals aren't free (but neither is the visitor pattern). But if you're still learning C++, then that's a topic for another day (when you feel you can handle it, google "data oriented design")

Finally there are rare cases (they're the exception!!!) where you may want to downcast. Particularly, I use a similar method to yours (use getType) and before the static_cast I also write "assert( dynamic_cast<IDeviceB>*myDevice )" just to double check I didn't make a mistake in getType.
But this isn't considered good practice, just last resort medicine.

By design virtuals should avoid 98% the need to downcast. While another 1.5% can be handled by storing those derived types separately so you never need to downcast. And that last 0.5% is the one you didn't see when you were planning, and may force you to choose between downcasting or refactor.

But don't overdo virtuals, in x86 they're very cheap, but if you're working for phones & consoles, they can get expensive (i.e. don't make a function virtual "just in case")

Edited by Matias Goldberg, 19 December 2012 - 09:39 PM.


#6 Mercurialol   Members   -  Reputation: 221

Like
1Likes
Like

Posted 19 December 2012 - 10:33 PM

Matrias is right. Consider this:

You: "Hey device, what can you do?"
Device: "I can do function1(), tellMeWhoYouAre() and veryComplicatedFunction()"
You: "But who actually are you? Are you a IDeviceA? IDeviceB?"
Device: "That is not of your concern. I told you what functionalities I provide."
You: "So you guarantee that whoever is hiding behind you, can provide those functionalities aswell in it's own way?"
Device: "Exactly. "

Lets go over the keywords real quickly:

1. Providing functionalities
[source lang="cpp"]class Device{public: Device(); ~Device(); // virtual basically means that subclasses can override this function // =0 means this function has no implementation making this class an abstract class virtual void function1()= 0; virtual std::string tellMeWhoYouAre(){ return "Device"; } void veryComplicatedFunction(){ // complicated stuff }};[/source]

When you look at device class you know what functionalities it, or it's subclasses provides.

2. Hiding

As polymorphism.
[source lang="cpp"]Device* device= new DeviceImplementationA();device->function1();[/source]

When calling function1, you don't generally care and most of the time you don't know if DeviceImplementation1 or DeviceImplementationX is hidden behind that device.

3. Handling things it's own way
[source lang="cpp"]class DeviceImplementation1 : public Device{public: DeviceImplementation1(); ~DeviceImplementation1(); // no '=0' since we have an implementation here virtual void function1(){ // do Implementation1 specific stuff } // again, tellMeWhoYouAre() needs a specific implementation virtual std::string tellMeWhoYouAre(){ return "DeviceImplementation1"; }};[/source]

Edited by Mercurialol, 20 December 2012 - 12:00 AM.


#7 Cosmic314   Members   -  Reputation: 1168

Like
0Likes
Like

Posted 20 December 2012 - 10:26 AM

These examples are helpful. I do understand what you're both saying about encapsulation and polymorphism and, in fact, I do these very things with my device inheritance hierarchy. That is, I let my virtual chain choose the appropriate function.

However, the problem is more nuanced. Consider that certain of my subclassed items add functionality to some of the devices through new methods. Suppose DeviceA simply overrides the base class through the virtual mechanism. Now assume that DeviceB adds a new function that DeviceA and the base class do not have: NewFunctionNoOtherDevicesHave(). If I use an IDevice* interface and call NewFunctionNoOtherDevicesHave() on all Devices then I will throw a runtime exception. In other words my collection of vector<IDevice *> is not homogeneous. I want to be able to select a certain subset of my IDevice* objects that contain this functionality and filter out the rest. How do I do that?

One solution is to lookup runtime type, whether through RTTI or through an interface that identifies the object's class. With that knowledge I then cast to the correct subclass interface. But I feel like this is a bad idea and against the spirit of object oriented programming (ie have the language do the lifting when it comes to types).

Without some explicit mechanism to identify the type, I'm having trouble determining just how I can get C++ to do just this.

#8 Álvaro   Crossbones+   -  Reputation: 12473

Like
0Likes
Like

Posted 20 December 2012 - 10:32 AM

It's hard to have a meaningful conversation about software design without actually describing what we are talking about in detail. What do these devices represent? What are some examples of subclasses? What kinds of operations are you going to perform on all devices, and what kinds of operations only on certain subtypes? Which subtypes?

#9 Cosmic314   Members   -  Reputation: 1168

Like
0Likes
Like

Posted 20 December 2012 - 11:14 AM

It's hard to have a meaningful conversation about software design without actually describing what we are talking about in detail. What do these devices represent? What are some examples of subclasses? What kinds of operations are you going to perform on all devices, and what kinds of operations only on certain subtypes? Which subtypes?


I am writing a distributed service that periodically monitors and evaluates the status of compute resources. It also randomly generates code to stress test these devices. Attached to the processors are a variety of monitors, electrical clock generators, power supplies, temperature controls, and a variety of other equipment. I want to model all of these things as "Devices" because common to all of them is the need for a specific host, an owner / current user, and permissions.

However, as you can see, a clock generator is not a power supply nor a temperature control, thus the need for differentiation.

I was hoping to maintain all of these devices on one list. If I could it would make the design a lot simpler. However, I'm starting to suspect that these devices need to be maintained on separate lists and have one list (or class) which handles the base functions of the devices.

I hope this adequately explains the situation.

For history's sake, I originally wrote a good portion of this software in C but then quickly ran into a situation where it became more and more painful to add new features. I had some prior C++ experience and felt it would better suit maintenance and extension needs that would surely arise. I spent the past few months learning as much as I could about it and software development in general: interface based programming, design patterns, basic C++ knowledge, test driven development. I am advancing at a steady pace but have much to learn. (Would it be useful to share my learning progress on the forums somewhere?)

When I was deciding to choose C++ I was very hesitant, in large part by the responses in this forum. Many feel C++ shouldn't be tackled right away so I was full of self-doubt. Then I ran across this paper (from the author of C++ no less, Bjarne Stroustrup): http://www.stroustrup.com/new_learning.pdf Anyways, after reading it, it's how I ended up deciding to use it, and I find myself agreeing with Bjarne's sentiments.

#10 Álvaro   Crossbones+   -  Reputation: 12473

Like
1Likes
Like

Posted 20 December 2012 - 11:44 AM

I think keeping separate containers makes much more sense in your situation, unless looping over all devices is going to be a common operation. Having a common base class for the devices as a way to avoid code duplication seems OK to me, although it's not the way I normally do things.

When I look at a host, an owner and permissions, I don't think of those things together as forming a device, but perhaps as describing the access to a device. Perhaps it can be called AccessInfo, or something like that (although I don't love using "Info" in my class names because it's easy to abuse), and then each device type will have a member of that type.

If your Device base class can provide some more meaningful functionality (say, you can query its status, or something like that), then I would prefer to model it the way you have done it.

But it looks like you have a pretty good handle on the situation and a lot of these things come down to personal style.




Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS