cpp Linked List

[tjheldna]

Hi All,

 

This is my first post so be gentle =). I've been quietly working on Leadwerks for a few weeks now and have managed to source out what I need from the forums with a great deal of success, however I do have a few questions and here is my first..

 

So my first question is is there some kind of in built linked list feature that I can use in cpp? If not what would be recommended to use? I'll be using it to store groups of entities, inventory etc.

 

Many Thanks!

[Roland]

#include <list>
#include <iostream>
using namespace std;
int main()
{
  list<int>  myList;
  myList.push_back( 10 );
  myList.push_back( 11 );
  for( list<int>::iterator it = myList.begin();
	    it  != myList.end(); it++ )
  {
		  cout <<  *it << endl;
  }
}

[TheoLogic]

First question, do you require a linked-list, or a dynamic array? In my experience, std::vector covers 90% of the container use cases.

List: http://www.cplusplus.com/reference/stl/list/

Vector: http://www.cplusplus.com/reference/stl/vector/

 

Next some remarks on Roland's code:

for(auto it(myList.begin()); it  != myList.end(); ++it)
{
  cout <<  *it << endl;
}

1. Use auto to define iterator types (if you have a C++11 enable compiler). Saves you time, and you can change the container type as you like and don't break your code.

2. Use '++'-like prefix, especially for iterators. http://thunderguy.com/semicolon/2002/08/13/prefer-prefix-operators-over-postfix/

[Josh]

Lists should be used if objects will be randomly removed from the container.

[Roland]

First question, do you require a linked-list, or a dynamic array? In my experience, std::vector covers 90% of the container use cases.

List: http://www.cplusplus...rence/stl/list/

Vector: http://www.cplusplus...nce/stl/vector/

 

Next some remarks on Roland's code:

for(auto it(myList.begin()); it  != myList.end(); ++it)
{
  cout <<  *it << endl;
}

1. Use auto to define iterator types (if you have a C++11 enable compiler). Saves you time, and you can change the container type as you like and don't break your code.

2. Use '++'-like prefix, especially for iterators. http://thunderguy.co...s-over-postfix/

 

Good comments.

[Brent Taylor]

Lists should be used if objects will be randomly removed from the container.

 

Or if you don't know the length of the container ahead of time. The last thing you want is lag spike when your data is being copied due to your array or std::vector being re-sized. Assuming your data being housed is large enough to be an issue of course.

[TheoLogic]

Lists should be used if objects will be randomly removed from the container.

Why would that be? Just one example how you can handle it:

for(auto it(myVector.begin()); it != myVector.end(); )
{
   if(must_remove_this_element)
   {
    myVector.erase(it++);
   }
   else ...
}

 

 

Or if you don't know the length of the container ahead of time. The last thing you want is lag spike when your data is being copied due to your array or std::vector being re-sized. Assuming your data being housed is large enough to be an issue of course.

std::vector can reserve capacity, so knowing the maximum number of elements can indeed be a nice thing. However, with move semantics you are able to just move elements on resizing. STL has been modified to support this, so std::vector<std::string> for example will not copy on reallocation, but move. You can write your own move constructor and assignment operator if this is your bottleneck.

[Brent Taylor]

However, with move semantics you are able to just move elements on resizing. STL has been modified to support this, so std::vector<std::string> for example will not copy on reallocation, but move. You can write your own move constructor and assignment operator if this is your bottleneck.

 

Is this new in C++11? I've never come across this before. Either I missed it or it's new. Either way, I'm thankful for the info. Very useful.

 

----

Resource on move constructor: http://msdn.microsof...y/dd293665.aspx

 

EDIT: After a quick google search, it appears it is indeed a C++11 feature.

[TheoLogic]

Yep, indeed a C++11 feature. Finally a way to express temporaries!

 

EDIT: Have an article on rvalue references and move semantics for the interested: http://www.benoitroosens.com/articles/rvalue-references-and-move-semantics

[Josh]

A vector is a contiguous block of memory. If you remove an element in the middle of it, everything after that element has to be copied to where the element's position was. If you add an element at the end of the vector and it exceeds the size of the memory allocated for that vector, a new block of memory has to be requested, and the entire contents of the container copied to it.

 

