Use of a list of pointers in C++, (inheritance or performance?)

Question

I have been given some code to read which does some geometric operations on meshes.

A mesh data structure, by definition, should contain at least the information regarding the coordinates of points, edge connectivity and face information.

So, the code given to me has classes to define vertex, edge and face data structure, named respectively as Vertex, Edge and Face.

However the mesh class looks like this.

class basemesh
{
public:
  /* Methods to operate on the protected data below.*/

protected:
   /*! list of edges */
  std::list<Edge*>           m_edges;

  /*! list of vertices */
  std::list<Vertex*>         m_verts;

  /*! list of faces */
  std::list<Face*>       m_faces;

}

My question: Why does the mesh data structure store a list of pointers rather than a list of the corresponding objects themselves.

e.g why not say directly std::list<Vertex>

I have seen this construct being used in a couple of other C++ codes

Does this have something to do with inheritance of classes? Or is it something to do with performance with regards to iterating on the list?

This basemesh class is, as the name suggests, a base class from which other specialized meshes are derived.

Simply pointers are faster than copies. They point, not making copies. — MahanGM, Nov 05 '13 at 20:36
Could it just be that the Edges, vertices and Faces are meant to be shared amongst instances? — juanchopanza, Nov 05 '13 at 20:36

score 2 · Accepted Answer · edited May 23 '17 at 10:32

There is no performance reasons here. Its simply a case of ownership sharing. Remember this as a rule of thumb: Pointers in C++ are used to share/pass ownership of a resource, or to provide polymorphic behaviour through dynamic binding.

People is talking about performence because you avoid copying the things. Blah, blah, blah. If you need to copy, you should copy. The only reason why its using pointers is because the author didn't want to copy the things when he/she copies the list of things, in other words, he/she wants to maintain the same things in two locations (lists): Ownership sharing, as I said before.

On the other hand, note that the class is called basemesh. So the real point of the pointers here could be to work with polymorphic vertices, edges, etc (Dynamic binding).

NOTE: If performance was the point here, I'm pretty sure the author would be using compact and aligned non-cache-miss-prone std::vector instead of std::list. In this case, the most presumable reason about the use of pointers is polymorphism, not performance. Anything related to pointers, dereferencing, and transversing linked lists will always have less performance than compact data, exactly what std::vector<Vertex> is, for example. Again, if the use of pointers is not for polymorphism, is for ownership related things, not performance.

Other note: Copying Yes, you are copying. But note what and how are copying. Vertices are, except of a very rare implementation, pairs of floats/ints. There is no gain at all about copying 64bits of floats vs 32/64bits of pointers.
Also note that, except you don't be so lucky, you are copying things stored at the same cache line, or almost at the cache.

A good rule about optimization nowadays is: Try to optimize memory accesses, not CPU cicles. I recommend this thread: What is "cache-friendly" code?, and this for a practical case: Why are elementwise additions much faster in separate loops than in a combined loop?. Finally, this thread contains good notes about optimizing using modern compilers.

score 1 · Answer 2 · answered Nov 05 '13 at 21:55

My guess is that it's either made for a very unusual specific case, but more likely, it's written by a programmer who doesn't know how heap allocations or std::list actually work, and just blindly use pointers.

It seems very unlikely a std::list of pointers to single vertices was the best option performance- or designwise.

score 0 · Answer 3 · answered Nov 05 '13 at 20:38

0

On a practical level if a method changes a point it does not need to reproduce the change in the other data structures. They will all point to the same thing.

But in terms of memory management it would be wise to use smart pointers,

answered Nov 05 '13 at 20:38

Ed Heal

59,252
17
87
127

score 0 · Answer 4 · answered Nov 05 '13 at 20:39

At a guess I'd say it's so that these objects can have pointers to each other (e.g. an Edge can have pointers to two Vertices, each of which can have a pointer back to the Edge).

If all the Vertices lived in a std::list in basemesh, then pointers to them would not be reliable, although list::iterators might work well enough.

Jack · Answer 5 · 2013-11-05T20:47:32.697

Using pointers is less efficient when retrieving inner data in general because you will have to dereference the value every time you access it.

But at the same time it will be more efficient when passing data around, since you are just passing pointers. I guess the solution chosen is related to the fact that data is shared between multiple objects by composition. Eg: multiple Edge instances could refer to same Vertex.

Now std::list guarantees that addresses to values contained are consistent until the element itself is removed so actually doing something like

Edge(const Vertex *v1, const Vertex *v2) { .. }

std::list<Vertex>::iterator it = std::advance(vertices.begin(), 3);
std::list<Vertex>::iterator it2 = std::advance(vertices.begin(), 5);
new Edge(&(*it), &(*it2));

Would work since addresses won't be invalidated so there is no real necessity to use pointers to store objects. Actually by using this solution you don't need to care about memory management of single objects since you won't need to delete them or wrap them into smart pointers.

score -1 · Answer 6 · answered Nov 05 '13 at 20:40

It's using pointers for performance reasons and to reduce the chance of an error.

Imagine the alternative of not using pointers. Every insertion into class basemesh would cause a copy of the object to be created, and every time you access an object, if you aren't careful, you'll get a copy as well.

For example, imagine this statement:

Edge e = m_edges[0];
e.doSomethingThatModifiesState();

In this example, without pointers, you'll have a copy of the object, and any operations you perform on it will not affect the actual edge object stored in m_edges.

With pointers, you don't have this issue:

Edge* e = m_edges[0];
e->doSomethingThatModifiesState();

In this example, no copy of the object is made, and when you do something, you get the intended behavior.

score -1 · Answer 7 · answered Nov 05 '13 at 20:59

-1

As many others said the speed is the most obvious reason. Another reason is to get polymorphic behavior through pointers to the base class.

answered Nov 05 '13 at 20:59

dnk

661
4
5

1

Thank you. Could you expand on the polymorphic behavior point? – smilingbuddha Nov 05 '13 at 21:07

Use of a list of pointers in C++, (inheritance or performance?)

7 Answers7