Jump to content
  • Advertisement
Sign in to follow this  
True_Krogoth

My object list organization

This topic is 1216 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Advertisement
Is there any particular reason you're set on using a linked list and recursion to solve this problem? It seems to me like you're overcomplicating this and maybe trying to use C++ like you'd use a functional language like Haskell or Lisp. Why not simply stick your components in an array or a vector and then iterating through them with a loop? C++ is not Haskell. smile.png
 
// note that TComponent doesn't need to know anything about any of the other components
class TComponent {
public:
  // note that this doesn't need to be virtual, anymore, though it can call virtual functions internally
  void Update();

  //...
};

// here's our update function - note that it takes a vector (a dynamic array) of TComponents
void UpdateAll(std::vector<TComponent>& components) {
   for (auto& component : components) {
       component.Update();
   }
}
If you do things the way I'm suggesting, you avoid:
- using a solution that is not idiomatic in C++
- the complexity associated with using a linked list to represent your component list (pretty much all the code in your post is dealing with this)
- the performance hit associated with using a linked list (linked lists tend to put nodes all over memory, which can be bad for cache performance)
- the performance hit associated with recursion (due to pushing stack frames around, and potential stack overflows if your container is too large, though both of these problems might be optimized away by a sufficiently aggressive compiler Edited by Oberon_Command

Share this post


Link to post
Share on other sites

I am sorry, I had to remove my OP until I take a better thought.

The concept had 1 toooooo big flaw to handle. (Good I removed it fast, people would laugh)

 

Yeah, I know that. I just love recursion .)))

 

Edit:

And recursion isn't slower afaik, due to tail call optimization, is it?

Edited by True_Krogoth

Share this post


Link to post
Share on other sites

I am sorry, I had to remove my OP until I take a better thought.
The concept had 1 toooooo big flaw to handle. (Good I removed it fast, people would laugh)


Please don't do that. That is not a valid reason to remove your post and I don't anticipate that the mods will comply with your request. Nobody will laugh at you and other posters (mainly lurkers) might learn something. Trying to get a post you feel reflects badly on you will only give others the impression that you care over-much about your reputation. smile.png

Being wrong on a forum is not bad, it's a learning opportunity.
 

Edit:
And recursion isn't slower afaik, due to tail call optimization, is it?


I'm not the best person to ask, but your compiler might not do tail call optimization in some cases. Could be wrong about that, though, this does seem like a case where tail-call optimization would be pretty straightforward.

Either way, your solution isn't particularly good from a object-oriented design perspective, either. Again, the downside to an intrusive list (what this pattern is called) is that nodes need to know about other nodes in order for the list to function. That makes the node itself more complex and violates the single-responsibility principle. On a simple code level, it makes your code much less clear, too - the for each loop in my example is not only shorter and less complex, but it's very clear from those three lines of code what I'm trying to do to anyone reading it.

C++ is usually treated as an imperative object-oriented language. Patterns from functional languages are gradually becoming more and more ingrained in the language and culture of C++, but I doubt you'll find many a C++ practitioner who would implement your original solution in production code. If you're coming from a functional programming language, you will find that you need to re-frame your approach to common problems in an imperative mindset to write concise C++ code, just as a programmer coming from C++ will need to re-frame his/her approach when learning Haskell or Erlang or Scheme. Edited by Oberon_Command

Share this post


Link to post
Share on other sites

Hey, so after looking at your code, I think the best method would be to have a "world" class hold an array(like std::vector) of objects for updating. Objects should not need to know about all of the objects that are in the world through a linked list. With a "world" class, it also makes it easier to update different components at different times, remove components, and allow components to only worry about their code. This can definitely help reduce bugs later down the road, i.e forgetting to call a Next->Update() function after overriding a component.

Share this post


Link to post
Share on other sites

Oberon_Command, thank you for wide answer. :]

 

They say, GCC does optimization even for mutual recursion, converting recursion into loop.

 

I understand, this is out of C++ style, as I don't even use much containers!

 

But I like my approach and do not wanna abandon it.

 

I don't like an idea of something over objects, like a list other than intrusive.

My object functionality lies in the object itself, or to be concrete, in its nature. This is what I am trying to describe with my code.

 

For example, there is a plane flying. In this case I define plane object as a plane itself and a close air around, that is dynamically changing part of the object. So air resistance influence is a part of plane class.

Easier to understand with a cat that meow meow. I do not define its sound as a part of some Air Vibration class, or some Molecular Forces, or just Physics. But we know that cat couldn't meow without physics. It can try to meow, but it's not exclusively its action, if we do sharp distinction between cat and surrounding physics. Still, the cat class has Meow method, and it's understandable.

 

Same concept I apply to object update. They update themselves, as momentarily their definition includes all updating factors applied to them. They also delete themselves, though it is not very popular method.

 

Recursion is much closer to this approach than loop and exists only in source code.

 

Otherwise I would have to manipulate with iterators rather than pointers. What's the profit?

I would not use std list functionality other than loop. I also add objects in my manner (as it was said, according to 'order index' parameter), and I do not sort anything.

Edited by True_Krogoth

Share this post


Link to post
Share on other sites

Hey, so after looking at your code, I think the best method would be to have a "world" class hold an array(like std::vector) of objects for updating. Objects should not need to know about all of the objects that are in the world through a linked list. With a "world" class, it also makes it easier to update different components at different times, remove components, and allow components to only worry about their code. This can definitely help reduce bugs later down the road, i.e forgetting to call a Next->Update() function after overriding a component.