Linked lists have a next and previous pointer for each element. When an element is removed, the program just has to update the memory pointers of the previous and next elements to point to each other, so insertion and removal is fast.

 

I almost never use vectors.

[TheoLogic]

A vector is a contiguous block of memory. If you remove an element in the middle of it, everything after that element has to be copied to where the element's position was. If you add an element at the end of the vector and it exceeds the size of the memory allocated for that vector, a new block of memory has to be requested, and the entire contents of the container copied to it.

 

Linked lists have a next and previous pointer for each element. When an element is removed, the program just has to update the memory pointers of the previous and next elements to point to each other, so insertion and removal is fast.

 

I almost never use vectors.

 

Oh boy (going off topic).

Iterating over vectors is faster as over a list. List is node based and vector is a contiguous blocks of memory, which the CPU loves... That's also the reason that C# containers are slower as C++ containers, in C# all (except arrays) are node based. And be honest, what do you use the most? Inserting and removing or iterating?

* render all items

* update all items

Simple examples, this is where you need the performance! Not in that rare case where you need to add or remove for example, this could be done during loading! And even most of the time if you require adding, vector push_back is as fast as list push_back.

 

And OK, you have a case where you have both: often iterate and often remove in the middle for example. Use move semantics!

 

Sorry Josh, but you need to work on your C++ skills.

* Using std::map (red-black binary tree) for entity management? Use objects, or at least std::unordered_map (C++11 hash map) if you really, really, really want to use an ID

* Using std::list where you want std::vector

* Public datamembers, just wtf. Encapsulation my friend!

[Josh]

Iterating over vectors is faster as over a list. List is node based and vector is a contiguous blocks of memory, which the CPU loves... That's also the reason that C# containers are slower as C++ containers, in C# all (except arrays) are node based. And be honest, what do you use the most? Inserting and removing or iterating?

It doesn't matter, the vector won't scale well when the numbers get big. If you have 10,000 entities, this can result in 40,000 bytes being allocated or copied every single time you create or delete a single entity. The list will always add and remove elements at the same speed. The iteration speed of both will increase linearly with the number of elements.

 

When designing systems you want predictable performance and scalability. Sacrificing scalability to gain a minute performance increase (in the lightweight scenarios where it isn't even needed) is a bad idea.

 

Sorry Josh, but you need to work on your C++ skills.

* Using std::map (red-black binary tree) for entity management? Use objects, or at least std::unordered_map (C++11 hash map) if you really, really, really want to use an ID

What? Who said anything about maps?

 

* Public datamembers, just wtf. Encapsulation my friend!

I like being able to access members. It's simple and convenient. It would be silly to call Entity::GetPosition() and allocate a new Vec3 object every time I need to perform some math on an entity, when I can just access the member directly. If you don't like it, don't use them, because there is a getter and setter for anything you need to access.

[Canardia]

There's 3 bad things about setting object attributes directly:

1) some attributes might need additional actions also, which can be done only in a setter method

2) some attribute names might change, but the setter name will almost never change

3) the data structure of attributes might change, but the setter parameter will complain about incompatible datatypes

Besides, the setter can be a operator=() for many attributes, so you won't even notice that you are using a setter.

[Josh]

There's 3 bad things about setting object attributes directly:

1) some attributes might need additional actions also, which can be done only in a setter method

2) some attribute names might change, but the setter name will almost never change

3) the data structure of attributes might change, but the setter parameter will complain about incompatible datatypes

Besides, the setter can be a operator=(), so you won't even notice that you are using a setter.

I don't recommend setting members directly. For example, changing the position member of an entity would not have the intended result, because the 4x4 matrix and other things have to be updated. Members generally should be treated as read-only attributes.

 

For that reason, you will never be expected to rely on members. If you want simpler code and faster performance in intensive routines, you can read them. Any members we document will be considered "fixed" and won't change. Don't mess around with anything that's not documented, because that could be subject to change.

 

Members also gives you a little more power. For example, Material::GetTexture(const int& index=0) increments the refcount of the texture and allocates a new handle that has to be deleted (so you can safely use a texture without worrying about it being automatically deleted when the material is deleted), but you can avoid this by just reading the member with material->texture[0].

[Rick]

