I have been using a Image<Node> as the main object to store the data for my program. It is a 2D grid of Node objects. The nodes have properties like bool Visited , float Priority , etc.

I often want to modify these nodes, put some of them in a vector to operate on them, pass them around, etc. Lately, it seems like some things would be easier if I had used a Image<Node*> instead.

Is the only overhead that I would have to then iterate through the image and delete all of the nodes when the image is destructed? That is, what are positives and negatives to each approach and when would you use one over the other?

Thanks,

David

Recommended Answers

All 6 Replies

That depends. I wouldn't care much about overhead in constructors and destructors, they are called rarely. Pointers would be better if you move a lot of data inside Image container and are a must if you want to use Node derivatives. But for example you can have Image<Node> and use std::vector<Node*> in your operations. If you think it would be easier to use pointers, use them.

BTW if Image<Node> is large (about 1M objects) I wouldn't use bool members, because it takes 4 bytes for every Node object. std::vector<std::vector<bool> > is smaller (it takes 1 bit for every value) and usually faster (due to caching).

>>Is the only overhead that I would have to then iterate through the image and delete all of the nodes when the image is destructed?

I would hardly call that an overhead unless you are making new images and destroying old ones all the time. The real overhead is indirection and memory spread. Assuming that Image<Node> would store nodes is contiguous memory (std::vector<Node> or something similar), then traversing the nodes linearly will be much more efficient than if you had a vector of pointers to heap-allocated Nodes. This is because you have to fetch the memory in the vector to get the pointer value, then you have to fetch the memory at that pointer value (address) which could be very different place and far-between. This breaks memory locality and will be the biggest overhead that you will suffer.

>>That is, what are positives and negatives to each approach and when would you use one over the other?
If you need to store base-class pointers because of dynamic polymorphism, then do so. Otherwise, I don't see any real advantage to it.

As for the bigger issue, typically, you want to abstract away the reference to your nodes. I would suggest you take a look at the PropertyMapConcept in Boost Graph Library. Basically: if you have a vector of Node pointers, then the fastest way to access one Node at any time is by its pointer; if you have a vector of Nodes, then the fastest way to access one Node at any time is by its index; if you have a list of Nodes, then the fastest way to access one Node at any time is by its iterator; if you have a map of Nodes, then the fastest way to access one Node at any time is by its key-value... so on. The point here is that, for any storage you like, you can find a unique value of some type that is an invariant way of accessing the node. In BGL, this is called the "vertex_descriptor". This is a very good way to abstract away your storage mechanism, then write generic code, and test any combination of storage strategies you like and see which performs the best. Don't commit to one storage strategy too early, write generic code and later select the strategy that is the most appropriate (fastest and/or safest).

The particular case that had caused me problems is this:

typedef itk::Image<Node, 2> ImageType;
itk::ImageRegionConstIterator<ImageType> imageIterator = 

  itk::ImageRegionConstIterator<ImageType>(image, region);

// make a vector of pointers to particular nodes
std::vector<Node*> nodes;
  while(!imageIterator.IsAtEnd())
    {
    nodes.push_back( &(imageIterator.Get()) );
    ++imageIterator;
    }

With the above, I get "warning: taking address of temporary" (and indeed it works incorrectly). The .Get() method of the iterator return a reference to the data at the pixel, so I thought that would be ok, but I guess I don't fully understand references.

My thought was that if the image was Image<Node*, 2> then .Get() would just return the address of the actual node and everything would be ok. Does that make sense?

What is the definition of itk::ImageRegionConstIterator<ImageType>::Get() ? I'm betting you're getting the memory address where the return value from Get() is stored instead of the actual pointer value.

You'll probably have to get rid of the '&' for it to work.

Referring to the dox, the following should work:

typedef itk::Image<Node, 2> ImageType;
itk::ImageRegionConstIterator<ImageType> imageIterator = 

  itk::ImageRegionConstIterator<ImageType>(image, region);

  // make a vector of pointers to particular nodes
  std::vector<const Node*> nodes; //note const pointer (because ImageRegionConstIterator is const too.
  while(!imageIterator.IsAtEnd())
    {
    nodes.push_back( &(imageIterator.Value()) ); //Value returns a const ref.
    ++imageIterator;
    }

It would seem that GetIndex() would also be a viable option. But the above is good.

Mike,

Yea you're right! I didn't see the Value function. It does just what I was looking for. Thought it seems inappropriately named... I would have said something more like GetReference().

Thanks!

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.