- Forum
- General C++ Programming
- Best way to find unique combinations of
Best way to find unique combinations of different objects
I'm going to simplify the problem I'm facing down to an abstraction while describing it to avoid confusing the issue with unnecessary details.
Right now I have three basic structs, each of which contain a different type of data, which I'll call BaseA, BaseB, and BaseC. I have a master list of all of those that I'm using. The master list for each of these is potentially hundreds of thousands of items long, and their lengths do not necessarily match. Then there's another struct, which I'll call Brick, which is essentially just a pointer to a single BaseA, BaseB, and BaseC in their respective master lists. Finally, I have the class House, which contains a list of Bricks. The list is of arbitrary length, but I can reasonably expect that it will never be longer than 10. Finally, I have a master list of every House. This list is potentially hundreds of thousands of items long as well.
Different Bricks can use the same BaseA, BaseB, or BaseC. Different Houses can currently use Bricks made of the exact same BaseA, BaseB, and BaseC components as another Brick in another House (but not another Brick in the same House), but they'd still be stored separately as unique Bricks. I'd like to change that. What I'd like to do is make a master list of Bricks, and convert all of my Houses in my master list into a new type of House, let's call it a Shack, that just contains a list of indices into the master Brick list.
The obvious solution is to make an empty list of Shacks and an empty list of Bricks. Go through each House in the list of Houses, and make a new Shack. Go through the list of each Brick in that House, and compare it against every Brick in the master Brick list. If there's a match, put the index to the matching Brick in the Shack. If there's no match, put that Brick at the end of the Brick list and put the index to that in the Shack. When the House is out of Bricks, put the Shack in the Shack list, move to the next House, and make another new Shack. However, I forsee this taking a long, long time to complete.
Is there a better way? Maybe I can have each BaseA, BaseB, and BaseC build a list of Bricks using them as I'm first creating the Houses? I'm not sure, but I've been staring at it too long now and can't think of how to best proceed.
Right now I have three basic structs, each of which contain a different type of data, which I'll call BaseA, BaseB, and BaseC. I have a master list of all of those that I'm using. The master list for each of these is potentially hundreds of thousands of items long, and their lengths do not necessarily match. Then there's another struct, which I'll call Brick, which is essentially just a pointer to a single BaseA, BaseB, and BaseC in their respective master lists. Finally, I have the class House, which contains a list of Bricks. The list is of arbitrary length, but I can reasonably expect that it will never be longer than 10. Finally, I have a master list of every House. This list is potentially hundreds of thousands of items long as well.
Different Bricks can use the same BaseA, BaseB, or BaseC. Different Houses can currently use Bricks made of the exact same BaseA, BaseB, and BaseC components as another Brick in another House (but not another Brick in the same House), but they'd still be stored separately as unique Bricks. I'd like to change that. What I'd like to do is make a master list of Bricks, and convert all of my Houses in my master list into a new type of House, let's call it a Shack, that just contains a list of indices into the master Brick list.
The obvious solution is to make an empty list of Shacks and an empty list of Bricks. Go through each House in the list of Houses, and make a new Shack. Go through the list of each Brick in that House, and compare it against every Brick in the master Brick list. If there's a match, put the index to the matching Brick in the Shack. If there's no match, put that Brick at the end of the Brick list and put the index to that in the Shack. When the House is out of Bricks, put the Shack in the Shack list, move to the next House, and make another new Shack. However, I forsee this taking a long, long time to complete.
Is there a better way? Maybe I can have each BaseA, BaseB, and BaseC build a list of Bricks using them as I'm first creating the Houses? I'm not sure, but I've been staring at it too long now and can't think of how to best proceed.
First, the 'easy' way out for a small program/problem..
One way is to have self-aware types. That is, you have a generic type that has the attributes you need (eg cost, color, model number, whatever data) and an enum or something that tells you what it is. Bam. Now your house has a list of stuff (a vector or list or whatever type seems appropriate). Sort it by type... you can look at how many bricks of what type it has, how much copper wire, how many slabs of sheetrock, what floor tiles it uses, blah blah blah. This is the derpy no nonsense way to do it without excessive inheritance and polymorphism tricks. It works great for simple problems, but you eventually reach a point where it does not work for whatever reason (the data types start to split, for example, with a brick having x,y, and z attributes and a water pipe having m,n, and o attributes, so now the mega class needs x,y,z AND m,n,o.. gets ugly).
You can abstract that idea one level with pointers. You can store a bunch of pointers + the type pointed to, and make a vector or list or whatever of THOSE. This will let you store anything alongside anything, so long as you bother to check types everywhere. This has its own problems, but here again its a simple design for a simple problem that works 'to a point' and then begins to not work as things get too complicated.
If the above is insufficient, you will probably want some sort of inheritance, and the design for that takes time and thought up front to cover all the things you need to do for YOUR project. This is "the right way to do it" but you will have to invest more time thinking and designing the hierarchy of your classes. The upside is that the code that uses the classes is simpler and cleaner, less bug prone and if done right scales to add features later. I don't think we have enough info to help with this design yet. (?).
One way is to have self-aware types. That is, you have a generic type that has the attributes you need (eg cost, color, model number, whatever data) and an enum or something that tells you what it is. Bam. Now your house has a list of stuff (a vector or list or whatever type seems appropriate). Sort it by type... you can look at how many bricks of what type it has, how much copper wire, how many slabs of sheetrock, what floor tiles it uses, blah blah blah. This is the derpy no nonsense way to do it without excessive inheritance and polymorphism tricks. It works great for simple problems, but you eventually reach a point where it does not work for whatever reason (the data types start to split, for example, with a brick having x,y, and z attributes and a water pipe having m,n, and o attributes, so now the mega class needs x,y,z AND m,n,o.. gets ugly).
You can abstract that idea one level with pointers. You can store a bunch of pointers + the type pointed to, and make a vector or list or whatever of THOSE. This will let you store anything alongside anything, so long as you bother to check types everywhere. This has its own problems, but here again its a simple design for a simple problem that works 'to a point' and then begins to not work as things get too complicated.
If the above is insufficient, you will probably want some sort of inheritance, and the design for that takes time and thought up front to cover all the things you need to do for YOUR project. This is "the right way to do it" but you will have to invest more time thinking and designing the hierarchy of your classes. The upside is that the code that uses the classes is simpler and cleaner, less bug prone and if done right scales to add features later. I don't think we have enough info to help with this design yet. (?).
Last edited on
I don't think that giving advice like that is useful for such an abstract problem statement. Elize has to be much more specific if he wants a useful answer.
Sets and maps are collection types designed to manage stuff that is reusable.
A std::shared_ptr<> is useful for shared dynamic objects, and can be combined with sets and maps.
Good luck!
Sets and maps are collection types designed to manage stuff that is reusable.
A std::shared_ptr<> is useful for shared dynamic objects, and can be combined with sets and maps.
Good luck!
Topic archived. No new replies allowed.