• Announcements

    • khawk

      Download the Game Design and Indie Game Marketing Freebook   07/19/17

      GameDev.net and CRC Press have teamed up to bring a free ebook of content curated from top titles published by CRC Press. The freebook, Practices of Game Design & Indie Game Marketing, includes chapters from The Art of Game Design: A Book of Lenses, A Practical Guide to Indie Game Marketing, and An Architectural Approach to Level Design. The GameDev.net FreeBook is relevant to game designers, developers, and those interested in learning more about the challenges in game development. We know game development can be a tough discipline and business, so we picked several chapters from CRC Press titles that we thought would be of interest to you, the GameDev.net audience, in your journey to design, develop, and market your next game. The free ebook is available through CRC Press by clicking here. The Curated Books The Art of Game Design: A Book of Lenses, Second Edition, by Jesse Schell Presents 100+ sets of questions, or different lenses, for viewing a game’s design, encompassing diverse fields such as psychology, architecture, music, film, software engineering, theme park design, mathematics, anthropology, and more. Written by one of the world's top game designers, this book describes the deepest and most fundamental principles of game design, demonstrating how tactics used in board, card, and athletic games also work in video games. It provides practical instruction on creating world-class games that will be played again and again. View it here. A Practical Guide to Indie Game Marketing, by Joel Dreskin Marketing is an essential but too frequently overlooked or minimized component of the release plan for indie games. A Practical Guide to Indie Game Marketing provides you with the tools needed to build visibility and sell your indie games. With special focus on those developers with small budgets and limited staff and resources, this book is packed with tangible recommendations and techniques that you can put to use immediately. As a seasoned professional of the indie game arena, author Joel Dreskin gives you insight into practical, real-world experiences of marketing numerous successful games and also provides stories of the failures. View it here. An Architectural Approach to Level Design This is one of the first books to integrate architectural and spatial design theory with the field of level design. The book presents architectural techniques and theories for level designers to use in their own work. It connects architecture and level design in different ways that address the practical elements of how designers construct space and the experiential elements of how and why humans interact with this space. Throughout the text, readers learn skills for spatial layout, evoking emotion through gamespaces, and creating better levels through architectural theory. View it here. Learn more and download the ebook by clicking here. Did you know? GameDev.net and CRC Press also recently teamed up to bring GDNet+ Members up to a 20% discount on all CRC Press books. Learn more about this and other benefits here.
Sign in to follow this  
Followers 0
Cosmic314

Design recommendations for multiple map<> of objects

9 posts in this topic

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!
0

Share this post


Link to post
Share on other sites
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).
1

Share this post


Link to post
Share on other sites
[quote name='Cosmic314' timestamp='1355948909' post='5012579']
What would you recommend?
Thanks![/quote]
[b]For starters[/b], 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).


[b]Second[/b], 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.


[b]Third[/b]. 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.


[b]Fourth[/b], 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


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

Cheers
Dark Sylinc Edited by Matias Goldberg
1

Share this post


Link to post
Share on other sites
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:

[code]
const string&
DeviceB::get_device_type() { return string("B"); }
[/code]

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

[code]
IDeviceB *device = static_cast<IDeviceB *>(matching_device);
[/code]

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++.)
0

Share this post


Link to post
Share on other sites
[quote name='Cosmic314' timestamp='1355967997' post='5012668']
[code]
IDeviceB *device = static_cast<IDeviceB *>(matching_device);
[/code]

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++.)
[/quote]
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:
[code]
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 */}
}[/code]

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
1

Share this post


Link to post
Share on other sites
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[b] functionalities I provide[/b]."
You: "So you guarantee that whoever [b]is hiding[/b] behind you, can provide those functionalities aswell in [b]it's own way[/b]?"
Device: "Exactly. "

Lets go over the keywords real quickly:

1. [b]Providing functionalities[/b]
[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. [b]Hiding[/b]

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 [b]hidden [/b]behind that device.

3. Handling things [b]it's own way[/b]
[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
1

Share this post


Link to post
Share on other sites
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.
0

Share this post


Link to post
Share on other sites
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?
0

Share this post


Link to post
Share on other sites
[quote name='Álvaro' timestamp='1356021150' post='5012832']
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?
[/quote]

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): [url="http://www.stroustrup.com/new_learning.pdf"]http://www.stroustrup.com/new_learning.pdf[/url] Anyways, after reading it, it's how I ended up deciding to use it, and I find myself agreeing with Bjarne's sentiments.
0

Share this post


Link to post
Share on other sites
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.
1

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!


Register a new account

Sign in

Already have an account? Sign in here.


Sign In Now
Sign in to follow this  
Followers 0