Will all of this be exposed through Lua as well because if not functionality between Lua and the other languages will again be different and offer possible differenent capabilities, which would be bad. ie. there might be some tricks that someone can do by accessing these variables directly that can't be done in Lua unless the variables are exposed directly as well.

[Josh]

Will all of this be exposed through Lua as well because if not functionality between Lua and the other languages will again be different and offer possible differenent capabilities, which would be bad. ie. there might be some tricks that someone can do by accessing these variables directly that can't be done in Lua unless the variables are exposed directly as well.

I have some members exposed in Lua, but I would not ever use them in example programs in the documentation. I could see an argument for not having them exposed at all in Lua, since they are a low-level hardcore C++ feature for writing intensive routines.

[Canardia]

At least structure attributes could be exposed to Lua, so you could code have which looks like if you would access the object's attributes directly:

x1=cube1:Position().x;

But actually you would be just accessing a vec3's x attribute, which is a copy of cube1's position, since it's returned by the Position() method.

[Josh]

At least structure attributes could be exposed to Lua, so you could code have which looks like if you would access the object's attributes directly:

x1=cube1:Position().x;

You would use "x1=cube1:GetPosition().x" in that situation. Of course, even better would be this:

position = cube1:GetPosition()

 

By the way, there is no point in the engine where we ever iterate through the list of all entities. It's always broken down into the scene octree.

[Canardia]

Although both would be a bit inefficient, if you only need the x coordinate. So a x1=cube1:GetPositionx() would be more optimal.

[Josh]

Although both would be a bit inefficient, if you only need the x coordinate. So a x1=cube1:GetPositionx() would be more optimal.

That's a situation where calling "x1 = cube1.position.x" seems the simplest to me, and would't require allocation of a new Vec3 and Lua table.

[Canardia]

But if the user then does cube1.rotation.x=45, it wouldn't work if the rotation is actually a mat4 internally?

[Josh]

But if the user then does cube1.rotation.x=45, it wouldn't work if the rotation is actually a mat4 internally?

Correct, that would cause unpredictable results, which is why the "correct" way I will always recommend is Get/SetRotation(). C#'s solution for this kind of behavior is one nice thing about that language.

[Canardia]

So my cube1:SetRotationx(45) would still work, and the same of course with position to keep it consistent.

In C++ using operator=() and operator(), you could still do:

cube1.Rotationx=45 and x1=cube1.Rotationx and it would internally do the mat4 tricks.

Not sure if Lua can do that, but I faintly remember that it could.

[Josh]

So my cube1:SetRotationx(45) would still work, and the same of course with position to keep it consistent.

Correct. That is the usage the documentation will always describe. Power users may want a little more, but they're generally smart enough to not hurt themselves.

[TheoLogic]

It doesn't matter, the vector won't scale well when the numbers get big. If you have 10,000 entities, this can result in 40,000 bytes being allocated or copied every single time you create or delete a single entity. The list will always add and remove elements at the same speed. The iteration speed of both will increase linearly with the number of elements.

 

When designing systems you want predictable performance and scalability. Sacrificing scalability to gain a minute performance increase (in the lightweight scenarios where it isn't even needed) is a bad idea.

 

 

What? Who said anything about maps?

 

 

I like being able to access members. It's simple and convenient. It would be silly to call Entity::GetPosition() and allocate a new Vec3 object every time I need to perform some math on an entity, when I can just access the member directly. If you don't like it, don't use them, because there is a getter and setter for anything you need to access.

 

You should really read this book: http://www.amazon.co...s/dp/0321113586

Everything you are stating here will gently be countered in 101 rules by Herb Sutter, C++ ISO chairman, and Andrei Alexandrescu. 2 veteran C++ developers! You are burning yourself to the very things they are warning about.

 

For example:

7. Know when and how to code for scalability. 14

10. Minimize global and shared data. 19

11. Hide information. 20

41. Make data members private, except in behaviorless aggregates (C-style structs). 72

76. Use vector by default. Otherwise, choose an appropriate container. 150

77. Use vector and string instead of arrays. 152

78. Use vector (and string::c_str) to exchange data with non-C++ APIs. 153

 

Really, don't take this the wrong way. I broke myself on endless nights, making the same assumptions as you make. That's just what's making C++ so hard!