Indeed, I should make those full private.

 

Child components don't need to worry about the list. TObject performs everything itself, and you don't need to put Next->Update() in overriding function. Next->Update() is called by loopUpdate() that is not virtual, but explicitly Object's own and performs call of this particular object's update and the next one's.

Edited by True_Krogoth

Share this post


Link to post
Share on other sites

And I still reworked it with std::list!

https://github.com/trueKrogoth/keng/blob/master/keng/main/obj_basic_types.cpp

No more intrusive lists and recursion.

 

+ Replaced array with vector

+ Removed Object, reworked Component as super-class and Basis now :: Component

 

Emmm...

            component->iterator = component_list.insert(++order_component[i]->iterator--, *component);

Are these pre-post increments common thing when you work with iterators?

Edited by True_Krogoth

Share this post


Link to post
Share on other sites

Basis is the Component that is designed to build other Components.
All Components created are built on some Basis, and they all have pointers to it. Basis, on the other hand, has pointers to some Components that are last Components of certain 'order index', according to which Components are put to the list. For example, Active Window is put over Inactive Window, but still behind Cursor.
Thus Basis is the beginning element of its own Component list,
meanwhile it is just an ordinary Component in its parent Basis' list (if it's not the Null Basis).
Technically speaking, Basis is present in 2 lists at same time. (Yeah, I am gonna make some mystery from there)
 
And a few more about Null Basis, that it's the thing from which the World starts updating like this:
NullBasis->update();

This is not really mystical; instead it is so common that it has a name: The Composite Pattern.

 

Letting the question about using a std::xyz structure aside, this ...

QUESTION:
How to organize it? (Especially that 'double presence')

… and this ...

But the problems come as
the last Component must not touch its Basis upon destroying.
How to get it not over-complicating anything?

… is simple to answer: Do not use recursion. The functionality of deleting neighbors is misplaced when placed within the child nodes. Instead let the parent node delete the first child ode as long as child nodes are available.

 

In other words: The parent node is responsible for its child nodes!

Edited by haegarr

Share this post


Link to post
Share on other sites

My object functionality lies in the object itself, or to be concrete, in its nature. This is what I am trying to describe with my code.


But I wouldn't say that it's in the nature of the object to be in a list. Where is this assumption coming from? What if you want some objects to be standalone?
 

For example, there is a plane flying. In this case I define plane object as a plane itself and a close air around, that is dynamically changing part of the object. So air resistance influence is a part of plane class.


But the air isn't a part of the plane, it's a part of the atmosphere. So you could have a plane object that simply defines what the plane is and have a separate physics subsystem handle the air resistance based on some atmosphere object that describes the density of the air at the plane's altitude.
 

Easier to understand with a cat that meow meow. I do not define its sound as a part of some Air Vibration class, or some Molecular Forces, or just Physics. But we know that cat couldn't meow without physics. It can try to meow, but it's not exclusively its action, if we do sharp distinction between cat and surrounding physics. Still, the cat class has Meow method, and it's understandable.


No, the way I'd do this is to have an object that is solely responsible for making sounds and the cat's meow() method would ask the sound object to make a sound at the cat's location. The cat doesn't need to know what a sound actually is, it only needs to know how to start making a sound.
 

Otherwise I would have to manipulate with iterators rather than pointers. What's the profit?


Not really. Just don't have TComponents know about the collection they're a part of at all. Let the collection object handle it. Problem solved. smile.png

I have some more critique on your code on GitHub, by the way. First of all, why are you set on having components being able to remove themselves? This is the source of a lot of your remaining complexity. If you make adding and removing components the sole responsibility of TBasis, then:
- TComponents don't need to remember where they are in the list
- TComponent doesn't need to depend on the sub-class TBasis, both reducing coupling and making the class smaller
- Tcomponent doesn't need to have virtual insert/remove functions - these should only be on TBasis, and don't need to be virtual anymore

Secondly, why the use of std::list, if you're using a separate container (and a vector, to boot!) to store the ordering of the components? Just use either a single sorted container, or at least use a vector for the container that you don't need to be sorted. Remember, insertion on the end of a vector is amortized O(1) - if the container's underlying array storage is large enough to hold the new element, it's a simple as a pointer increment. If you don't care about the order of the components, removal is ALSO O(1) - just swap the element at the end of the vector with the one you want to remove, then call pop_back(). Also, then TComponents can store an integer index into their containing vector instead of having to store an iterator, which might get invalidated when the vector grows or is sorted.

Thirdly, unless you're using an old compiler, you should be able to use C++11's foreach loops, eg:
// what you have now
for (std::list<TComponent>::iterator i = component_list.begin(); i != component_list.end(); i++) 
  i->update(); 

// what you could have - note that we don't need an iterator, so the code is easier to read
for (TComponent& component : component_list)
  component.update();
Finally, what is the __dummy argument to all the constructors for? It doesn't look like it does anything to me.
 

Are these pre-post increments common thing when you work with iterators?


No, that's undefined behaviour - the order of operations is undefined so your compiler could do anything there. Do NOT do what you're doing now. Put the increment/decrements in separate statements both for clarity and to avoid undefined behaviour. Edited by Oberon_Command

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!